A088957 Hyperbinomial transform of the sequence of 1's.

1, 2, 6, 29, 212, 2117, 26830, 412015, 7433032, 154076201, 3608522954, 94238893883, 2715385121740, 85574061070045, 2928110179818478, 108110945014584623, 4284188833355367440, 181370804507130015569, 8169524599872649117330, 390114757072969964280163

Offset: 0

Author

Paul D. Hanna, Oct 26 2003

Keywords

• nonn

Comments

See A088956 for the definition of the hyperbinomial transform.

a(n) is the number of partial functions on {1,2,...,n} that are endofunctions with no cycles of length > 1. The triangle A088956 classifies these functions according to the number of undefined elements in the domain. The triangle A144289 classifies these functions according to the number of edges in their digraph representation (considering the empty function to have 1 edge). The triangle A203092 classifies these functions according to the number of connected components. - Geoffrey Critzer, Dec 29 2011

a(n) is the number of rooted subtrees (for a fixed root) in the complete graph on n+1 vertices: a(3) = 29 is the number of rooted subtrees in K_4: 1 of size 1, 3 of size 2, 9 of size 3, and 16 spanning subtrees. - Alex Chin, Jul 25 2013 [corrected by Marko Riedel, Mar 31 2019]

From Gus Wiseman, Jan 28 2024: (Start)

Also the number of labeled loop-graphs on n vertices such that it is possible to choose a different vertex from each edge in exactly one way. For example, the a(3) = 29 uniquely choosable loop-graphs (loops shown as singletons) are:

{} {1} {1,2} {1,12} {1,2,13} {1,12,13}

{2} {1,3} {1,13} {1,2,23} {1,12,23}

{3} {2,3} {2,12} {1,3,12} {1,13,23}

{2,23} {1,3,23} {2,12,13}

{3,13} {2,3,12} {2,12,23}

{3,23} {2,3,13} {2,13,23}

{1,2,3} {3,12,13}

{3,12,23}

{3,13,23}

(End)

Examples

			a(5) = 2117 = 1296 + 625 + 160 + 30 + 5 + 1 = sum of row 5 of triangle A088956.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..387
• Marko Riedel et al., Proof of e.g.f. of sequence.

Crossrefs

Cf. A088956 (triangle).

Row sums of A144289. - Alois P. Heinz, Jun 01 2009

Cf. A086331, A000169.

Column k=1 of A144303. - Alois P. Heinz, Oct 30 2012

The covering case is A000272, also the case of exactly n edges.

Without the choice condition we have A006125 (shifted left).

The unlabeled version is A087803.

The choosable version is A368927, covering A369140, loopless A133686.

The non-choosable version is A369141, covering A369142, loopless A367867.

Cf. A000081, A000085, A057500, A062740, A137916, A277473, A322661, A367904, A368596, A368597, A368924.

Programs

Haskell

a088957 = sum . a088956_row  -- Reinhard Zumkeller, Jul 07 2013

Maple

a:= n-> add((n-j+1)^(n-j-1)*binomial(n,j), j=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 30 2012

Mathematica

nn = 16; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[Exp[x] Exp[t], {x, 0, nn}], x]  (* Geoffrey Critzer, Dec 29 2011 *)
With[{nmax = 50}, CoefficientList[Series[-LambertW[-x]*Exp[x]/x, {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Nov 14 2017 *)

PARI

x='x+O('x^10); Vec(serlaplace(-lambertw(-x)*exp(x)/x)) \\ G. C. Greubel, Nov 14 2017

Formula

a(n) = Sum_{k=0..n} (n-k+1)^(n-k-1)*C(n, k).

E.g.f.: A(x) = exp(x+sum(n>=1, n^(n-1)*x^n/n!)).

E.g.f.: -LambertW(-x)*exp(x)/x. - Vladeta Jovovic, Oct 27 2003

a(n) ~ exp(1+exp(-1))*n^(n-1). - Vaclav Kotesovec, Jul 08 2013

Binomial transform of A000272. - Gus Wiseman, Jan 25 2024