A077045 Doubly restricted composition numbers: number of compositions of 1+2+3+...+n = n(n+1)/2 into exactly n positive integers each no more than n.

1, 1, 2, 7, 44, 381, 4332, 60691, 1012664, 19610233, 432457640, 10701243741, 293661065788, 8851373201919, 290711372717976, 10334165623697259, 395320344293410544, 16192709833199300337, 707125993042984343136, 32795665902734099555845, 1609908874238209683872480

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..100

Index entries for sequences related to compositions

Formula

a(n) = A077042(n, n). Roughly n^(n-3/2)*sqrt(6/Pi) by the central limit theorem and something like n^n*sqrt(6/(Pi*(n^3+0.3*n^2-0.91*n+0.3)) seems to be even closer.

a(n) = [x^binomial(n,2)](1+x+x^2+...+x^(n-1))^n. - Emanuele Munarini, Jul 15 2016

a(n) = Sum_{k = 0..floor((n-1)/2)} binomial(n,k)*binomial(n + binomial(n,2) - n*k - 1, n-1)*(-1)^k for n >=1. - Emanuele Munarini, Jul 15 2016

Example

a(3) = 7 since the compositions of 1+2+3=6 into exactly 3 positive integers each no more than 3 are: 1+2+3, 1+3+2, 2+1+3, 2+2+2, 2+3+1, 3+1+2, 3+2+1.

Maple

b:= proc(n, h, t) option remember;
      `if`(t*h<n, 0, `if`(n=0, 1,
       add(b(n-j, min(h, n-j), t-1), j=0..min(n, h))))
    end:
a:= n-> b(n*(n-1)/2, n-1, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 10 2012

Mathematica

f[n_] := Union[ CoefficientList[ Expand[ Sum[x^j, {j, n}]^n], x]][[-1]]; Join[{1}, Array[f, 18]] (* Robert G. Wilson v, Apr 06 2012 *)
f[n_] := Block[{ip = IntegerPartitions[n (n + 1)/2, {n}, Range@ n], k = 1, s = 0}, len = Length[ip] + 1; While[k < len, s = s + Length@ Permutations[ ip[[k]]]; k++]; s]; Array[f, 11, 0] (* CAUTION, very slow and requires a lot of resources beyond 10, Robert G. Wilson v, Apr 09 2012 *)
b[n_, h_, t_] := b[n, h, t] = If[t*h < n, 0, If[n == 0, 1, Sum[b[n-j, Min[h, n-j], t-1], {j, 0, Min[n, h]}]]]; a[n_] := b[n*(n-1)/2, n-1, n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Sep 16 2013, after Alois P. Heinz *)
Table[Sum[Binomial[n, k] Binomial[n + Binomial[n, 2] - n k - 1, n - 1] (-1)^k, {k, 0, Floor[(n-1)/2] + If[n == 0, 1, 0]}], {n, 0, 100}] (* Emanuele Munarini, Jul 15 2016 *)

Prog

(Maxima) makelist(sum(binomial(n, k)*binomial(n+binomial(n, 2)-n*k-1, n-1)*(-1)^k, k, 0, floor((n-1)/2)), n, 1, 12); (for n >= 1) /* Emanuele Munarini, Jul 15 2016 */
(PARI) a(n) = if(n<1, n==0, sum(k=0, (n-1)\2, binomial(n, k)*binomial(n + binomial(n, 2) - n*k - 1, n-1)*(-1)^k)); \\ Andrew Howroyd, Feb 27 2018

Crossrefs

Cf. A077042, A077046, A077047, A077048.

Sequence in context: A145073 A111561 A000155 * A178012 A194018 A196793

Adjacent sequences: A077042 A077043 A077044 * A077046 A077047 A077048

Keyword

nice,nonn

Author

Henry Bottomley, Oct 22 2002

Status

approved