most recent 30 from http://mathoverflow.net 2013-06-19T08:06:53Z http://mathoverflow.net/feeds/question/104826 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104826/explicit-formula-for-the-number-of-compositions-with-m-strictly-positive-parts-bo Fink 2012-08-16T11:57:47Z 2012-09-02T14:46:58Z

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

http://mathoverflow.net/questions/104826/explicit-formula-for-the-number-of-compositions-with-m-strictly-positive-parts-bo/104831#104831 Pietro Majer 2012-08-16T13:39:57Z 2012-08-16T14:53:14Z

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

http://mathoverflow.net/questions/104826/explicit-formula-for-the-number-of-compositions-with-m-strictly-positive-parts-bo/106161#106161 Brian Hopkins 2012-09-02T05:27:03Z 2012-09-02T14:46:58Z

<p>Heubach and Mansour's <em>Combinatorics of Compositions and Words</em> (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.</p> <p>p85, Exercise 3.12</p> <p>A composition $\sigma = \sigma_1 \cdots \sigma_m$ of $n$ with $m$ parts is said to be <em>limited</em> if $1 \leq \sigma_i \leq n_i$ for all $i = 1, 2, \ldots, n$. [[I think that should be $1, 2, \ldots m$.]]</p> <p>(1) Derive a formula for the generating function for the number of limited compositions of $n$.</p> <p>(2) Using Part (1), obtain a simple formula for the case $n_i = k$ for all $i$.</p> <p>(3) Prove that the number of limited compositions of $n$ is given by $F_{n+1}$ [[Fibonacci]] when $n_i = 2$ for all $i$.</p> <hr> <p>I wanted more room to follow up on Douglas' comment than a comment would allow.</p> <p>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.</p> <p>For maximum part $k = 2$, as in the Heubach &amp; 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 &amp; Quinn's <em>Proofs that Really Count</em> (MAA 2003, Identity 4).</p> <p>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 <a href="http://arXiv.org/abs/math.HO/0505425" rel="nofollow">http://arXiv.org/abs/math.HO/0505425</a>). For $k = 4$ the total number of limited compositions are given by "tetranacci" numbers (OEIS <a href="http://oeis.org/A000078" rel="nofollow">http://oeis.org/A000078</a>) 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:</p> <blockquote> <p>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] </p> </blockquote>