cp's OEIS Frontend

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

%I A217922 #42 Jun 11 2025 17:18:55
%S A217922 1,1,2,1,6,7,3,24,46,40,15,120,326,430,315,105,720,2556,4536,4900,
%T A217922 3150,945,5040,22212,49644,70588,66150,38115,10395,40320,212976,
%U A217922 574848,1011500,1235080,1032570,540540,135135
%N A217922 Triangle read by rows: labeled trees counted by improper edges.
%C A217922 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.
%H A217922 G. C. Greubel, <a href="/A217922/b217922.txt">Rows n = 1..50 of the irregular triangle, flattened</a>
%H A217922 J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.2010">Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure</a>, arXiv:1307.2010 [math.CO], 2013-2014.
%H A217922 William Y. C. Chen, Amy M. Fu, and Elena L. Wang, <a href="https://arxiv.org/abs/2506.01649">A Grammatical Calculus for the Ramanujan Polynomials</a>, arXiv:2506.01649 [math.CO], 2025. See p. 3.
%H A217922 Dominique Dumont and Armand Ramamonjisoa, <a href="https://doi.org/10.37236/1275">Grammaire de Ramanujan et Arbres de Cayley</a>, Electr. J. Combinatorics, Volume 3, Issue 2 (1996) R17 (see page 17).
%H A217922 Matthieu Josuat-Vergès, <a href="http://arxiv.org/abs/1310.7531">Derivatives of the tree function</a>, arXiv preprint arXiv:1310.7531 [math.CO], 2013.
%H A217922 Lucas Randazzo, <a href="https://arxiv.org/abs/1905.02083">Arboretum for a generalization of Ramanujan polynomials</a>, arXiv:1905.02083 [math.CO], 2019.
%H A217922 Jiang Zeng, <a href="https://web.archive.org/web/20240422220026/http://math.univ-lyon1.fr/homes-www/zeng/public_html/paper/publication.html">A Ramanujan sequence that refines the Cayley formula for trees</a>, Ramanujan Journal 3 (1999) 1, 45-54, <a href="http://dx.doi.org/10.1023/A:1009809224933">[DOI]</a>
%F A217922 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
%e A217922 Triangle begins:
%e A217922   \ k  0....1....2....3....4......
%e A217922   n
%e A217922   1 |..1
%e A217922   2 |..1
%e A217922   3 |..2....1
%e A217922   4 |..6....7....3
%e A217922   5 |.24...46...40....15
%e A217922   6 |120..326..430...315...105
%e A217922 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.
%t A217922 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]]];
%t A217922 Join[{1}, Table[T[n,k], {n,12}, {k,0,n-2}]//Flatten] (* modified by _G. C. Greubel_, May 07 2019 *)
%o A217922 (SageMath)
%o A217922 def T(n, k):
%o A217922     if k==0: return factorial(n-1)
%o A217922     elif (k<0 or k > n-2): return 0
%o A217922     else: return (n-1)*T(n-1, k) + (n+k-3)* T(n-1, k-1)
%o A217922 flatten([1] + [[T(n, k) for k in (0..n-2)] for n in (2..12)]) # _G. C. Greubel_, May 07 2019
%o A217922 (Magma)
%o A217922 function T(n,k) // T = A217922
%o A217922   if k lt 0 or k gt n-2 then return 0;
%o A217922   elif k eq 0 then return Factorial(n-1);
%o A217922   else return (n-1)*T(n-1,k) + (n+k-3)*T(n-1,k-1);
%o A217922   end if;
%o A217922 end function;
%o A217922 [1] cat [T(n,k): k in [0..n-2], n in [2..12]]; // _G. C. Greubel_, Jan 10 2025
%Y A217922 Row sums are A000272.
%Y A217922 Cf. A054589, A075856.
%K A217922 nonn,tabf
%O A217922 1,3
%A A217922 _David Callan_, Oct 14 2012