1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Have you tried ignoring the semimonotonicity condition while putting together your product of elementwise generating functions, then dividing out the overcounts at the end? $\endgroup$ – Eric Towers Aug 27 '17 at 20:29
  • $\begingroup$ 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? $\endgroup$ – Eric Towers Aug 27 '17 at 20:50
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Eric Towers Aug 28 '17 at 14:41
  • $\begingroup$ @d.y : I can't right now. Have to get back to work. I'll check in in several hours. $\endgroup$ – Eric Towers Aug 28 '17 at 14:45

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.