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.

  • 1
    $\begingroup$ This is proved by breaking up the partitions counted by $p(n,S)$ based on the number of occurrences of $s$. $\endgroup$ Jan 29 at 14:17
  • $\begingroup$ 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? $\endgroup$
    – Aryan
    Feb 2 at 10:12

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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.