login
Triangle read by rows: T(n,k) gives the number of set partitions of {1,...,n} with maximum block length k.
33

%I #72 Feb 16 2022 07:40:28

%S 1,1,1,1,3,1,1,9,4,1,1,25,20,5,1,1,75,90,30,6,1,1,231,420,175,42,7,1,

%T 1,763,2016,1015,280,56,8,1,1,2619,10024,6111,1890,420,72,9,1,1,9495,

%U 51640,38010,12978,3150,600,90,10,1,1,35695,276980,244035,91938,24024,4950,825,110,11,1

%N Triangle read by rows: T(n,k) gives the number of set partitions of {1,...,n} with maximum block length k.

%C Row sums are A000110 (Bell numbers). Second column is A001189 (Degree n permutations of order exactly 2).

%C From _Peter Luschny_, Mar 09 2009: (Start)

%C Partition product of Product_{j=0..n-1} ((k + 1)*j - 1) and n! at k = -1, summed over parts with equal biggest part (see the Luschny link).

%C Underlying partition triangle is A036040.

%C Same partition product with length statistic is A008277.

%C Diagonal a(A000217) = A000012.

%C Row sum is A000110. (End)

%C From _Gary W. Adamson_, Feb 24 2011: (Start)

%C Construct an array in which the n-th row is the partition function G(n,k), where G(n,1),...,G(n,6) = A000012, A000085, A001680, A001681, A110038, A148092, with the first few rows

%C 1, 1, 1, 1, 1, 1, 1, ... = A000012

%C 1, 2, 4, 10, 26, 76, 232, ... = A000085

%C 1, 2, 5, 14, 46, 166, 652, ... = A001680

%C 1, 2, 5, 15, 51, 196, 827, ... = A001681

%C 1, 2 5 15 52 202 869, ... = A110038

%C 1, 2, 5 15 52 203 876, ... = A148092

%C ...

%C Rows tend to A000110, the Bell numbers. Taking finite differences from the top, then reorienting, we obtain triangle A080510.

%C The n-th row of the array is the eigensequence of an infinite lower triangular matrix with n diagonals of Pascal's triangle starting from the right and the rest zeros. (End)

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

%H Peter Luschny, <a href="http://www.luschny.de/math/seq/CountingWithPartitions.html"> Counting with Partitions</a>.

%H Peter Luschny, <a href="http://www.luschny.de/math/seq/stirling2partitions.html"> Generalized Stirling_2 Triangles</a>.

%H J. Riordan, <a href="/A229223/a229223.pdf">Letter, 11/23/1970</a>. See second page of letter.

%F E.g.f. for k-th column: exp(exp(x)*GAMMA(k, x)/(k-1)!-1)*(exp(x^k/k!)-1). - _Vladeta Jovovic_, Feb 04 2005

%F From _Peter Luschny_, Mar 09 2009: (Start)

%F T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n.

%F T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,...,a_n such that

%F 1*a_1 + 2*a_2 + ... + n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*...*a_n!),

%F f^a = (f_1/1!)^a_1*...*(f_n/n!)^a_n and f_n = Product_{j=0..n-1} (-1) = (-1)^n. (End)

%F From _Ludovic Schwob_, Jan 15 2022: (Start)

%F T(2n,n) = C(2n,n)*(A000110(n)-1/2) for n>0.

%F T(n,m) = C(n,m)*A000110(n-m) for 2m > n > 0. (End)

%e T(4,3) = 4 since there are 4 set partitions with longest block of length 3: {{1},{2,3,4}}, {{1,3,4},{2}}, {{1,2,3},{4}} and {{1,2,4},{3}}.

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 3, 1;

%e 1, 9, 4, 1;

%e 1, 25, 20, 5, 1;

%e 1, 75, 90, 30, 6, 1;

%e 1, 231, 420, 175, 42, 7, 1;

%e 1, 763, 2016, 1015, 280, 56, 8, 1;

%e 1, 2619, 10024, 6111, 1890, 420, 72, 9, 1;

%e ...

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add(b(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))

%p end:

%p T:= (n, k)-> b(n, k) -b(n, k-1):

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

%t << DiscreteMath`NewCombinatorica`; Table[Length/@Split[Sort[Max[Length/@# ]&/@SetPartitions[n]]], {n, 12}]

%t (* Second program: *)

%t b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[b[n-i*j, i-1]*n!/i!^j/(n-i*j)!/j!, {j, 0, n/i}]]]; T[n_, k_] := b[n, k]-b[n, k-1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Feb 25 2014, after _Alois P. Heinz_ *)

%Y Cf. A080107, A080337, A008277, A178979, A276922, A327884.

%Y Cf. A157396, A157397, A157398, A157399, A157400, A157401, A157402, A157403, A157404, A157405. - _Peter Luschny_, Mar 09 2009

%Y Cf. A000012, A000085, A001680, A001681, A110038, A148092. - _Gary W. Adamson_, Feb 24 2011

%Y Columns k=1..10 give: A000012 (for n>0), A001189, A229245, A229246, A229247, A229248, A229249, A229250, A229251, A229252. - _Alois P. Heinz_, Sep 17 2013

%Y T(2n,n) gives A276961.

%Y Take differences along rows of A229223. - _N. J. A. Sloane_, Jan 10 2018

%K nonn,tabl

%O 1,5

%A _Wouter Meeussen_, Mar 22 2003