Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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 .

share|improve this answer
1  
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.) –  Fink Aug 16 '12 at 20:37
    
@Fink: Good luck, but there are many well-known derivations and it seems likely that you have rediscovered one. –  Douglas Zare Aug 16 '12 at 20:41
    
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). –  Fink Aug 17 '12 at 7:33
    
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. –  Douglas Zare Aug 17 '12 at 15:30
    
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 ... –  Fink Aug 18 '12 at 12:47
show 1 more comment

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]

share|improve this answer
    
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. –  Douglas Zare Sep 2 '12 at 8:03
add comment

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]
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.