# Recurrence relation related to integer partition

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.

• This is proved by breaking up the partitions counted by $p(n,S)$ based on the number of occurrences of $s$. Jan 29 at 14:17
• What is the $s$ on the upper bound of the sum? I mean like as far as I got out, $s$ is a random element from the set $S$, what does $\frac{n}{s}$ mean? Feb 2 at 10:12
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$$).