login
Triangle T(n,k) = number of partitions of n into k distinct parts, 1 <= k <= n.
17

%I #33 Mar 06 2020 01:01:46

%S 1,1,0,1,1,0,1,1,0,0,1,2,0,0,0,1,2,1,0,0,0,1,3,1,0,0,0,0,1,3,2,0,0,0,

%T 0,0,1,4,3,0,0,0,0,0,0,1,4,4,1,0,0,0,0,0,0,1,5,5,1,0,0,0,0,0,0,0,1,5,

%U 7,2,0,0,0,0,0,0,0,0,1,6,8,3,0,0,0,0,0,0,0,0,0,1,6,10,5,0,0,0,0,0,0,0,0,0

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

%C Also number of partitions of n-k(k+1)/2 into at most k parts (not necessarily distinct).

%C A025147(n) = Sum_{k=2..floor((n+2)/2)} a(n-k+1, k-1). - _Reinhard Zumkeller_, Nov 04 2007

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 831.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 94, 96 and 307.

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 219.

%D D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.2, p. 493.

%H Alois P. Heinz, <a href="/A060016/b060016.txt">Rows n = 1..141, flattened</a>

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

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

%F G.f.: Sum_{n>=0} z^n * q^((n^2+n)/2) / Product_{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 A000009; cf. to g.f. for A072574. - _Joerg Arndt_, Oct 20 2012

%e Triangle starts

%e [ 1] 1,

%e [ 2] 1, 0,

%e [ 3] 1, 1, 0,

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

%e [ 5] 1, 2, 0, 0, 0,

%e [ 6] 1, 2, 1, 0, 0, 0,

%e [ 7] 1, 3, 1, 0, 0, 0, 0,

%e [ 8] 1, 3, 2, 0, 0, 0, 0, 0,

%e [ 9] 1, 4, 3, 0, 0, 0, 0, 0, 0,

%e [10] 1, 4, 4, 1, 0, 0, 0, 0, 0, 0,

%e [11] 1, 5, 5, 1, 0, 0, 0, 0, 0, 0, 0,

%e [12] 1, 5, 7, 2, 0, 0, 0, 0, 0, 0, 0, 0,

%e [13] 1, 6, 8, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0,

%e [14] 1, 6, 10, 5, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e T(8,3)=2 since 8 can be written in 2 ways as the sum of 3 distinct positive integers: 5+2+1 and 4+3+1.

%p b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)

%p -> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0)))

%p end:

%p T:= proc(n) local l; l:= subsop(1=NULL, b(n, n));

%p l[], 0$(n-nops(l))

%p end:

%p seq(T(n), n=1..20); # _Alois P. Heinz_, Dec 12 2012

%t Flatten[Table[Length[Select[IntegerPartitions[n,{k}],Max[Transpose[ Tally[#]][[2]]]==1&]],{n,20},{k,n}]] (* _Harvey P. Dale_, Feb 27 2012 *)

%t T[_, 1] = 1; T[n_, k_] /; 1<k<n := T[n, k] = T[n-k, k]+T[n-k, k-1]; T[_, _] = 0; Table[T[n, k], {n, 1, 20}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Oct 26 2015 *)

%o (PARI)

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

%o gf=sum(n=0,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, A004526, A001399, A001400, A001401, etc. Cf. A000009 (row sums), A008289 (without zeros), A030699 (row maximum), A008284 (partition triangle including duplications).

%Y See A008289 for another version.

%K nonn,tabl,nice,easy

%O 1,12

%A _N. J. A. Sloane_

%E More terms, recurrence, etc. from _Henry Bottomley_, Mar 26 2001