partitions of positive integer $n$ with respect to a multiset

275 Views Asked by At

Recently, I think on a new problem related to partitions.

Let $n$ be a non-negative integer and $\mathbb{A}=\{a_1,\ldots,a_k\}$ be a multiset with $k$ not necessarily distinct positive integers. We denote by $D(n\mid\mathbb{A})$, the number of ways to partition $n$ in the form $a_1x_1+\cdots+a_kx_k$, where $x_i$'s are positive integers and $x_i\leqslant x_{i+1}$ whenever $a_i=a_{i+1}$.

I would like to calculate generation function of $D(n|A)$.

1

There are 1 best solutions below

2
On BEST ANSWER

Let's try again. (The original text is gone. If one would like to waste one's time, it is available through the "edited" link just below the examples.)

Instead of starting with a structureless multiset, let's go with: $I$ is the cardinality of the set of distinct elements in $A$, and $B = \{(b_i, m_i), i \in I\}$ where the $b_i$ are the distinct elements of $A$ and $m_i$ is the multiplicity of $b_i$ in $A$. So, for example, $\sum_{i \in I} m_i = |A|$.

For each $i$ in $I$, we want a monotonically nondecreasing sequence $n_{i,1} \leq n_{i,2} \leq \cdots \leq n_{i,m_i}$. We make the change of variables \begin{align*} d_{i,1} &= n_{i,1} \text{,} \\ d_{i,2} &= n_{i,2} - n_{i,1} \text{,} \\ &\vdots \\ d_{i,j} &= n_{i,j} - n_{i,j-1} & (2 \leq j \leq m_i) \text{,} \\ &\vdots \\ d_{i,m_i} &= n_{i,m_i} - n_{i,m_i-1} \text{.} \end{align*} Then the monotonically nondecreasing condition on the $(n_{i,j})_j$ becomes $d_{i,1} \geq 1$ and $d_{i,j} \geq 0$ for $1 \leq j \leq m_i$. Observe that \begin{align*} \sum_{j=1}^{m_i} n_{i,j} &= (d_{i,1}) + (d_{i,1} + d_{i,2}) + \cdots + (d_{i,1} + d_{i,2} + \cdots + d_{i,m_i}) \\ &= \sum_{j=1}^{m_i} (m_i - j +1) d_{i,j} \end{align*}

Then $D(n|A)$ is the number of ways of choosing all these $d_{i,j}$ such that \begin{align*} n &= \sum_{i \in I} b_i \sum_{j =1}^{m_i} n_{i,j} \\ &= \sum_{i \in I} b_i \sum_{j=1}^{m_i} (m_i - j +1) d_{i,j} \\ &= \sum_{i \in I} \left( b_i m_i d_{i,1} + \sum_{j=2}^{m_i} b_i (m_i - j +1) d_{i,j} \right) \text{,} \\ d_{i,1} &\geq 1 \qquad (i \in I) & \text{, and } \\ d_{i,j} &\geq 0 \qquad (i \in I, 2 \leq j \leq m_i) \text{.} \end{align*}

The generating function for $D$ is then $$ \prod_{i \in I} \left( \frac{x^{b_i m_i}}{1-x^{b_i m_i}} \prod_{j = 2}^{m_i} \frac{1}{1-x^{b_i(m_i - j +1)}} \right) \text{.} $$

Examples:

\begin{align*} \mathrm{gf}(D(n|\{1,2\})) &= x^3 + x^4 + 2 x^5 + 2 x^6 + 3 x^7 + 3 x^8 + 4 x^9 + 4 x^{10} + \cdots \text{,} \\ \mathrm{gf}(D(n|\{1,2,2\})) &= x^5 + x^6 + 2 x^7 + 2 x^8 + 4 x^9 + 4 x^{10} + 6 x^{11} + 6 x^{12} + 9 x^{13} \\ &\qquad + 9 x^{14} + 12 x^{15} + 12 x^{16} + 16 x^{17} + 16 x^{18} + 20 x^{19} + 20 x^{20} + \cdots \text{, and} \\ \mathrm{gf}(D(n|\{1,1,1\})) &= x^3 + x^4 + 2 x^5 + 3 x^6 + 4 x^7 + 5 x^8 + 7 x^9 + 8 x^{10} + \cdots \text{.} \end{align*}

Continuing:

We can simplify the gf a bit. \begin{align*} \prod_{i \in I} \left( \frac{x^{b_i m_i}}{1-x^{b_i m_i}} \prod_{j = 2}^{m_i} \frac{1}{1-x^{b_i(m_i - j +1)}} \right) &= \prod_{i \in I} \frac{x^{b_i m_i}}{1-x^{b_i m_i}} \frac{1}{\prod_{j = 2}^{m_i}1-x^{b_i(m_i - j +1)}} \\ &= \prod_{i \in I} \frac{x^{b_i m_i}}{\prod_{j = 1}^{m_i}1-x^{b_i(m_i - j +1)}} \\ &= \prod_{i \in I} \prod_{j = 1}^{m_i} \frac{x^{b_i}}{1-x^{b_i(m_i - j +1)}} \text{.} \end{align*}