|
|
A124323
|
|
Triangle read by rows: T(n,k) is the number of partitions of an n-set having k singleton blocks (0<=k<=n).
|
|
20
|
|
|
1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 4, 4, 6, 0, 1, 11, 20, 10, 10, 0, 1, 41, 66, 60, 20, 15, 0, 1, 162, 287, 231, 140, 35, 21, 0, 1, 715, 1296, 1148, 616, 280, 56, 28, 0, 1, 3425, 6435, 5832, 3444, 1386, 504, 84, 36, 0, 1, 17722, 34250, 32175, 19440, 8610, 2772, 840, 120, 45, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Row sums are the Bell numbers (A000110). T(n,0)=A000296(n). T(n,k) = binomial(n,k)*T(n-k,0). Sum(k*T(n,k),k=0..n) = A052889(n) = n*B(n-1), where B(q) are the Bell numbers (A000110).
Exponential Riordan array [exp(exp(x)-1-x),x]. - Paul Barry, Apr 23 2009
Sum_{k=0..n} T(n,k)*2^k = A000110(n+1) is the number of binary relations on an n-set that are both symmetric and transitive. - Geoffrey Critzer, Jul 25 2014
Also the number of set partitions of {1, ..., n} with k cyclical adjacencies (successive elements in the same block, where 1 is a successor of n). Unlike A250104, we count {{1}} as having 1 cyclical adjacency. - Gus Wiseman, Feb 13 2019
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = binomial(n,k)*[(-1)^(n-k)+sum((-1)^(j-1)*B(n-k-j), j=1..n-k)], where B(q) are the Bell numbers (A000110).
E.g.f.: G(t,z) = exp(exp(z)-1+(t-1)*z).
G.f.: 1/(1-xy-x^2/(1-xy-x-2x^2/(1-xy-2x-3x^2/(1-xy-3x-4x^2/(1-... (continued fraction). - Paul Barry, Apr 23 2009
|
|
EXAMPLE
|
T(4,2)=6 because we have 12|3|4, 13|2|4, 14|2|3, 1|23|4, 1|24|3 and 1|2|34 (if we take {1,2,3,4} as our 4-set).
Triangle starts:
1
0 1
1 0 1
1 3 0 1
4 4 6 0 1
11 20 10 10 0 1
41 66 60 20 15 0 1
162 287 231 140 35 21 0 1
715 1296 1148 616 280 56 28 0 1
3425 6435 5832 3444 1386 504 84 36 0 1
Row n = 5 counts the following set partitions by number of singletons:
{{1234}} {{1}{234}} {{1}{2}{34}} {{1}{2}{3}{4}}
{{12}{34}} {{123}{4}} {{1}{23}{4}}
{{13}{24}} {{124}{3}} {{12}{3}{4}}
{{14}{23}} {{134}{2}} {{1}{24}{3}}
{{13}{2}{4}}
{{14}{2}{3}}
... and the following set partitions by number of cyclical adjacencies:
{{13}{24}} {{1}{2}{34}} {{1}{234}} {{1234}}
{{1}{24}{3}} {{1}{23}{4}} {{12}{34}}
{{13}{2}{4}} {{12}{3}{4}} {{123}{4}}
{{1}{2}{3}{4}} {{14}{2}{3}} {{124}{3}}
{{134}{2}}
{{14}{23}}
(End)
Production matrix is
0, 1,
1, 0, 1,
1, 2, 0, 1,
1, 3, 3, 0, 1,
1, 4, 6, 4, 0, 1,
1, 5, 10, 10, 5, 0, 1,
1, 6, 15, 20, 15, 6, 0, 1,
1, 7, 21, 35, 35, 21, 7, 0, 1,
1, 8, 28, 56, 70, 56, 28, 8, 0, 1 (End)
|
|
MAPLE
|
G:=exp(exp(z)-1+(t-1)*z): Gser:=simplify(series(G, z=0, 14)): for n from 0 to 11 do P[n]:=sort(n!*coeff(Gser, z, n)) od: for n from 0 to 11 do seq(coeff(P[n], t, k), k=0..n) od; # yields sequence in triangular form
end proc:
|
|
MATHEMATICA
|
Flatten[CoefficientList[Range[0, 10]! CoefficientList[Series[Exp[x y] Exp[Exp[x] - x - 1], {x, 0, 10}], x], y]] (* Geoffrey Critzer, Nov 24 2011 *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Table[Length[Select[sps[Range[n]], Count[#, {_}]==k&]], {n, 0, 9}, {k, 0, n}] (* Gus Wiseman, Feb 13 2019 *)
|
|
CROSSREFS
|
A250104 is an essentially identical triangle, differing only in row 1.
Cf. A000126, A001610, A032032, A052841, A066982, A080107, A169985, A187784, A324011, A324014, A324015.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|