%I #13 Apr 29 2020 18:13:27
%S 1,2,1,6,8,2,24,75,20,6,120,864,216,72,24,720,12005,2744,882,336,120,
%T 5040,196608,40960,12288,4608,1920,720,40320,3720087,708588,196830,
%U 69984,29160,12960,5040,362880,80000000,14000000,3600000,1200000,480000,216000,100800,40320
%N Triangle read by rows: minimum inversion terminator in rooted labeled trees.
%C T(n,k) is the number of trees on vertex set [0,n-1], rooted at 0, with minimum inversion terminator = k if k>=1, with no inversion terminators if k=0. An inversion is a pair i,j of vertices with j a descendant of i and i>j; j is then an inversion terminator.
%H Andrew Howroyd, <a href="/A217877/b217877.txt">Table of n, a(n) for n = 2..1276</a>
%F T(n,0) = (n-1)!, T(n,k) = k!*(n-k-1)*n^(n-k-2) for 1<=k<=n-2.
%F Proof. For any given increasing tree T on [0,k], the number of rooted-at-0 trees on [0,n-1] that contain T is (k+1)n^(n-k-2) [J. W. Moon, Counting Labelled Trees (1970), Sec. 6.2]. Hence, since there are k! increasing trees on [0,k] [R. H. Stanley, Enumerative Combinatorics, Vol. 1, (1986), Sec. 1.3.16], the number of trees on [0,n-1] that contain *some* increasing tree on [0,k] is (k+1)!n^(n-k-2). But the minimum inversion terminator is k precisely when the tree contains some increasing tree on [0,k-1] but none on [0,k]. The number of such trees is therefore k!n^(n-k-1) - (k+1)!n^(n-k-2) = T(n,k) (for k>=1). QED.
%F This gives a nice combinatorial interpretation of the identity n^(n-2) = (n-1)! + Sum_{k=1..n-2} k!(n-k-1)n^(n-k-2). The identity is easy to establish analytically, of course, because the sum is telescoping.
%e Triangle starts at row n=2:
%e 1;
%e 2, 1;
%e 6, 8, 2;
%e 24, 75, 20, 6;
%e 120, 864, 216, 72, 24;
%e 720, 12005, 2744, 882, 336, 120;
%e 5040, 196608, 40960, 12288, 4608, 1920, 720;
%e ...
%e T(4,2)=2 counts 0->3->2, 0->1 and 0->1->3->2, in both of which the minimum (and only) inversion terminator is 2.
%t Table[If[k==0, (n-1)!, k!(n-k-1)n^(n-k-2)],{n,2,12},{k,0,n-2}]
%o (PARI) T(n,k) = {if(!k, (n-1)!, k!*(n-k-1)*n^(n-k-2))}
%o { for(n=2, 10, for(k=0, n-2, print1(T(n,k), ", ")); print) } \\ _Andrew Howroyd_, Apr 28 2020
%Y Row sums give A000272.
%K nonn,tabl
%O 2,2
%A _David Callan_, Oct 14 2012
%E Terms a(38) and beyond from _Andrew Howroyd_, Apr 28 2020