Counting Partitions of $k$ into $j$ distinct parts, with sizes restricted by a sequence.

Question

This question has come up in my research, but since I usually do not do combinatorics, I am struggling to find out any information regarding these sequences of numbers.

Let $L_n = L_1, L_2\dots$ be a sequence of non-negative integers. Suppose you go into a store which has $L_1$ many distinct items which each cost 1 dollar, $L_2$ many distinct items each costing 2 dollars, and so on... I want to count $p(\{L\};k,j)$ which is the number of ways to buy $j$ items with $k$ dollars. The case where there is an $L_0 > 0$ is also of interest (in the story, it would mean that the store has a few items that are free)

If the sequence $L_n$ is identically 1, then $p(\{L\};k,j)$ counts the partitions of $k$ into $j$ distinct parts for example.

Surely these sequences have been named and studied already, but I don't know what they are called. If there is a nice expression for the generating function $p(x) = \sum_{k = 0}^{\infty} p(\{L\};k,j)x^k$ that is something I am very curious to know as well. It seems like it would be some kind of q-function, maybe?

Answer 1

This question falls under the topic of “integer partitions.” Even the simplest case of $L$ are tricky.

$p(L,j,k)$ is the coefficient of $x^jy^k$ in the expansion of:

$$F_L(x,y)=\prod_{i=0}^{\infty}(1+xy^i)^{L_i}$$ Of course, you could limit the product to $i\leq k.$

If all $L_i=1,$ and we only want $F(1,y)$ (that is, we want to know the total number of purchases totaling $k,$ ignoring $j,)$ we get a coefficient $q(k)$ of $y^k$ satisfying:

$$ q(k) = a_k + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k-15) − q(k − 22) − \dots$$ where $a_k=(-1)^m$ when $k=3m^2-m$ and zero otherwise for some $m$ and $1,2,5,7,12,15,22,\dots$ are the pentagonal numbers $m(3m-1)/2$ for $m=1,-1,2,-2,\dots.$ See the section titled “Odd Parts and Distinct Parts” here.

---

It seems unlikely that there is a good general closed form for these coefficients, nor the power series coefficient $p_{L,j}(y)$ of $x^j.$ But there is a tantalizing feature of the $p_{L,i}$ for "nice" $L.$

We will say that $L$ is cyclotomic each if $p_{L,j}(y)$ is a rational function of $y$ with a denominator that only has roots of unity as factors.

We can show:

• If $L$ is non-zero for only finitely many integers, then $L$ is cyclomatic.
• If $L$ is cyclotomic, then so is $\Sigma L,$ where $\Sigma L_n=\sum_{i=0}^{n} L_i.$
• If $L,M$ are two cyclotomic seequences, then so is $L+M.$
• If $L_i=(i)$ where $f$ is a polynomial with non-negative integer coefficients, then $L$ is cyclotomic.
• If $L^1,\dots,L^p$ are $p$ cyclotomic sequences, then so is $L$ defined as $$L^1_1,L^2_1,\dots,L^p_1, L^1_2,\dots.$$ Basically, interleaving such sequences yields a cyclotomic sequence.

It seems highly unlikely this is true for all $L,$ but it is certainly true for a lot of nice $L.$