login
A216857
Number of connected functions from {1,2,...,n} into a subset of {1,2,...,n} that have a fixed point summed over all subsets.
15
0, 1, 4, 24, 224, 2880, 47232, 942592, 22171648, 600698880, 18422374400, 630897721344, 23864653578240, 988197253808128, 44460603225407488, 2159714024218951680, 112652924603290615808, 6280048587936003784704, 372616014329572403183616, 23445082059018189741752320, 1559275240299007139066675200
OFFSET
0,3
COMMENTS
Essentially the same as A038049.
Also the number of rooted trees whose nodes are labeled with the blocks of a set partition of {1,2,...,n} each having a distinguished element. (See A000248.)
The bijection is straightforward. The trees correspond to functional digraphs mapping the distinguished elements towards the root. All the elements within each block are mapped to the distinguished element of that block. The distinguished element in the root node is the fixed point.
LINKS
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
FORMULA
E.g.f.: T(x*exp(x)) where T(x) is the e.g.f. for A000169.
a(n) = Sum_{k=1..n} binomial(n,k)*k^(n-1).
a(n) ~ sqrt(1+LambertW(exp(-1))) * n^(n-1) / (exp(n)*LambertW(exp(-1))^n). - Vaclav Kotesovec, Jul 09 2013
O.g.f.: Sum_{n>=0} n^(n-1)* x^n / (1 - n*x)^(n+1). - Paul D. Hanna, May 22 2018
E.g.f.: the compositional inverse of A(x) is -A(-x). - Alexander Burstein, Aug 11 2018
MATHEMATICA
With[{nmax = 20}, CoefficientList[Series[-LambertW[-x*Exp[x]], {x, 0, nmax}], x]*Range[0, nmax]!] (* modified by G. C. Greubel, Nov 15 2017 *)
PROG
(PARI) for(n=0, 30, print1(sum(k=1, n, binomial(n, k)*k^(n-1)), ", ")) \\ G. C. Greubel, Nov 15 2017
(PARI) my(x='x+O('x^50)); concat([0], Vec(serlaplace(-lambertw(-x*exp(x))))) \\ G. C. Greubel, Nov 15 2017
CROSSREFS
Sequence in context: A034256 A179539 A277612 * A318005 A224800 A348904
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Sep 17 2012
STATUS
approved