

A006153


E.g.f.: 1/(1x*exp(x)).
(Formerly M3578)


14



1, 1, 4, 21, 148, 1305, 13806, 170401, 2403640, 38143377, 672552730, 13044463641, 276003553860, 6326524990825, 156171026562838, 4130464801497105, 116526877671782896, 3492868475952497313, 110856698175372359346, 3713836169709782989993
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Without the first "1" = eigensequence of triangle A003566.  Gary W. Adamson, Dec 29 2008
a(n) is the sum of the row entries of triangle A199673, that is, a(n) is the number of ways to assign n people into labeled groups and then to assign a leader for each group from its members; see example below.  Dennis P. Walsh, Nov 15 2011
a(n) is the number of functions f:{1,2,...,n}>{1,2,...,n} (endofunctions) such that for some j>1, f^j=f where f^j denotes iterated functional composition. Equivalently, the number of endofunctions such that every element is mapped to a recurrent element. Equivalently, every vertex of the functional digraph is at a distance at most 1 from a cycle.  Geoffrey Critzer, Jan 21 2012


REFERENCES

Getu, S.; Shapiro, L. W.; Combinatorial view of the composition of functions. Ars Combin. 10 (1980), 131145.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.32(d).


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 110
Dennis Walsh, Assigning people into labeled groups with leaders


FORMULA

a(n) = n! * Sum_{k=0..n}(nk)^k/k!.
a(n) = Sum_{k=0..n} k! k^(nk) binomial(n,k).
For n>=1, a(n1) = b(n) where b(1)=1 and b(n) = Sum_{i=1..n1} i*binomial(n1, i)*b(i).  Benoit Cloitre, Nov 13 2004
a(n) = Sum_{k=1..n}A199673(n,k) = Sum_{k=1..n}n! k^(nk)/(nk)!.  Dennis P. Walsh, Nov 15 2011
E.g.f. for a(n), n>=1: x*e^x/(1x*e^x).  Dennis P. Walsh, Nov 15 2011
a(n) ~ n! / ((1+LambertW(1))*LambertW(1)^n).  Vaclav Kotesovec, Jun 21 2013


EXAMPLE

a(3) = 21 since there are 21 ways to assign 3 people into labeled groups with designated leaders. If there is one group, there are 3 ways to select a leader from the 3 people in the group. If there are two groups (group 1 and group 2), there are 6 ways to assign leaders and then 2 ways to select a group for the remaining person, and thus there are 12 assignments. If there are three groups (group1, group 2, and group3), each person is a leader of their singleton group, and there are 6 ways to assign the 3 people to the 3 groups. Hence a(3) = 3 + 12 + 6 = 21.
a(4) = 148 = 4 + 48 + 72 + 24.


MAPLE

a := proc(n) local k; add(k^(nk)*n!/(nk)!, k=1..n); end; # for n >= 1


MATHEMATICA

With[{nn=20}, CoefficientList[Series[1/(1x Exp[x]), {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Aug 29 2012 *)


PROG

(PARI) x='x+O('x^66); /* that many terms */
egf=1/(1x*exp(x)); /* = 1 + x + 2*x^2 + 7/2*x^3 + 37/6*x^4 + 87/8*x^5 +... */
Vec(serlaplace(egf)) /* show terms */ /* Joerg Arndt, Apr 30 2011 */
(Sage)
def A006153_list(len):
f, R, C = 1, [1], [1]+[0]*(len1)
for n in (1..len1):
f *= n
for k in range(n, 0, 1):
C[k] = C[k1]*(1/(k1) if k>1 else 1)
C[0] = sum((1)^k*C[k] for k in (1..n))
R.append(C[0]*f)
return R
print A006153_list(20) # Peter Luschny, Feb 21 2016


CROSSREFS

Row sums of triangle A199673.
Cf. A003566, A072597, A089148.
Sequence in context: A233481 A163861 A247054 * A286286 A277505 A183387
Adjacent sequences: A006150 A006151 A006152 * A006154 A006155 A006156


KEYWORD

nonn,easy,nice


AUTHOR

Simon Plouffe and N. J. A. Sloane


EXTENSIONS

Definition corrected by Joerg Arndt, Apr 30 2011


STATUS

approved



