|
%I #35 Mar 30 2020 03:18:23
%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
|
