OFFSET
1,3
COMMENTS
T(n, 0) = (n-1)! because 0 leaves means all nodes are part of a cycle.
T(n, 1) = n (1 node is chosen to be a leaf) * (n-1)! (the others are cyclically arranged) * (n-1) (the leaf's successor is chosen).
T(n, n-1) = n because all leaves must be mapped onto one chosen fixed point.
LINKS
Andrei Z. Broder, The r-Stirling numbers Discrete Math., vol. 449, iss. 3 (1984), pp. 142-259.
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-T(x*e^((y-1)*x)))), where T(x) = -W(-x) is the e.g.f. of A000169.
D-finite with T(n,k) = n*((n/k-1)*T(n-1,k-1) + T(n-1,k)).
Let Q(n) = Sum_{k=1..n} n!/((n-k)!*n^k) ~ sqrt(Pi*n/2) be Ramanujan's Q function (see A393141/A036505).
T(n,k) = C(n,k)*Sum_{j=1..n-k} (-1)^(n-k-j)*C(n-k,j) * j^(n-1)*Q(j).
T(n,k) = (n!/k!) * Sum_{r=1..n-k} S(r; n-1, n-k) if k>0 else (n-1)!, with S(r; n, k) an r-Stirling number of the second kind.
Sum_{k=0..n-1} T(n,k) = n^(n-1)*Q(n) = A001865(n).
Sum_{k=0..n-1} T(n,k)*k = n*(n-1)^(n-1)*Q(n-1).
For the m-th binomial moment:
Sum_{k=0..n-1} T(n,k)*C(k,m) = C(n,m)*(n-m)^(n-1)*Q(n-m).
n-th row has expectation ~ n/e and variance ~ n*(1-1/e)/e.
Sum_{k=1..n-1} T(n,k)*k!/n! = A350589(n-1).
EXAMPLE
Triangle starts:
n\k| 0 1 2 3 4 5 6 7
---+-------------------------------------------------
1 | 1
2 | 1 2
3 | 2 12 3
4 | 6 72 60 4
5 | 24 480 840 220 5
6 | 120 3600 10800 6360 690 6
7 | 720 30240 138600 145320 38220 1974 7
8 |5040 282240 1834560 3010560 1468320 199248 5320 8
MAPLE
T := (n, k) -> local j; binomial(n, k)*add((-1)^(n-k-j)*j^(n-1)*binomial(n-k, j)*hypergeom([1, 1-j], [], -1/j), j = 1..n-k): seq(print(seq(simplify(T(n, k)), k = 0..n-1)), n = 1..8); # Peter Luschny, Mar 08 2026
T := proc(n, k) option remember; if k < 0 or k > n-1 or n < 0 then return 0 fi; if n = 1 then return 1 fi; if k = 0 then return (n-1)*T(n-1, 0) fi; n*((n/k-1)*T(n-1, k-1) + T(n-1, k)) end: seq(print(seq(T(n, k), k = 0..n-1)), n = 1..8); # Peter Luschny, Mar 16 2026
MATHEMATICA
l=7; T[x_]:=-LambertW[-x]
CoefficientList[CoefficientList[Normal[Series[Log[1/(1-T[x*E^((u-1)*x)])], {x, 0, l}]], x][[2;; ]], u]*Range[1, l]! // MatrixForm
(* For individual terms: *)
Q[n_]=Gamma[n, n]*E^n/n^(n-1)
T[n_, k_]=Binomial[n, k]*Sum[(-1)^(n-k-j)*Binomial[n-k, j]*j^(n-1)*Q[j], {j, 1, n-k}]
PROG
(Python)
from math import comb, factorial as fact, perm
rsubset=lambda r, n, k: sum((-1)**(k-r-i)*comb(k-r, i)*(i+r)**(n-r) for i in range(k-r+1))//fact(k-r)
T=lambda n, k: perm(n, n-k)*sum(rsubset(r, n-1, n-k) for r in range(1, n-k+1)) if k else fact(n-1)
(Python)
from math import comb, factorial as fact, perm
from fractions import Fraction as frac
Q=lambda n: sum(frac(perm(n, k), n**k) for k in range(1, n+1))
T=lambda n, k: comb(n, k)*sum((-1)**(n-k-j)*comb(n-k, j)*j**(n-1)*Q(j) for j in range(1, n-k+1))
(Python)
from math import comb, perm
def T(n: int, k: int) -> int: return comb(n, k) * sum((-1) ** (n - k - j) * comb(n - k, j) * sum(j ** (n - i) * perm(j - 1, i - 1) for i in range(1, j + 1)) for j in range(1, n - k + 1)) # Peter Luschny, Mar 08 2026
CROSSREFS
There is also the convention that only nonrecurrent preimages disqualify nodes' leafhood (ie. allowing members of cycles to be leaves). Table of triangles for connected and unrestricted endofunctions by convention:
predecs | nonrec. | any
--------+---------+---------
connect | A387632 | this seq
KEYWORD
nonn,tabl
AUTHOR
Natalia L. Skirrow, Mar 08 2026
STATUS
approved