cp's OEIS Frontend

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.

%I A077045 #62 Apr 13 2025 15:01:45
%S A077045 1,1,2,7,44,381,4332,60691,1012664,19610233,432457640,10701243741,
%T A077045 293661065788,8851373201919,290711372717976,10334165623697259,
%U A077045 395320344293410544,16192709833199300337,707125993042984343136,32795665902734099555845,1609908874238209683872480
%N 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.
%H A077045 Alois P. Heinz, <a href="/A077045/b077045.txt">Table of n, a(n) for n = 0..100</a>
%H A077045 <a href="/index/Com#comp">Index entries for sequences related to compositions</a>
%F A077045 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.
%F A077045 From _Emanuele Munarini_, Jul 15 2016: (Start)
%F A077045 a(n) = [x^binomial(n,2)](1+x+x^2+...+x^(n-1))^n.
%F A077045 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)
%e A077045 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.
%p A077045 b:= proc(n, h, t) option remember;
%p A077045       `if`(t*h<n, 0, `if`(n=0, 1,
%p A077045        add(b(n-j, min(h, n-j), t-1), j=0..min(n, h))))
%p A077045     end:
%p A077045 a:= n-> b(n*(n-1)/2, n-1, n):
%p A077045 seq(a(n), n=0..20);  # _Alois P. Heinz_, Apr 10 2012
%t A077045 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 *)
%t A077045 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 *)
%t A077045 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_ *)
%t A077045 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 *)
%o A077045 (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 */
%o A077045 (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
%Y A077045 Cf. A077042, A077046, A077047, A077048, A362967.
%K A077045 nice,nonn
%O A077045 0,3
%A A077045 _Henry Bottomley_, Oct 22 2002