I am wondering if there is a standard notation and name for the following. Let $\lambda$ be a partition $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_r\geq 1$ of $n$ into $r$ parts. Then we can form a partition $\mu$ of $r$ by keeping track of how many times each integer occurs in $\lambda$. For example the partition (3,3,2,2,2,1,1) of 14 into 7 parts has associated partition $\mu=(3,2,2)$ of $7$ because one integer appears 3 times and 2 integers appear twice. If $\mu$ is a partition of $r$, let $C_{n,\mu}$ be the number of partitions $\lambda$ of $n$ into $r$ parts such the partition associated to $\lambda$ is $\mu$.

Question. What is $C_{n,\mu}$ called and what is the standard notation? Is the some formula or combinatorial rule to compute it?


Let $\mu=(\mu_1,\dots,\mu_m)$ and $\gamma_i$ be the number of parts equal $i$ in $\mu$. Then $$\sum_{i=1}^r \gamma_i = m\quad\text{and}\quad\sum_{i=1}^r i\cdot\gamma_i = r.$$

Then $C_{n,\mu}$ equals $\frac{1}{\gamma_1!\cdots \gamma_r!}$ times the number of solutions to $$(\star)\qquad \mu_1\cdot y_1 + \dots + \mu_m\cdot y_m = n$$ in pairwise distinct positive integers $y_1,\dots, y_n$.

Without of the distinctness requirement, the number of solutions to $(\star)$ has generating function: $$F(\mu,x) = \frac{x^{\mu_1+\dots+\mu_m}}{(1-x^{\mu_1})\cdots (1-x^{\mu_m})}.$$ To enforce the distinctness, one can use inclusion-exclusion.

For any unordered partition $P=(P_1,\dots,P_k)$ of the set $[m]$, we define $\mu_P$ as "contraction" of $\mu$, where parts of $\mu$ with indices from the same part of $P$ are summed up and represent a single element of $\mu_P$.

By inclusion-exclusion, we have $C_{n,\mu}$ equal the coefficient of $x^n$ in $$\frac{1}{\gamma_1!\cdots \gamma_r!} \sum_{P} (-1)^{m-k}\cdot (|P_1|-1)!\cdots (|P_k|-1)!\cdot F(\mu_P,x).$$

Example. For $\mu=(3,2,2)$, we have $m=3$, $r=3+2+2=7$, $\gamma=(0,2,1,0,0,0,0,0)$. The have the following set partitions of $[3]=\{1,2,3\}$ and the corresponding contracted partitions $\mu_P$:

$P=\{\{1,2,3\}\}\qquad \mu_P=(7)$

$P=\{\{1,2\},\{3\}\}\qquad \mu_P=(5,2)$

$P=\{\{1,3\},\{2\}\}\qquad \mu_P=(5,2)$

$P=\{\{2,3\},\{1\}\}\qquad \mu_P=(4,3)$

$P=\{\{1\},\{2\},\{3\}\}\qquad \mu_P=(3,2,2)$

So, the generating function for $C_{n,(3,2,2)}$ is $$\frac{1}{2} (2\cdot F((7),x) - F((5,2),x) - F((5,2),x) - F((4,3),x) + F((3,2,2),x))$$ $$={\frac {{x}^{13} \left( 3\,{x}^{6}+6\,{x}^{5}+8\,{x}^{4}+8\,{x}^{3}+6\,{x}^{2}+3\,x+1 \right) (1-x)^2}{ (1-x^3) (1-x^4) (1-x^5) (1-x^7) }}$$ $$=x^{13} + x^{14} + 2\cdot x^{15} + x^{16} + 2\cdot x^{17} + 2\cdot x^{18} + 3\cdot x^{19} + 3\cdot x^{20} + 6\cdot x^{21} + 3\cdot x^{22} + \dots.$$

For example, the coefficient of $x^{21}$ enumerates the following six partitions of 21: $(7,7,2,2,1,1,1)$, $(6,6,3,3,1,1,1)$, $(5,5,4,4,1,1,1)$, $(5,5,3,3,3,1,1)$, $(4,4,3,3,3,2,2)$, and $(5,5,5,2,2,1,1)$.

  • $\begingroup$ It will take me a moment to digest this. Thanks for the answer. $\endgroup$ – Benjamin Steinberg Apr 24 '15 at 16:35
  • 1
    $\begingroup$ Just addressing your question about history and notation, Andrews uses $\{f_i\}_{i=1}^\infty$ for the partition $\{1^{f_1} 2^{f_2} 3^{f_3} \cdots \}$ of $\sum f_i \cdot i$ in The Theory of Partitions (especially chapter 8). I don't believe he names it, but I've seen this called the frequency representation (which is compatible with his selection of $f$). Your object seems to be a sorted version of this with zeros removed. $\endgroup$ – Brian Hopkins Apr 30 '15 at 16:17

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.