# Number of partitions with restriction on the greatest part and on the number of parts

I apologise that my original question wasn't clear .
I've made some improvements to make it more understandable (hopefully) .

I need help about the following two theorems from G. Chrystal's "Algebra", Part II, 1900, pp. 559-561, regarding partitions of integers.
( A remark just for general background :
G. Chrystal's "Algebra" is an old algebra text-book (for higher classes of secondary schools and for colleges), one that influenced the famous mathematician S.Ramanujan . Unfortunately, something has gone wrong in the teaching of algebra since then...)

The author uses the following (a bit oldish) notation :
P(n|p|q) means the number of partitions of n into p parts, the greatest of which is q ;
P(n|p|not>q) means the number of partitions of n into p parts, no one of which exceeds q ;
P(n|*|not>q) means the number of partitions of n into any number of parts, no one of which
exceeds q .

According to the author, two following theorems hold (in author's notation and formulation):

Theorem I :

P(n|p|not>q) = P(n-p|* |not>p) - ∑P(n-µ1-p|* |not>p) + ∑P(n-µ2-p|* |not>p) -
- ∑P(n-µ3-p|* |not>p) +-

Here the summations are with respect to µ1, µ2, µ3, … ;
µ1 is any one of the numbers q, q+1, …, q+p-1;
µ2
is the sum of any two of them ;
µ3 is the sum of any three,
and so on.
The series of sums is to be continued so long as n-µ1-p, n-µ2-p, n-µ3-p, ... are positive .
If P(n|p|not>q) comes out zero or negative, this indicates that the partition in question is impossible .

Theorem II :

P(n|not>p|not>q) = P(n|* |not>p) - ∑P(n-v1|* |not>p) + ∑P(n-v2|* |not>p) -
- ∑P(n-v3|* |not>p) +- ...

Here v1, v2, v3, … have the same meanings with regard to q+1, q+2, … , q+p as µ1, µ2,... with regard to q, q+1, … , q+p-1 .

The two theorems can be very useful in calculating the number of so called doubly restricted partitions (i.e., partitions with restrictions on the number of their parts, AND on the size of their parts) .
Using these theorems for such calculations, you don't have to make use of generating functions,
q-series, and so on (which, of course, doesn't mean that generating functions or q-series are not useful) .
Unfortunately, the author gives no proof for the two theorems .
Both theorems seem to be provable by inclusion-exclusion principle, but I'm unable to find out the proofs .
I'm hoping somebody can help me to prove the two theorems, please.

• As I can see, my question was closed on Aug 26 as unclear . – J.Grody Aug 31 '18 at 9:23
• Although I've made some improvements in my original question to make it more understandable, but, as you say, the question is still unclear, so you closed it . Unfortunately, I really don't see how I can make it more clear. Please, would you mind reading it once more ? Anyway, I'm extremely sorry for having waisted your time . – J.Grody Aug 31 '18 at 10:06
• First of all, thank you for reopening my question ! – J.Grody Sep 7 '18 at 16:25
• I absolutely agree with your explanation about why it's really the same theorem twice. As for the first theorem, I'm not sure that the expression you've written on the right side of the equation is quite the same that is given in Chrystal's "Algebra" . According to your advice, I tried to use "MathJax" to render the equation exactly as it looks in Chrystal's book : $$P( n | p | \leqslant q ) = P( n-p | * | \leqslant p )\; -$$ $$-\;\sum P( n-\mu_1-p | * | \leqslant p )\; +$$ $$+\;\sum P(n-\mu_2 | * | \leqslant p )\;\mp \cdots$$ \\ The summations are with respect to \mu_1,\mu_2,\ldots . – J.Grody Sep 7 '18 at 20:24
• I absolutely agree with your explanation about why it's really the same theorem twice. As for the first theorem, I'm not sure that the expression you've written on the right side of the equation is quite the same that is given in Chrystal's "Algebra" . According to your advice, I tried to use "MathJax" to render the equation exactly as it looks in Chrystal's book : – J.Grody Sep 7 '18 at 20:34

Since the primary technique applied in the book is manipulation of generating functions, that seems likely to be the intended approach here too. I'm sure there's a more elegant proof than this; if you find it, please post your own answer.

Chrystal gives (p557)

$$1 + \sum P(n|p|\le q)z^p x^n = \frac{1}{\prod_{i=1}^q 1-zx^i} \tag{6}$$

$$1 + \sum P(n|p|*)z^p x^n = \frac 1{\prod_{i=1}^\infty 1 - zx^i} \tag{9}$$

But IMO it's more natural (or maybe just a more modern convention) to take $P(0|0|*) = P(0|0|\le q) = 1$ and pull in that loose $1$ from the two left-hand sides:

$$\sum_{n,p} P(n|p|\le q)z^p x^n = \frac{1}{\prod_{i=1}^q 1-zx^i} \tag{6'}$$

$$\sum_{n,p} P(n|p|*)z^p x^n = \frac 1{\prod_{i=1}^\infty 1 - zx^i} \tag{9'}$$

Now, by $9'$ we have $$\sum_{n,p} (-1)^{|s|} P\left(n-\sum_{i \in s} i \middle| p \middle| *\right) z^p x^n = \frac{(-1)^{|s|} x^{\sum_{i \in s}i}}{\prod_{i=1}^\infty 1 - zx^i}$$ so summing over $s \subseteq S$ we get $$\frac{\sum_{s \subseteq S} (-1)^{|s|} x^{\sum_{i \in s}i}}{\prod_{i=1}^\infty 1 - zx^i}$$

If we consider just the numerator (since the denominator is independent of $S$), let's see what happens when we adjoin an element to $S$. $$\sum_{s \subseteq S \cup \{s_0\}} (-1)^{|s|} x^{\sum_{i \in s}i} = \sum_{s \subseteq S} (-1)^{|s|} x^{\sum_{i \in s}i} + \sum_{s \subseteq S} (-1)^{|s \cup \{s_0\}|} x^{\sum_{i \in s \cup \{s_0\}}i} \\ = (1 - x^{s_0}) \sum_{s \subseteq S} (-1)^{|s|} x^{\sum_{i \in s}i}$$ So by induction, $$\sum_{s \subseteq S} (-1)^{|s|} x^{\sum_{i \in s}i} = \prod_{j \in S} 1 - x^j$$

Summary so far: $$\sum_{s \subseteq S} \sum_{n,p} (-1)^{|s|} P\left(n-\sum_{i \in s} i \middle| p \middle| *\right) z^p x^n = \frac{\prod_{j \in S} 1 - x^j}{\prod_{i=1}^\infty 1 - zx^i}$$

Now, on p559 in the proof of $(15)$ we encounter the identity

$$\frac{1}{\prod_{i=1}^\infty 1-zx^i} = 1 + \sum \frac{x^p z^p}{\prod_{i=1}^p 1-x^i}$$

Therefore $$\sum_{s \subseteq S} \sum_{n,p} (-1)^{|s|} P\left(n-\sum_{i \in s} i \middle| p \middle| *\right) z^p x^n = \sum_{p \ge 0} x^p z^p \frac{\prod_{j \in S}1 - x^j}{\prod_{i=1}^p 1-x^i}$$

Now we switch tacks. On page 560 we encounter the identity

$$\frac{1}{\prod_{i=0}^q 1-zx^i} = 1 + \sum_{p \ge 1} z^p \frac{(1-x^{q+1})(1-x^{q+2})\cdots(1-x^{q+p})}{(1-x)(1-x^2)\cdots(1-x^p)}$$

Multiplying both sides by $(1 - z)$ and rearranging we get $$\frac{1}{\prod_{i=1}^q 1-zx^i} = \sum_{p \ge 0} z^p x^p \frac{\prod_{j=q}^{q+p-1} 1-x^j}{\prod_{i=1}^p 1-x^i}$$

The LHS is familiar from $(6)$; the RHS matches our previous expression in terms of $S$ if we set $S = \{q, q+1, \ldots, q+p-1\}$. Therefore we find that

$$\sum_{n,p} P(n|p|\le q) z^p x^n = \sum_{s \subseteq \{q, q+1, \ldots, q+p-1\}} \sum_{n,p} (-1)^{|s|} P\left(n-\sum_{i \in s} i \middle| p \middle| *\right) z^p x^n$$

and by equating the coefficient of $z^p x^n$ we have $$P(n|p|\le q) = \sum_{s \subseteq \{q, q+1, \ldots, q+p-1\}} (-1)^{|s|} P\left(n-\sum_{i \in s} i \middle| p \middle| *\right)$$

But since

$$P(n|p|*) = P(n-p|*|\le p) \tag{15}$$

we obtain $$P(n|p|\le q) = \sum_{s \subseteq \{q, q+1, \ldots, q+p-1\}} (-1)^{|s|} P\left(n-p-\sum_{i \in s} i \middle| * \middle| \le p\right)$$ which is theorem 1 in different notation.

Finally, since $P(n | p | \le q) = P(n - p | \le p | \le q-1)$ by subtracting $1$ from each part, theorem 2 follows.

• Oh, my! It's really a pleasure to see your proof and your excellent ability to deal with the algebraic manipulations with generating functions. After having read your proof, I think it is very hard (perhaps even impossible) to find some "more elegant" or purely combinatorial proof. By the way: is there any possibility to preview the MathJax content when writing comments? Thank you very much! Best regards, J. Grody. – J.Grody Sep 8 '18 at 17:39
• Tweaking theorem 2 to $$P(n|\le p|\le q) = \sum (-1)^{|s|} P(n -\sum i | \le p | *)$$ is what made me give up on searching for a combinatorial proof. If the RHS instead had $\le p - |s|$ and a different range for the inclusion-exclusion I could see it, but the bounding box of the Ferrers diagram needs to take into account the parts accounted for by $s$. – Peter Taylor Sep 8 '18 at 18:20
• To preview MathJax for comments I work in the answer box and then cut and paste. – Peter Taylor Sep 8 '18 at 18:21
• Ok, thank you for your insightful remark about little chance for inclusion-exclusion principle to be usable in thus case . – J.Grody Sep 8 '18 at 19:00