Given $n\in\Bbb{N}$, the number of (unrestricted) integer partitions of $n$ are given by $$\sum_{n\geq0}p(n)x^n=\prod_{j\geq1}\frac1{1-x^j}.$$ Define the collapsed partitions of $n$ to be the partitions of $n$ with multiplicities removed. For example, if $n=4$ then its partitions are $4, 31, 22, 211, 1111$. The collapsed partitions become $4, 31, 2, 21, 1$.

Denote the sum of the $k$-th powers of the collapsed partitions of $n$ by $cp_k(n)$. For example, $cp_1(4)=4+3+1+2+2+1+1=14$. The first few values of $cp_1(n)$ are: $$cp_1(1)=1, cp_1(2)=3, cp_1(3)=7, cp_1(4)=14, cp_1(5)=26.$$

Recall the Eulerian polynomials of type $A$ defined by $$\sum_{n\geq0}(n+1)^kx^n=\frac{A_k(x)}{(1-x)^{k+1}}.$$

Experiments prompt me to ask: is this true? $$\sum_{n\geq0}cp_k(n+1)x^n=\frac{A_k(x)}{(1-x)^{k+1}}\prod_{j\geq1}\frac1{1-x^j}.$$


It is easy to see that $$cp_k(n) = \sum_{i=1}^n p(n-i)\cdot i^k,$$ where $p(n-i)$ stands for the number of (collapsed) partitions of $n$ that contain $i$ as a part.

Since $i^k$ is the coefficient of $x^{i-1}$ in $\frac{A_k(x)}{(1-x)^{k+1}}$, we conclude that $cp_k(n)$ equals the coefficient of $x^{n-1}$ in $\frac{A_k(x)}{(1-x)^{k+1}}\cdot \prod_{j\geq 1}\frac{1}{1-x^j}$. QED

  • $\begingroup$ I found the same answer, but 27 minutes after you. My sum ran from $i=1$ to $i=n$, and I simply said (in my deleted answer) that $i$ participates in exactly $p(n-i)$ stripped partitions, so the identity is clear. The notation $A_k(x)$ is irrelevant to the question and the answer. $\endgroup$ – GH from MO Aug 25 '18 at 16:33
  • $\begingroup$ @GHfromMO: I've changed summation to start with $i=1$ to avoid confusion. The answer is indeed quite straightforward. I do not quite follow your comment about $A_k(x)$ being irrelevant. $\endgroup$ – Max Alekseyev Aug 25 '18 at 16:39
  • $\begingroup$ What I meant is: you can ask the question and answer it without ever mentioning $A_k(x)$. The identity you state is equivalent to the OP's identity. $\endgroup$ – GH from MO Aug 25 '18 at 16:45

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.