A080510 Triangle read by rows: T(n,k) gives the number of set partitions of {1,...,n} with maximum block length k.
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, 1, 763, 2016, 1015, 280, 56, 8, 1, 1, 2619, 10024, 6111, 1890, 420, 72, 9, 1, 1, 9495, 51640, 38010, 12978, 3150, 600, 90, 10, 1, 1, 35695, 276980, 244035, 91938, 24024, 4950, 825, 110, 11, 1
Offset: 1
Examples
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}}. Triangle begins: 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; 1, 763, 2016, 1015, 280, 56, 8, 1; 1, 2619, 10024, 6111, 1890, 420, 72, 9, 1; ...
Links
- Alois P. Heinz, Rows n = 1..141, flattened
- Peter Luschny, Counting with Partitions.
- Peter Luschny, Generalized Stirling_2 Triangles.
- J. Riordan, Letter, 11/23/1970. See second page of letter.
Crossrefs
Cf. A157396, A157397, A157398, A157399, A157400, A157401, A157402, A157403, A157404, A157405. - Peter Luschny, Mar 09 2009
Columns k=1..10 give: A000012 (for n>0), A001189, A229245, A229246, A229247, A229248, A229249, A229250, A229251, A229252. - Alois P. Heinz, Sep 17 2013
T(2n,n) gives A276961.
Take differences along rows of A229223. - N. J. A. Sloane, Jan 10 2018
Programs
-
Maple
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i))) end: T:= (n, k)-> b(n, k) -b(n, k-1): seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Apr 20 2012
-
Mathematica
<< DiscreteMath`NewCombinatorica`; Table[Length/@Split[Sort[Max[Length/@# ]&/@SetPartitions[n]]], {n, 12}] (* Second program: *) 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 *)
Formula
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
From Peter Luschny, Mar 09 2009: (Start)
T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n.
T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,...,a_n such that
1*a_1 + 2*a_2 + ... + n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*...*a_n!),
f^a = (f_1/1!)^a_1*...*(f_n/n!)^a_n and f_n = Product_{j=0..n-1} (-1) = (-1)^n. (End)
From Ludovic Schwob, Jan 15 2022: (Start)
T(2n,n) = C(2n,n)*(A000110(n)-1/2) for n>0.
T(n,m) = C(n,m)*A000110(n-m) for 2m > n > 0. (End)
Comments