login
Triangle read by rows: T(n,k) is the number of partitions of an n-set having k singleton blocks (0<=k<=n).
20

%I #38 Sep 17 2024 20:41:12

%S 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,

%T 287,231,140,35,21,0,1,715,1296,1148,616,280,56,28,0,1,3425,6435,5832,

%U 3444,1386,504,84,36,0,1,17722,34250,32175,19440,8610,2772,840,120,45,0,1

%N Triangle read by rows: T(n,k) is the number of partitions of an n-set having k singleton blocks (0<=k<=n).

%C 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).

%C Exponential Riordan array [exp(exp(x)-1-x),x]. - _Paul Barry_, Apr 23 2009

%C 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

%C 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

%H Alois P. Heinz, <a href="/A124323/b124323.txt">Rows n = 0..140, flattened</a>

%H David Callan, <a href="https://arxiv.org/abs/math/0508052">On conjugates for set partitions and integer compositions</a>, arXiv:math/0508052 [math.CO], 2005.

%H T. Mansour, A. O. Munagi, <a href="https://doi.org/10.1016/j.ejc.2014.06.008">Set partitions with circular successions</a>, European Journal of Combinatorics, 42 (2014), 207-216.

%F 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).

%F E.g.f.: G(t,z) = exp(exp(z)-1+(t-1)*z).

%F 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

%e 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).

%e Triangle starts:

%e 1

%e 0 1

%e 1 0 1

%e 1 3 0 1

%e 4 4 6 0 1

%e 11 20 10 10 0 1

%e 41 66 60 20 15 0 1

%e 162 287 231 140 35 21 0 1

%e 715 1296 1148 616 280 56 28 0 1

%e 3425 6435 5832 3444 1386 504 84 36 0 1

%e From _Gus Wiseman_, Feb 13 2019: (Start)

%e Row n = 5 counts the following set partitions by number of singletons:

%e {{1234}} {{1}{234}} {{1}{2}{34}} {{1}{2}{3}{4}}

%e {{12}{34}} {{123}{4}} {{1}{23}{4}}

%e {{13}{24}} {{124}{3}} {{12}{3}{4}}

%e {{14}{23}} {{134}{2}} {{1}{24}{3}}

%e {{13}{2}{4}}

%e {{14}{2}{3}}

%e ... and the following set partitions by number of cyclical adjacencies:

%e {{13}{24}} {{1}{2}{34}} {{1}{234}} {{1234}}

%e {{1}{24}{3}} {{1}{23}{4}} {{12}{34}}

%e {{13}{2}{4}} {{12}{3}{4}} {{123}{4}}

%e {{1}{2}{3}{4}} {{14}{2}{3}} {{124}{3}}

%e {{134}{2}}

%e {{14}{23}}

%e (End)

%e From _Paul Barry_, Apr 23 2009: (Start)

%e Production matrix is

%e 0, 1,

%e 1, 0, 1,

%e 1, 2, 0, 1,

%e 1, 3, 3, 0, 1,

%e 1, 4, 6, 4, 0, 1,

%e 1, 5, 10, 10, 5, 0, 1,

%e 1, 6, 15, 20, 15, 6, 0, 1,

%e 1, 7, 21, 35, 35, 21, 7, 0, 1,

%e 1, 8, 28, 56, 70, 56, 28, 8, 0, 1 (End)

%p 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

%p # Program from _R. J. Mathar_, Jan 22 2015:

%p A124323 := proc(n,k)

%p binomial(n,k)*A000296(n-k) ;

%p end proc:

%t 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 *)

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t Table[Length[Select[sps[Range[n]],Count[#,{_}]==k&]],{n,0,9},{k,0,n}] (* _Gus Wiseman_, Feb 13 2019 *)

%Y Cf. A000110, A052889, A124324.

%Y A250104 is an essentially identical triangle, differing only in row 1.

%Y For columns see A000296, A250105, A250106, A250107.

%Y Cf. A000126, A001610, A032032, A052841, A066982, A080107, A169985, A187784, A324011, A324014, A324015.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Oct 28 2006