login
A122455
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.
15
1, 1, 3, 13, 71, 456, 3337, 27203, 243203, 2357356, 24554426, 272908736, 3218032897, 40065665043, 524575892037, 7197724224361, 103188239447115, 1541604242708064, 23945078236133674, 385890657416861532, 6440420888899573136, 111132957321230896024
OFFSET
0,3
COMMENTS
A122454(n,k) = A098546(n,k) times A036040(n,k) (two triangles shaped by integer partitions A000041(n)).
Row sums of A098546 give sequence A098545 and row sums of A036040 give sequence A000110 (the Bell numbers)
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
Number of Green's H-classes in the full transformation semigroup on [n]. Row sums of A090683. - Geoffrey Critzer, Dec 27 2022
REFERENCES
O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, pages 58-62.
LINKS
FORMULA
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
EXAMPLE
A098546(n) begins 1 2 1 3 3 1 4 6 6 4 1 ...
A036040(n) begins 1 1 1 1 3 1 1 4 3 6 1 ...
so
A122454(n) begins 1 2 1 3 9 1 4 24 18 24 1 ...
and
the present sequence begins 1 3 13 71 ...
with A000041 entries per row.
MAPLE
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
# Alternatively:
A122455 := n -> add(binomial(n, k)*Stirling2(n, k), k=0..n):
seq(A122455(n), n=0..21); # Peter Luschny, Aug 11 2015
MATHEMATICA
Table[Sum[Binomial[n, k]*StirlingS2[n, k], {k, 0, n}], {n, 0, 20}]
PROG
(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
(PARI) a(n)=sum(k=0, n, binomial(n, k) * stirling(n, k, 2) ); /* Joerg Arndt, Jun 16 2012 */
(Magma) [(&+[Binomial(n, k)*StirlingSecond(n, k): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Feb 07 2019
(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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Alford Arnold, Sep 18 2006
EXTENSIONS
More terms from R. J. Mathar, Jul 17 2007
Definition modified by Olivier Gérard, Oct 23 2012
a(0)=1 prepended by Alois P. Heinz, Sep 17 2017
STATUS
approved