[Math] Restricted partition of integer: strictly k distinct parts from a set

combinatoricsintegers

I am looking for a way to compute/approach a serie of restricted partitions (or compositions) of integers.

I've found the $Q(n,k)$ quantity (OEIS) satisfying the first two of my following constraints :

  • fixed order $k$
  • $k$ distinct parts
  • parts of the partition $\subset [1, \ldots, m]$

In other words, I would like to be able to count the number of the partitions (or directly the compositions) of an integer n in k distinct parts, the parts being taken from the set [1, …, m].

For an order of magnitude, my parameters would vary a lot, i.e. n would be pretty big, from a range between $200$ and $3000$, k between $5$ to $15$ and m between $60$ to $300$. My hope being that my strict contraints limit the numbering process.

I've looked through the OEIS website, MathWorld the work of Henry Bottomley and tried the John d'Errico matlab code with no success until now so here I am.

If someone has an idea or any avenue to explore, I would be eternally grateful!

Supplementary

For example, on Matlab, at a first glance it seems to be able to get me what I want (with no consideration about the computation time) but when I'm running it it gives me partition with repetitive parts despite the max_count at 1.

I have also tried Wolfram, and it seemed very promising -as it was able to compute me very quickly some random "unrestricted" partition of big integer consistent with my parameters-

but despite the functions defined here, the

IntegerPartitions[n,kspec,{s1,s2,…}]

is only running me the unrestricted partition

IntegerPartitions[n]

in WolframAlpha.

**

EDIT :

**

Great thanks N. Shales, really appreciated it!

You get my point and looking at the first coefficients, it seems to work smoothly but I have one doubt about something.

Accordingly to your example,

with $k=5$ and $m=10$

the minimum $n$ would be defined by $\frac{k^2+k}{2}$ as your generating function shows;

and then here would be 15, as the sum of the 5 first naturals from $[1,2,3,4,5, …,10]$.

Reciprocally, the maximum $n$ would be 40 from $[1, …, 6,7,8,9,10]$ and not 65 no?

I was defining this value by $$n_{max}=k \frac{2m-k+1}{2}$$

Moreover, when I am looking at $x^{40}$, the coefficient is 141 and I was expecting 1 -as for me there is only one way to achieve a maximal/minimal $n$ with strictly $k$ distinct parts from a set.

Am I missing something?

Last but not least, for clarity, do you mind to put your Sage code with the parameters?

Anyway, again thank you for your help, it is such a great way to learn here, thanks to people like you.

All the best!

**

EDIT 2 :

**

New question about this.

When you are using this generating function proposed by N.Shales and getting the polynomial expression, by looking at the coefficients, you can observe an obvious symmetry.

Let's look at his example case for instance you have this serie
$$[1, 1, 2, 3, 5, 7, 9, …, 19, 20, 20, 19, …, 9, 7, 5, 3, 2, 1, 1]$$
and when I'm looking at my cases I can make some very basic and intuitive observation based on the odd or even number of elements on those series and the two or one central integer with the biggest number of restricted partitions.

But I was wondering if you have a formal expression of this bell-curve looking like distribution?

Thanks!

Best Answer

The generating function for distinct partitions into $k$ parts using elements from the set $\{1,\ldots,m\}$ is given using the $q$-binomial coefficient

$$\binom{m}{k}_q=\prod_{j=1}^{k}\frac{1-q^{m+1-j}}{1-q^j}\, .$$

The desired generating function is simply:

$$q^{\binom{k+1}{2}}\binom{m}{k}_q=\sum_{n=\binom{k+1}{2}}^{\binom{k+1}{2}+mk}p_{n,k,m}^*q^n\, ,$$

where $p_{n,k,m}^*$ is the number of partitions of $n$ in to $k$ distinct parts with no part greater than $m$.

We can use, for example, the free open source computer algebra system sage to expand

$$q^{\binom{6}{2}}\binom{10}{5}_q $$

which lists, as it's coefficients, partitions into distinct parts with $k=5$ parts and no part greater than $m=10$. Using the sage input:

j=var('j')
f(x)=x^15*product((1-x^(11-j))/(1-x^j),j,1,5)
show(expand(f(x)))

we get output:

$$\begin{align}&x^{40} + x^{39} + 2 \, x^{38} + 3 \, x^{37} + 5 \, x^{36} + 7 \, x^{35} + 9 \, x^{34} + 11 \, x^{33} + 14 \, x^{32} + 16 \, x^{31} + 18 \, x^{30}\\& + 19 \, x^{29} + 20 \, x^{28} + 20 \, x^{27} + 19 \, x^{26} + 18 \, x^{25} + 16 \, x^{24} + 14 \, x^{23} + 11 \, x^{22} + 9 \, x^{21} +\\& 7 \, x^{20} + 5 \, x^{19} + 3 \, x^{18} + 2 \, x^{17} + x^{16} + x^{15}\end{align}$$

Here we have 1 such partition for each of 15 and 16, 2 such partitions of 17, 3 partitions of 18 and so on.

The show command allows us to retrieve the output in $\LaTeX$ format so that, for example, it can be used to illustrate an answer on MSE ;)

By the way: A composition is different from a partition. For a composition the order of it's summands counts, whereas for partitions it doesn't.

Perhaps you already know this, however I am just making it clear for any other readers who may not be aware of the distinction. Of course, since we are counting partitions in to $k$ distinct parts then the number of compositions can be counted by multiplying by $k!$.

As per @GCab's request (see comments) I am posting a download link for more information on $q$-binomial coefficients:

A Course in Enumeration by Martin Aigner (pdf download)

The relevant section is 1.6.

Aigner gives a lucid account of the connection between $q$-binomial coefficients, lattice paths and restricted partitions. He then goes on to link, via a well known bijection, to the restricted partitions into distinct parts (corollary 1.2) talked about here.

Related Question