|
| |
|
|
A006153
|
|
E.g.f. 1/(1-x*exp(x)).
(Formerly M3578)
|
|
3
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Without the first "1" = eigensequence of triangle A003566. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), 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. [From Dennis P. Walsh, Nov 15 2011]
a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} such that for some j>1, f^j=f where f^j denotes iterated functional composition. The e.g.f. = exp(log(1/(1-A(x))) where A(x) = x*exp(x) enumerates the connected functions for the case j=2. - Geoffrey Critzer, Jan 21 2012
|
|
|
REFERENCES
| Getu, S.; Shapiro, L. W.; Combinatorial view of the composition of functions. Ars Combin. 10 (1980), 131-145.
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
| 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, (n-k)^k/k!).
For n>=1 a(n-1)=b(n) where b(1)=1 and b(n)=sum(i=1, n-1, i*binomial(n-1, i)*b(i)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Nov 13 2004
a(n) = sum(A199673(n,k),k=1..n) = sum(n! k^(n-k)/(n-k)!, k=1..n) [From Dennis P. Walsh, Nov 15 2011]
E.g.f. for a(n), n>=1: x*e^x/(1-x*e^x).
|
|
|
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.
|
|
|
MAPLE
| a := proc(n) local k; add(k^(n-k)*n!/(n-k)!, k=1..n); end; # for n >= 1
|
|
|
PROG
| (Pari) x='x+O('x^66); /* that many terms */
egf=1/(1-x*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 */
|
|
|
CROSSREFS
| Cf. A072597.
Cf. A003566.
Row sums of triangle A199673.
Sequence in context: A158577 A006879 A163861 * A183387 A025164 A166901
Adjacent sequences: A006150 A006151 A006152 * A006154 A006155 A006156
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Simon Plouffe, N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Definition corrected, Joerg Arndt, Apr 30 2011.
|
| |
|
|
