|
%I #37 Dec 28 2022 09:02:16
%S 1,1,3,13,71,456,3337,27203,243203,2357356,24554426,272908736,
%T 3218032897,40065665043,524575892037,7197724224361,103188239447115,
%U 1541604242708064,23945078236133674,385890657416861532,6440420888899573136,111132957321230896024
%N a(n) = Sum_{k=0..n} C(n,k)*S2(n,k). Binomial convolution of the Stirling numbers of the 2nd kind. Also sum of the rows of A122454.
%C A122454(n,k) = A098546(n,k) times A036040(n,k) (two triangles shaped by integer partitions A000041(n)).
%C Row sums of A098546 give sequence A098545 and row sums of A036040 give sequence A000110 (the Bell numbers)
%C Equals column zero of triangle A134090: let C equal Pascal's triangle, I the identity matrix and D a matrix where D(n+1,n)=1 and zeros elsewhere; then a(n) = column 0 of row n of (I + D*C)^n (see A134090). - _Paul D. Hanna_, Oct 07 2007
%C Number of Green's H-classes in the full transformation semigroup on [n]. Row sums of A090683. - _Geoffrey Critzer_, Dec 27 2022
%D O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, pages 58-62.
%H Alois P. Heinz, <a href="/A122455/b122455.txt">Table of n, a(n) for n = 0..500</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Green's_relations">Green's relations</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Transformation_semigroup">Transformation semigroup</a>
%F a(n) = [x^n] Sum_{k=0..n} C(n,k) * x^k / [Product_{i=0..k} (1 - i*x)]; equivalently, a(n) = Sum_{k=0..n} C(n,k) * S2(n,k), where S2(n,k) = A048993(n,k) are Stirling numbers of the 2nd kind. - _Paul D. Hanna_, Oct 07 2007
%e A098546(n) begins 1 2 1 3 3 1 4 6 6 4 1 ...
%e A036040(n) begins 1 1 1 1 3 1 1 4 3 6 1 ...
%e so
%e A122454(n) begins 1 2 1 3 9 1 4 24 18 24 1 ...
%e and
%e the present sequence begins 1 3 13 71 ...
%e with A000041 entries per row.
%p sortAbrSteg := proc(L1,L2) local i ; if nops(L1) < nops(L2) then RETURN(true) ; elif nops(L2) < nops(L1) then RETURN(false) ; else for i from 1 to nops(L1) do if op(i,L1) < op(i,L2) then RETURN(false) ; fi ; od ; RETURN(true) ; fi ; end: A098546 := proc(n,k) local prts,m ; prts := combinat[partition](n) ; prts := sort(prts, sortAbrSteg) ; if k <= nops(prts) then m := nops(op(k,prts)) ; binomial(n,m) ; else 0 ; fi ; end: M3 := proc(L) local n,k,an,resul; n := add(i,i=L) ; resul := factorial(n) ; for k from 1 to n do an := add(1-min(abs(j-k),1),j=L) ; resul := resul/ (factorial(k))^an /factorial(an) ; od ; end: A036040 := proc(n,k) local prts,m ; prts := combinat[partition](n) ; prts := sort(prts, sortAbrSteg) ; if k <= nops(prts) then M3(op(k,prts)) ; else 0 ; fi ; end: A122454 := proc(n,k) A098546(n,k)*A036040(n,k) ; end: A122455 := proc(n) add(A122454(n,k),k=1..combinat[numbpart](n)) ; end: seq(A122455(n),n=1..18) ; # _R. J. Mathar_, Jul 17 2007
%p # Alternatively:
%p A122455 := n -> add(binomial(n,k)*Stirling2(n,k),k=0..n):
%p seq(A122455(n),n=0..21); # _Peter Luschny_, Aug 11 2015
%t Table[Sum[Binomial[n, k]*StirlingS2[n, k], {k, 0, n}], {n, 0, 20}]
%o (PARI) a(n)= polcoeff(sum(k=0,n,binomial(n,k)*x^k/prod(i=0,k,1-i*x +x*O(x^n))),n) \\ _Paul D. Hanna_, Oct 07 2007
%o (PARI) a(n)=sum(k=0,n, binomial(n,k) * stirling(n,k,2) ); /* _Joerg Arndt_, Jun 16 2012 */
%o (Magma) [(&+[Binomial(n,k)*StirlingSecond(n,k): k in [0..n]]): n in [0..20]]; // _G. C. Greubel_, Feb 07 2019
%o (Sage) [sum(binomial(n,k)*stirling_number2(n,k) for k in (0..n)) for n in range(20)] # _G. C. Greubel_, Feb 07 2019
%Y Cf. A000041, A000110, A036040, A098545, A098546, A122454.
%Y Cf. A134090, A048993 (S2).
%Y Cf. A090683.
%K easy,nonn
%O 0,3
%A _Alford Arnold_, Sep 18 2006
%E More terms from _R. J. Mathar_, Jul 17 2007
%E Definition modified by _Olivier Gérard_, Oct 23 2012
%E a(0)=1 prepended by _Alois P. Heinz_, Sep 17 2017
|
