|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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 ...
|
|
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):
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|