Track / Stage 6 / 134 of 400 #1134 of 2000

Problem 1134

National olympiad, first round

Combinatorics Difficulty 6.2 Prove it

33. For a positive integer $n$ , partition $n$ into the sum of one or several positive integers, and arrange these numbers in non-decreasing order, which is called a partition $\pi$ of $n$ . For any partition $\pi$ , define $A(\pi)$ as the number of times the number 1 appears in the partition, and $B(\pi)$ as the number of distinct numbers in the partition (for example, for a partition $\pi: 1+1+2+2+2+5$ of $n=13$ , $A(\pi)=2, B(\pi)=3$ ). Prove that for any given positive integer $n$ , the sum of all $A(\pi)$ is equal to the sum of all $B(\pi)$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

33. Let $p(n)$ denote the number of all distinct partitions of $n$ , and define $p(0)=1$ . We consider the following quantity: $S=$ $\sum_{k=0}^{n-1} p(k)$ .

First, in the partitions of $n$ , those with the first number being 1 are $p(n-1)$ in number, those with the first two numbers being 1 are $p(n-2)$ in number, $\cdots$ , those with the first $n-1$ numbers being 1 are $p(1)$ in number, and those with the first $n$ numbers being 1 are $p(0)$ in number. It is clear that in $S=\sum_{k=0}^{n-1} p(k)$ , the partition $\pi$ is counted once in $p(n-1)$ , $p(n-2)$ , $\cdots$ , $p(n-A(\pi))$ , a total of $A(\pi)$ times, so $S=\sum A(\pi)$ . On the other hand, the partitions containing the number $i(1 \leqslant i \leqslant n)$ are $p(n-i)$ in number, so in $S=\sum_{k=0}^{n-1} p(k)=\sum_{i=1}^{n} p(n-i)$ , a partition $\pi$ is counted as many times as it has distinct numbers, i.e., each $\pi$ is counted $B(\pi)$ times. Therefore, we also have $S=\Sigma B(\pi)$ , so $S A(\pi)=\sum B(\pi)$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.