Kvant Math Problem 885

The quantity $q(n)$ equals the sum, over all partitions $\lambda$ of $n$, of the number of distinct values appearing among the parts of $\lambda$.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 24m27s
Source on kvant.digital

Problem

$ \colsep{0pt}{\begin{array}{lc} \text{Разбиения}\quad&\text{Разбросы}\ 1+1+1+1&1\ 2+1+1&2\ 2+2&1\ 3+1&2\ 4&1\\hline p(4)=5&q(4)=7 \end{array}}$

Fig. 2

For each positive integer $n$, let $p(n)$ denote the number of partitions of $n$ into a sum of positive integers (partitions differing only in the order of the summands are considered the same; see Fig. 2). The number of distinct integers occurring in a given partition will be called its spread.

  1. Prove that the sum $q(n)$ of the spreads of all partitions of the number $n$ is equal to $$1+p(1)+p(2)+\ldots+p(n-1).$$.
  2. Prove that this sum does not exceed $\sqrt{2n},p(n)$.

A. V. Zelevinsky

Tournament of Towns (Spring 1984)

1. Identity for $q(n)$

The quantity $q(n)$ equals the sum, over all partitions $\lambda$ of $n$, of the number of distinct values appearing among the parts of $\lambda$. This can be rewritten as counting ordered pairs $(\lambda,a)$, where $\lambda$ is a partition of $n$ and $a$ is a distinct part occurring in $\lambda$.

Fix a positive integer $a \le n$. Consider all pairs $(\lambda,a)$ in which the partition $\lambda$ contains at least one part equal to $a$. From such a pair, remove one occurrence of the part $a$ from $\lambda$. The result is a partition $\mu$ of $n-a$.

This construction does not depend on any choice among identical parts, since only the value $a$ is specified and exactly one occurrence is removed. Multiple copies of $a$ in $\lambda$ are irrelevant because the pair $(\lambda,a)$ does not distinguish between them; it only asserts that at least one copy exists.

Conversely, start from any partition $\mu$ of $n-a$ and fix the same integer $a$. Adding one additional part equal to $a$ produces a partition $\lambda$ of $n$ in which $a$ is a part. This construction always produces a valid pair $(\lambda,a)$.

These two transformations are inverse to each other: removing one $a$ from $\lambda$ and then adding it back recovers the original partition, and adding one $a$ and then removing one $a$ also recovers the original partition. This gives a bijection between partitions of $n-a$ and pairs $(\lambda,a)$.

Therefore the number of such pairs equals $p(n-a)$, and summing over all $a$ yields

$$q(n)=\sum_{a=1}^{n} p(n-a).$$

Since $p(0)=1$, reindexing gives

$$q(n)=1+p(1)+p(2)+\cdots+p(n-1).$$

2. Inequality $q(n)\le \sqrt{2n},p(n)$

Let $d(\lambda)$ denote the number of distinct part sizes in a partition $\lambda$ of $n$. Then

$$q(n)=\sum_{\lambda \vdash n} d(\lambda).$$

Let the distinct parts of $\lambda$ be $a_1<a_2<\cdots<a_k$. Each $a_i$ appears at least once in $\lambda$, so

$$a_1+a_2+\cdots+a_k \le n.$$

The left-hand side is minimized, for a fixed $k$, when the distinct parts are $1,2,\dots,k$, giving

$$1+2+\cdots+k=\frac{k(k+1)}{2}\le n.$$

This implies $k(k+1)\le 2n$, hence $k^2\le 2n$. Therefore every partition of $n$ satisfies

$$d(\lambda)\le \sqrt{2n}.$$

Substituting this bound into the expression for $q(n)$ gives

$$q(n)\le \sum_{\lambda \vdash n} \sqrt{2n}=\sqrt{2n},p(n).$$

Conclusion

The first identity follows from a bijection between partitions of $n-a$ and pairs consisting of a partition of $n$ together with a distinguished part value $a$. The second estimate follows from bounding the number of distinct part sizes in any partition of $n$ by the maximal size of a strictly increasing sequence of positive integers with sum at most $n$, which is at most $\sqrt{2n}$.