OFFSET
0,3
COMMENTS
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
Numerators in rational approximations of Lambert W(1). See Ramanujan, Notebooks, volume 2, page 22: "2. If e^{-x} = x, shew that the convergents to x are 1/2, 4/7, 21/37, 148/261, &c." - Michael Somos, Jan 21 2019
REFERENCES
S. Ramanujan, Notebooks, Tata Institute of Fundamental Research, Bombay 1957 Vol. 2, see page 22.
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
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}(n-k)^k/k!.
a(n) = Sum_{k=0..n} k!*k^(n-k)*binomial(n,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, Nov 13 2004
a(n) = Sum_{k=1..n}A199673(n,k) = Sum_{k=1..n}n! k^(n-k)/(n-k)!. - Dennis P. Walsh, Nov 15 2011
E.g.f. for a(n), n>=1: x*e^x/(1-x*e^x). - Dennis P. Walsh, Nov 15 2011
a(n) ~ n! / ((1+LambertW(1))*LambertW(1)^n). - Vaclav Kotesovec, Jun 21 2013\
O.g.f.: Sum_{n>=0} n! * x^n / (1 - n*x)^(n+1). - Paul D. Hanna, May 22 2018
a(0) = 1; a(n) = n * Sum_{k=0..n-1} binomial(n-1,k) * a(k). - Ilya Gutkovskiy, Jul 12 2020
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^(n-k)*n!/(n-k)!, k=1..n); end; # for n >= 1
MATHEMATICA
With[{nn=20}, CoefficientList[Series[1/(1-x Exp[x]), {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Aug 29 2012 *)
a[ n_] := If[n < 0, 0, n! + n! Sum[(n - k)^k / k!, {k, n}]]; (* Michael Somos, Jan 21 2019 *)
PROG
(PARI) x='x+O('x^66);
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)) /* Joerg Arndt, Apr 30 2011 */
(PARI) {a(n) = if(n<0, 0, n! * sum(k=0, n, (n-k)^k / k!))}; /* Michael Somos, Jan 21 2019 */
(Sage)
def A006153_list(len):
f, R, C = 1, [1], [1]+[0]*(len-1)
for n in (1..len-1):
f *= n
for k in range(n, 0, -1):
C[k] = -C[k-1]*(1/(k-1) 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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Definition corrected by Joerg Arndt, Apr 30 2011
STATUS
approved