I have to prove a recurrence relation which is given by:
$p_{(n,S)} = \displaystyle\sum_{t=0}^{\lfloor \frac{n}{s} \rfloor}$${p_{(n − st , S-\{s\})}}$
assuming that $\{s\}$ is an arbitrary fixed element of $S$.
(We assume that $p_{(0,S')}$ is to be equal to $1$ for any $S'$ and $p_{(m,S')}$ is equal to $0$ for any
negative $m$ and every $S'$.)
so at last $p_{(n,S)}$ is the integer partition of $n$ from the set of allowed elements $S$. I read about integer partition and young's diagram and even went through some videos reagrading how we can construct a generating function for $p_{(n)}$ but I am unable to prove this recurrence relation. Any help will be appreciated.
Thanks in advance.
Best Answer
This is an elaboration on Mike Earnest's comment and a slightly more formal statement of your claim.
For $S \subseteq \mathbb{N}$ and any $s \in S$, $$ p(n,S) = \sum_{t=0}^{\lfloor n/s \rfloor} p(n-ts,S \setminus \{s\}).$$
Proof: A partition of $n$ included in the count $p(n,S)$ has some number of parts $s$ and the other parts come from $S \setminus \{s\}$. More explicitly, if $s$ occurs exactly $t$ times in $\lambda \vdash n$, then removing those $t$ copies of $s$ from $\lambda$ leaves a partition of $n-ts$ with parts from $S \setminus \{s\}$. There are $p(n-ts,S \setminus \{s\})$ of the "leftover" partitions. Note that $t$ can vary from 0 (i.e., $\lambda$ contains no part $s$) to $\lfloor n/s \rfloor$ (the maximal possible number of parts $s$).