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

Author

Henry Bottomley, Oct 22 2002

Keywords

• nice
• nonn

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..100
• Index entries for sequences related to compositions

Crossrefs

Cf. A077042, A077046, A077047, A077048, A362967.

Programs

Maple

b:= proc(n, h, t) option remember;
      `if`(t*h 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 *)

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

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.

From Emanuele Munarini, Jul 15 2016: (Start)

a(n) = [x^binomial(n,2)](1+x+x^2+...+x^(n-1))^n.

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. (End)