A217922 Triangle read by rows: labeled trees counted by improper edges.

1, 1, 2, 1, 6, 7, 3, 24, 46, 40, 15, 120, 326, 430, 315, 105, 720, 2556, 4536, 4900, 3150, 945, 5040, 22212, 49644, 70588, 66150, 38115, 10395, 40320, 212976, 574848, 1011500, 1235080, 1032570, 540540, 135135

Offset

1,3

Comments

T(n,k) is the number of labeled trees on [n], rooted at 1, with k improper edges, for n >= 1, k >= 0. See Zeng link for definition of improper edge.

Links

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

J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013-2014.

Dominique Dumont, Armand Ramamonjisoa, Grammaire de Ramanujan et Arbres de Cayley, Electr. J. Combinatorics, Volume 3, Issue 2 (1996) R17 (see page 17).

M. Josuat-Vergès, Derivatives of the tree function, arXiv preprint arXiv:1310.7531 [math.CO], 2013.

Lucas Randazzo, Arboretum for a generalization of Ramanujan polynomials, arXiv:1905.02083 [math.CO], 2019.

Jiang Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan Journal 3 (1999) 1, 45-54, [DOI]

Example

Table begins
\ k  0....1....2....3   ...
n
1 |..1
2 |..1
3 |..2....1
4 |..6....7....3
5 |.24...46...40....15
6 |120..326..430...315...105
T(4,2) = 3 because we have 1->3->4->2, 1->4->2->3, 1->4->3->2, in each of which the last 2 edges are improper.

Mathematica

T[n_, 0]:= (n-1)!; T[n_, k_]:= If[k<0 || k>n-2, 0, (n-1)T[n-1, k] +(n+k-3)T[n-1, k-1]];
Join[{1}, Table[T[n, k], {n, 12}, {k, 0, n-2}]//Flatten] (* modified by G. C. Greubel, May 07 2019 *)

Prog

(Sage)
def T(n, k):
    if k==0: return factorial(n-1)
    elif (k<0 or k > n-2): return 0
    else: return (n-1)*T(n-1, k) + (n+k-3)* T(n-1, k-1)
[1] + [[T(n, k) for k in (0..n-2)] for n in (2..12)] # G. C. Greubel, May 07 2019

Crossrefs

Cf. A054589, A075856. Row sums are n^(n-2), A000272.

Sequence in context: A192329 A059364 A258870 * A196554 A244647 A324037

Adjacent sequences: A217919 A217920 A217921 * A217923 A217924 A217925

Keyword

nonn,tabf

Author

David Callan, Oct 14 2012

Status

approved