A387632 Triangle read by rows: T(n,k) is the number of connected endofunctions on [n] in which k nodes have no nonrecurrent preimages, n >= 1, 1 <= k <= n.

1, 2, 1, 6, 9, 2, 24, 72, 40, 6, 120, 600, 620, 205, 24, 720, 5400, 9000, 5100, 1236, 120, 5040, 52920, 130200, 113400, 44142, 8659, 720, 40320, 564480, 1928640, 2410800, 1371216, 415520, 69280, 5040, 362880, 6531840, 29635200, 50591520, 39859344, 16941456, 4283064, 623529, 40320

Offset

1,2

Comments

T(n,1) = n! counts endofunctions whose digraph representation is a single fixed point with a tail of preimages.

T(n,n) = (n-1)! counts endofunctions comprised of a single cycle.

Links

Table of n, a(n) for n=1..45.

Philippe Flajolet, Peter J. Grabner, Peter Kirschenhofer, and Helmut Prodinger, On Ramanujan's Q-function, Journal of Computational and Applied Math., vol. 58, iss. 1 (1995-03-20), pp. 103-116.

Natalia L. Skirrow, Euler's tree function

Formula

E.g.f.: log( 1/(1-( (u-1)*x + T(x*E^((u-1)*x)) )) ), where T(x) = -W(-x) is the e.g.f. of A000169.

Let Q(n) = Sum_{k=1..n} n! / ((n-k)!*n^k) = Gamma(n,n) * e^n/n^(n-1) ~ sqrt(Pi*n/2) be Ramanujan's Q function.

T(n,k) = C(n,k) * Sum_{r=0..n-k} (-1)^(n-k-r) * C(n-k,r) * Sum_{j=0..n-1} r^j * (n-1)!/j!.

T(n,k) = (n!/k!) * Sum_{j=n-k..n-1} Stirling2(j,n-k) * (n-1)!/j!.

Sum_{k=1..n} T(n,k) = n^(n-1) * Q(n) = A001865(n).

Sum_{k=1..n} T(n,k)*k = n * (n-1)^(n-1) * (Q(n-1)+1) = n * A063170(n-1).

m-th binomial moment:

Sum_{k=1..n} T(n,k) * C(k,m) = C(n,m) * Gamma(n,n-m) * e^(n-m) = C(n,m) * (n-m)^(n-1) * hypergeometric([1-n,1],[],1/(m-n)).

n-th row has expectation ~ n/e and variance ~ n*(1-1/e)/e.

These are asymptotically the same as A386973, since only Theta(sqrt(n)) nodes are in the cycle.

Example

n\k|   1     2      3      4     5    6   7
---+---------------------------------------
 1 |   1     .      .      .     .    .   .
 2 |   2     1      .      .     .    .   .
 3 |   6     9      2      .     .    .   .
 4 |  24    72     40      6     .    .   .
 5 | 120   600    620    205    24    .   .
 6 | 720  5400   9000   5100  1236  120   .
 7 |5040 52920 130200 113400 44142 8659 720

Mathematica

T[x_]=-LambertW[-x]
l=7
CoefficientList[CoefficientList[Normal[Series[Log[1/(1-((u-1)*x-LambertW[-x*E^((u-1)*x)]))], {x, 0, l}]], x][[2;; ]]/u, u]*Range[1, l]! // MatrixForm

Prog

(Python)
from math import factorial as fact
from sympy.functions.combinatorial.numbers import stirling
T=lambda n, k: fact(n)//fact(k)*sum(fact(n-1)//fact(j)*stirling(j, n-k, 2) for j in range(n-k, n))
(Python)
from math import comb, factorial as fact
T=lambda n, k: comb(n, k)*sum((-1)**(n-k-r)*comb(n-k, r)*sum(fact(n-1)//fact(j)*r**j for j in range(n)) for r in range(n-k+1))

Crossrefs

Cf. A001865 (row sums).

Here we stipulate nonrecurrent preimages prevent leafhood; another convention loosens this to any preimages.

Table of triangles for connected and unrestricted endofunctions by convention:

predecs| any |nonrec.

-------+-------+-------

connect|A386973|this seq.

unrest.|A219859|A231536

Sequence in context: A248927 A176013 A391933 * A263255 A145663 A276664

Adjacent sequences: A387629 A387630 A387631 * A387633 A387634 A387635

Keyword

nonn,tabl

Author

Natalia L. Skirrow, Mar 08 2026

Status

approved