By a partition $\pi$ of an integer $n\ge 1$, we mean here a representation of $n$ as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if $n=4$, then the partitions $\pi$ are $1+1+1+1$, $1+1+2$, $1+3, 2+2$, and $4$). For any partition $\pi$, define $A(\pi)$ to be the number of $1$'s which appear in $\pi$, and define $B(\pi)$ to be the number of distinct integers which appear in $\pi$. (E.g., if $n=13$ and $\pi$ is the partition $1+1+2+2+2+5$, then $A(\pi)=2$ and $B(\pi) = 3$). Prove that, for any fixed $n$, the sum of $A(\pi)$ over all partitions of $\pi$ of $n$ is equal to the sum of $B(\pi)$ over all partitions of $\pi$ of $n$.
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, function, real analysis, induction, combinatorics unsolved
21.10.2013 09:57
any solution, please?
21.10.2013 11:38
i have proof by induction. Let $P_i(k)$ to be the number for over all partitions $\pi $ of $k$ by $i$ ones. So we have that \[ A_n(\pi)=1P_0(n-1)+2P_0(n-2)+...+nP_0(0) \] and \[ A_n(\pi)-A_{n-1}(\pi)=P_0(n-1)+...+P_0(0) .\] So easily get that \[ B_n(\pi)-B_{n-1}(\pi)=P_0(n-1)+...+P_0(0) \] because, $ B_n(\pi)-P_0(n-1)-...-P_0(0) $ is sum of number of distinct integers of partitions $ \pi $ of $n$ by $0$ ones. Who can solve the problem by generating function?
21.10.2013 15:45
Here is a solution using generating functions. Naturally, we would start with the second because it is probably easier... Indeed, if we let $S$ be the set $\{1, 2, \cdots, n\}$, we count the number of sets containing $i$ for $i \in S$. This is: \[B(\pi) = \sum_{i=1}^{n} \left(\dfrac{1}{\prod_{j=1}^{n} (1-x)^j} - \dfrac{1}{\prod_{j=1, j \neq i}^{n} (1-x)^j}\right)\] Which simplifies to $B(\pi) = \dfrac{x}{(1-x) \prod_{j=1}^{n} (1-x)^j}$. Now for $A(\pi)$, notice the bijection between partitions having $i$ ones for $i \in S$ and the sets of $n-i$ elements without any ones (obviously just fill the missing ones). For a partition with no ones, it is: \[f(x) = \dfrac{1}{\prod_{j=2}^{n} (1-x)^j}\] Now, for each $i$, there will be $i$ ones, hence the coefficient of $x^{n-i}$ in the expansion of $f(x)$ must be multiplied by $i$. That means $A(\pi)$ becomes: \[\left(\sum_{i=1}^{n} ix^i\right)f(x)\] Which simplifies to $A(\pi) = \dfrac{x}{(1-x)^2}f(x)$ because the $\sum_{i=1}^{n} ix^i$ is just the convolution of $1 \ast 1$. Comparing the co-efficients shows $A(\pi) = B(\pi)$.
21.10.2013 15:58
Okay this seems to be a rather absurd bijective proof, but hey, it's a bijective proof! Fix $n$. Suppose $P(i)$ is the number of partitions of $n$ that contains the number $i$, and $Q(i)$ is the number of partitions of $n$ that contains at least $i$ instances of the number $1$. Trivially $P(i) = Q(i)$ for all $i$; remove the number $i$ from the partitions counted in $P(i)$ and the first $i$ instances of $1$ from the partitions counted in $Q(i)$ and the rest will be identical. (For example, when $n = 9$, the partition $4+2+2+1 = (4+2+1)+2$ counted in $P(2)$ and the partition $4+2+1+1+1 = (4+2+1)+1+1$ counted in $Q(2)$ will be identical after removing the $2$ and the $1+1$ outside the brackets.) However, $\sum P(i) = \sum A(\pi)$; each partition is counted once for each distinct number it has. (For example, the partition $\pi = 4+2+2+1$ is counted at $P(1), P(2), P(4)$, counted $3$ times, and indeed $A(\pi) = 3$.) Similarly, $\sum Q(i) = \sum B(\pi)$; each partition is counted once for each $1$ it has. (For example, the partition $\pi = 4+2+1+1+1$ is counted at $Q(1), Q(2), Q(3)$, counted $3$ times, and indeed $B(\pi) = 3$.) Since $\sum P(i) = \sum Q(i)$, it follows that $\sum A(\pi) = \sum B(\pi)$.
04.08.2014 00:59
We can also instead just use $P(n)$, referring to the number of partitions of $n$, where we define $P(0)$ as $1$. Let $S_n$ be the set of all partitions of $n$. Then we claim that \[\sum_{\pi \in S_n} A(\pi) = P(n-1)+P(n-2)+\cdots+P(1)+P(0)\] and \[\sum_{\pi \in S_n} B(\pi) = P(n-1)+P(n-2)+\cdots+P(1)+P(0)\]so that by transitivity, \[\sum_{\pi \in S_n} A(\pi) = \sum_{\pi \in S_n} B(\pi)\] For the first statement, we proceed by induction on $n$. As a base case, when $n=1$, there is only one partition: $1$, which has a single $1$, so that $\sum_{\pi \in S_1} A(\pi) = 1$, while $P(0) = 1$ as well. For the inductive step, assume that for $n = k$, $\sum_{\pi \in S_n} A(\pi) = P(n-1)+P(n-2)+\cdots+P(1)+P(0)$. Then for $n=k+1$, we must consider partitions of $k+1$. To count $1$s in partitions, note that a partition that does not contain a $1$ will add nothing to the sum, so that we only consider partitions with at least one of $1$. Removing the first $1$ in a partition of $k+1$, we are left with a partition of $k$, for which the count of $1$s is accounted for in $\sum_{\pi \in S_k} A(\pi)$. So, $\sum_{\pi \in S_{k+1}} A(\pi)$ is equal to $\sum_{\pi \in S_k} A(\pi)$ together with the number of leading $1$s removed over all permutations, but this is just the number of partitions of $k$, or $P(k)$, so that we have: \[\sum_{\pi \in S_{k+1}} A(\pi) = \left(\sum_{\pi \in S_k} A(\pi)\right) + P(k) = P(k)+P(k-1)+\cdots+P(1)+P(0)\]and the induction is complete. For the second statement, note that $\sum_{\pi \in S_n} B(\pi)$ can be counted by determining how many partitions of $n$ contain at least one of $1$, how many contain at least one of $2$, ..., how many contain at least one of $n$, and then summing these. We also see that the number of partitions that contain at least one of $j$ for $1 \le j \le n$ is just $P(n-j)$, since the $j$ addend can be removed and we may partition $n-j$ in any way and then place $j$ in the appropriate spot. So, we also have that $\sum_{\pi \in S_n} B(\pi) = P(n-1)+P(n-2)+\cdots+P(1)+P(0)$, so that the result does hold.
04.09.2022 05:25
We use multi-variate generating function. Let $F(x,y) = (1+xy+(xy)^2+\cdots)(1+x^2+x^4+\cdots) \cdots (1+x^n+x^{2n}+\cdots) \cdots$ Then $[x^ny^k] F(x,y)$ is the number of ways to partition $n$ with $k$ 1's. Thus, $A(n)=[x^n] \frac{\partial}{\partial y} F(x,y) |_{y=1}$ Analogously we get $B(n) = [x^n] \frac{\partial}{\partial y} G(x,y)|_{y=1}$ Where $G(x,y)$ is $\prod\limits_{n\ge 1} (1+\frac{yx^n}{1-x^n})$ Now we show that $\sum A(n)x^n = \sum B(n)x^n$. We first multiply both by $\prod\limits_{n\ge 1} (1-x^n)$ to see it suffices to show $[x^n] \frac{\partial}{\partial y}\frac{1-x}{1-xy}|_{y=1} = [x^n] \frac{\partial}{\partial y}\prod\limits_{n\ge 1} (1+(y-1)x^n)|_{y=1} $ for all $n\ge 1$ Note LHS is $[x^n] \frac{\partial}{\partial y}((xy)^n -x^ny^{n-1} )= 1$ RHS is $ [x^n] \frac{\partial}{\partial y}\prod\limits_{n\ge 1} (1+yx^n)|_{y=0}$. When we expand and differentiate, the only way to get this not to vanish at $y=0$ is to have a $yx^n$ term, whose derivative wrt y is $x^n$, and this means the answer is 1.