Is there any known formula for the number of compositions of an integer k (partitions with considering the order of the parts) of length m (exactly m parts) where the parts do not exceed a given integer n? Without limitation of the parts there is, of course, a well-known formula (binomial k-1 over m-1). Introducing the limitation I worked out a formula but I don´t know whether it´s already published anywhere ...
3 Answers
If I understand well, you consider the number $a(k,n,m)$ of multi-indices $a=(a_1,\dots,a_m)\in\{1,\dots,n\}^m$ with weight $\sum_{i=1}^m a_i=k$. This is therefore the coefficient of $x^k$ in $$\left (\sum _ {j=1}^n x^j \right)^m = x^m(1-x^n)^m (1-x)^{-m}\, .$$ Since the above generating function is the product of functions with elementary power series expansion, a formula for $a(k,n,m)$ is available as a convolution of binomial coefficients. Is this what you mean? This is certainly in any text on the subject .
-
1$\begingroup$ All right, this is the right number. Thank you very much! In my deduction of the formula I avoid power series and generating functions. But this is a nice approach, too. As I use merely geometrical and combinatorial arguments it might be interesting to publish my treatise nevertheless. (I´m going to do so.) $\endgroup$– FinkAug 16, 2012 at 20:37
-
$\begingroup$ @Fink: Good luck, but there are many well-known derivations and it seems likely that you have rediscovered one. $\endgroup$ Aug 16, 2012 at 20:41
-
$\begingroup$ O.k. But why do computer algebra systems (like Maple, MuPAD) need such a long time to calculate the number? Obviously they use recursions and not an explicit formula (for example the command combinat::compositions::count(38,Length=11,MaxPart=6) needs more than 2 hours to calculate the number in question = 25090131). $\endgroup$– FinkAug 17, 2012 at 7:33
-
$\begingroup$ Then that function is poorly implemented. Even a brute-force construction of the list shouldn't take anywhere close to that long. The inclusion-exclusion formula from the first combinatorics class I took is a single summation (in Mathematica, a[k_, n_, m_] := Sum[(-1)^i Binomial[k - 1 - i n, m - 1] Binomial[m, i], {i, 0, Floor[(k - m)/n]}]) and computes it almost instantly, so the Timing function returned a time of $0$. $a[380000,6000,1100]$ took about $1/60$ of a second. $\endgroup$ Aug 17, 2012 at 15:30
-
$\begingroup$ First I apologize for my bad spelling style. E.g. correct is: to take a long time, not: to need ... I noticed the mistake shortly after having mailed the text. Concerning the topic: Now I´m convinced. Thank you very much! By the way the formula (Sum(-1)^i...) mentioned in your answer is (not surprisingly) the one which I found out after many hours of mathematical work. My derivation is, indeed, based on inclusion-exclusion and geometrical analogies. But before setting to work we (a student an I) had started an extensive search for a solution of our problem (literature/web) without result ... $\endgroup$– FinkAug 18, 2012 at 12:47
Heubach and Mansour's Combinatorics of Compositions and Words (CRC 2010) call these "limited" in an exercise (copied below), although I have not found that terminology elsewhere. Part 2 suggests there is a "simple" formula for what you want.
p85, Exercise 3.12
A composition $\sigma = \sigma_1 \cdots \sigma_m$ of $n$ with $m$ parts is said to be limited if $1 \leq \sigma_i \leq n_i$ for all $i = 1, 2, \ldots, n$. [[I think that should be $1, 2, \ldots m$.]]
(1) Derive a formula for the generating function for the number of limited compositions of $n$.
(2) Using Part (1), obtain a simple formula for the case $n_i = k$ for all $i$.
(3) Prove that the number of limited compositions of $n$ is given by $F_{n+1}$ [[Fibonacci]] when $n_i = 2$ for all $i$.
I wanted more room to follow up on Douglas' comment than a comment would allow.
Douglas, I believe you're right, that everything comes down to essentially Pietro's generating function and the summation you gave in a comment there. Let me just add some other names used for the numbers that answer Fink's original question.
For maximum part $k = 2$, as in the Heubach & Mansour exercise part (3) above, there are $F_{n+1}$ (Fibonacci) limited compositions of $n$. The number with $m$ parts is $\binom{m}{n-m}$ (there are $n-m$ 2's and $2m-n$ 1's). The connection between these binomial coefficients and the Fibonacci number is often expressed as sums of diagonal entries in Pascal's triangle; proving the identity in terms of limited compositions is the basis of Benjamin & Quinn's Proofs that Really Count (MAA 2003, Identity 4).
For maximum part $k = 3$, Fibonacci numbers are replaced by "tribonacci" numbers (recurrence $a_n = a_{n-1}+a_{n-2}+a_{n-3}$) and binomial coefficients are replaced by trinomial coefficients, so not Pascal's triangle of coefficients of $(1+x)^n$ but coefficients of $(1+x+x^2)^n$, studied by Euler (see http://arXiv.org/abs/math.HO/0505425). For $k = 4$ the total number of limited compositions are given by "tetranacci" numbers (OEIS http://oeis.org/A000078) and the number with $m$ parts is given by "quadronomial" coefficients (http://oeis.org/A008287). A comment for that integer sequence describes the general result:
In general, the entry $(n,k)$ of the ($\ell$+1)-nomial triangle gives the number of compositions of $k$ into $n$ parts $p$, each part $0 \leq p \leq \ell$. [Steffen Eger, Jun 18 2011]
-
$\begingroup$ Yes, inclusion-exclusion, or using the binomial theorem on Pietro Majer's answer, gives a single summation, which I gave in the comments. This is standard. I don't think you can do better. $\endgroup$ Sep 2, 2012 at 8:03
Here's a fast python implementation of the a(k,n,m) function you described. You can use it to check your answers as I noticed some incorrect answers in the posts above.
def roundup_pow2(x):
while x&(x-1):
x = (x|(x>>1))+1
return max(x,1)
def to_long(x):
return long(rint(x))
def poly_pow(a,b):
n = len(a) * b - b + 1
nr = roundup_pow2(n)
a += [0]*(nr-len(a))
u = fft(a)
w = ifft(pow(u,b))[:n].real
return map(to_long,w)
def a(k,n,m):
l = poly_pow([1]*n,m)
return l[k]