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.

0, 1, 4, 24, 224, 2880, 47232, 942592, 22171648, 600698880, 18422374400, 630897721344, 23864653578240, 988197253808128, 44460603225407488, 2159714024218951680, 112652924603290615808, 6280048587936003784704, 372616014329572403183616, 23445082059018189741752320, 1559275240299007139066675200

Offset: 0

Author

Geoffrey Critzer, Sep 17 2012

Keywords

• nonn

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

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.

Crossrefs

Cf. A048802, A072034.

Programs

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 *)

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

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