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

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

• Have you tried ignoring the semimonotonicity condition while putting together your product of elementwise generating functions, then dividing out the overcounts at the end? – Eric Towers Aug 27 '17 at 20:29
• Why wouldn't you divide out the coefficient you extract by $n_i!$ where the $n_i$ are the repetition counts in the multiset $A$, rather than trying to do this with the gf? – Eric Towers Aug 27 '17 at 20:50

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*}

• @d.y : I'd rather say $B = \{(1,\ell)\}$ so that $B$ is a set of ordered pairs $(b_i, m_i)$ (with distinct $b_i$s). The gf for this $B$ is exactly the one given and is the same as the one you write. The given gf is a character-by-character translation of the last sum in the display above it. – Eric Towers Aug 28 '17 at 14:41
• @d.y : I can't right now. Have to get back to work. I'll check in in several hours. – Eric Towers Aug 28 '17 at 14:45