Skip to main content
3 of 4
minor correction
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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),z) - F((5,2),z) - F((5,2),z) - F((4,3),z) + F((3,2,2),z))$$ $$={\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)$.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152