# A question of terminology regarding integer partitions

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)$.

• It will take me a moment to digest this. Thanks for the answer. – Benjamin Steinberg Apr 24 '15 at 16:35
• 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. – Brian Hopkins Apr 30 '15 at 16:17