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

G. C. Greubel, Rows n = 1..50 of the irregular triangle, flattened

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

William Y. C. Chen, Amy M. Fu, and Elena L. Wang, A grammatical calculus for the Ramanujan polynomials, Ramanujan J. 70 (2026), Art. 35. See also arXiv:2506.01649 [math.CO], 2025. See p. 3.

Dominique Dumont and Armand Ramamonjisoa, Grammaire de Ramanujan et Arbres de Cayley, Elec. J. Comb. 3(2) (1996), Art. R17. See p. 17.

Matthieu 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 J. 3(1) (1999), 45-54, [DOI].

Formula

T(n, k) = (n-1)*T(n-1, k) + (n+k-3)*T(n-1, k-1), for 1 <= k <= n-2, with T(n, 0) = (n-1)!. - G. C. Greubel, Jan 10 2025

Example

Triangle begins:
  \ k  0....1....2....3....4......
  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_, k_]:= T[n, k]= If[k<0 || k>n-2, 0, If[k==0, (n-1)!, (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

(SageMath)
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)
flatten([1] + [[T(n, k) for k in (0..n-2)] for n in (2..12)]) # G. C. Greubel, May 07 2019
(Magma)
function T(n, k) // T = A217922
  if k lt 0 or k gt n-2 then return 0;
  elif k eq 0 then return Factorial(n-1);
  else return (n-1)*T(n-1, k) + (n+k-3)*T(n-1, k-1);
  end if;
end function;
[1] cat [T(n, k): k in [0..n-2], n in [2..12]]; // G. C. Greubel, Jan 10 2025

Crossrefs

Row sums are A000272.

Cf. A054589, A075856.

Sequence in context: A192329 A059364 A258870 * A382173 A196554 A391931

Adjacent sequences: A217919 A217920 A217921 * A217923 A217924 A217925

Keyword

nonn,tabf

Author

David Callan, Oct 14 2012

Status

approved