login
Triangle T(n,k) of number of compositions (ordered partitions) of n into exactly k distinct parts, 1<=k<=n.
19

%I #29 Oct 18 2022 13:32:45

%S 1,1,0,1,2,0,1,2,0,0,1,4,0,0,0,1,4,6,0,0,0,1,6,6,0,0,0,0,1,6,12,0,0,0,

%T 0,0,1,8,18,0,0,0,0,0,0,1,8,24,24,0,0,0,0,0,0,1,10,30,24,0,0,0,0,0,0,

%U 0,1,10,42,48,0,0,0,0,0,0,0,0,1,12,48,72,0,0,0,0,0,0,0,0,0,1,12,60,120,0

%N Triangle T(n,k) of number of compositions (ordered partitions) of n into exactly k distinct parts, 1<=k<=n.

%C If terms in the compositions did not need to be distinct then the triangle would have values C(n-1,k-1), essentially A007318 offset.

%H Joerg Arndt, <a href="/A072574/b072574.txt">Table of n, a(n) for n = 1..5050</a> (rows 1..100, flattened).

%H B. Richmond and A. Knopfmacher, <a href="http://dx.doi.org/10.1007/BF01827930">Compositions with distinct parts</a>, Aequationes Mathematicae 49 (1995), pp. 86-97.

%H <a href="/index/Com#comp">Index entries for sequences related to compositions</a>

%F T(n, k) = T(n-k, k)+k*T(n-k, k-1) [with T(n, 0)=1 if n=0 and 0 otherwise] = A000142(k)*A060016(n, k).

%F G.f.: sum(n>=0, n! * z^n * q^((n^2+n)/2) / prod(k=1..n, 1-q^k ) ), rows by powers of q, columns by powers of z; includes row 0 (drop term for n=0 for this triangle, see PARI code); setting z=1 gives g.f. for A032020. [_Joerg Arndt_, Oct 20 2012]

%e T(6,2)=4 since 6 can be written as 1+5=2+4=4+2=5+1.

%e Triangle starts (trailing zeros omitted for n>=10):

%e [ 1] 1;

%e [ 2] 1, 0;

%e [ 3] 1, 2, 0;

%e [ 4] 1, 2, 0, 0;

%e [ 5] 1, 4, 0, 0, 0;

%e [ 6] 1, 4, 6, 0, 0, 0;

%e [ 7] 1, 6, 6, 0, 0, 0, 0;

%e [ 8] 1, 6, 12, 0, 0, 0, 0, 0;

%e [ 9] 1, 8, 18, 0, 0, 0, 0, 0, 0;

%e [10] 1, 8, 24, 24, 0, 0, ...;

%e [11] 1, 10, 30, 24, 0, 0, ...;

%e [12] 1, 10, 42, 48, 0, 0, ...;

%e [13] 1, 12, 48, 72, 0, 0, ...;

%e [14] 1, 12, 60, 120, 0, 0, ...;

%e [15] 1, 14, 72, 144, 120, 0, 0, ...;

%e [16] 1, 14, 84, 216, 120, 0, 0, ...;

%e [17] 1, 16, 96, 264, 240, 0, 0, ...;

%e [18] 1, 16, 114, 360, 360, 0, 0, ...;

%e [19] 1, 18, 126, 432, 600, 0, 0, ...;

%e [20] 1, 18, 144, 552, 840, 0, 0, ...;

%e These rows (without the zeros) are shown in the Richmond/Knopfmacher reference.

%e From _Gus Wiseman_, Oct 17 2022: (Start)

%e Column n = 8 counts the following compositions.

%e (8) (1,7) (1,2,5)

%e (2,6) (1,3,4)

%e (3,5) (1,4,3)

%e (5,3) (1,5,2)

%e (6,2) (2,1,5)

%e (7,1) (2,5,1)

%e (3,1,4)

%e (3,4,1)

%e (4,1,3)

%e (4,3,1)

%e (5,1,2)

%e (5,2,1)

%e (End)

%t Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],Length[#]==k&]],{n,0,15},{k,1,n}] (* _Gus Wiseman_, Oct 17 2022 *)

%o (PARI)

%o N=21; q='q+O('q^N);

%o gf=sum(n=0,N, n! * z^n * q^((n^2+n)/2) / prod(k=1,n, 1-q^k ) );

%o /* print triangle: */

%o gf -= 1; /* remove row zero */

%o P=Pol(gf,'q);

%o { for (n=1,N-1,

%o p = Pol(polcoeff(P, n),'z);

%o p += 'z^(n+1); /* preserve trailing zeros */

%o v = Vec(polrecip(p));

%o v = vector(n,k,v[k]); /* trim to size n */

%o print(v);

%o ); }

%o /* _Joerg Arndt_, Oct 20 2012 */

%Y Columns (offset) include A057427 and A052928.

%Y Row sums are A032020.

%Y Cf. A060016, A072576.

%Y A008289 is the version for partitions (zeros removed).

%Y A072575 counts strict compositions by maximum.

%Y A097805 is the non-strict version, or A007318 (zeros removed).

%Y A113704 is the constant instead of strict version.

%Y A216652 is a condensed version (zeros removed).

%Y A336131 counts splittings of partitions with distinct sums.

%Y A336139 counts strict compositions of each part of a strict composition.

%Y Cf. A075900, A097910, A307068, A336127, A336128, A336130, A336132, A336141, A336142, A336342, A336343.

%K nonn,tabl

%O 1,5

%A _Henry Bottomley_, Jun 21 2002