

A217877


Triangle read by rows: minimum inversion terminator in rooted labeled trees.


1



1, 2, 1, 6, 8, 2, 24, 75, 20, 6, 120, 864, 216, 72, 24, 720, 12005, 2744, 882, 336, 120, 5040, 196608, 40960, 12288, 4608, 1920, 720, 40320, 3720087, 708588, 196830, 69984, 29160, 12960, 5040, 362880, 80000000, 14000000, 3600000, 1200000, 480000, 216000, 100800, 40320
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

T(n,k) is the number of trees on vertex set [0,n1], 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.


LINKS

Andrew Howroyd, Table of n, a(n) for n = 2..1276


FORMULA

T(n,0) = (n1)!, T(n,k) = k!*(nk1)*n^(nk2) for 1<=k<=n2.
Proof. For any given increasing tree T on [0,k], the number of rootedat0 trees on [0,n1] that contain T is (k+1)n^(nk2) [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,n1] that contain *some* increasing tree on [0,k] is (k+1)!n^(nk2). But the minimum inversion terminator is k precisely when the tree contains some increasing tree on [0,k1] but none on [0,k]. The number of such trees is therefore k!n^(nk1)  (k+1)!n^(nk2) = T(n,k) (for k>=1). QED.
This gives a nice combinatorial interpretation of the identity n^(n2) = (n1)! + Sum_{k=1..n2} k!(nk1)n^(nk2). The identity is easy to establish analytically, of course, because the sum is telescoping.


EXAMPLE

Triangle starts at row n=2:
1;
2, 1;
6, 8, 2;
24, 75, 20, 6;
120, 864, 216, 72, 24;
720, 12005, 2744, 882, 336, 120;
5040, 196608, 40960, 12288, 4608, 1920, 720;
...
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.


MATHEMATICA

Table[If[k==0, (n1)!, k!(nk1)n^(nk2)], {n, 2, 12}, {k, 0, n2}]


PROG

(PARI) T(n, k) = {if(!k, (n1)!, k!*(nk1)*n^(nk2))}
{ for(n=2, 10, for(k=0, n2, print1(T(n, k), ", ")); print) } \\ Andrew Howroyd, Apr 28 2020


CROSSREFS

Row sums give A000272.
Sequence in context: A113374 A136470 A220884 * A138510 A026215 A026220
Adjacent sequences: A217874 A217875 A217876 * A217878 A217879 A217880


KEYWORD

nonn,tabl


AUTHOR

David Callan, Oct 14 2012


EXTENSIONS

Terms a(38) and beyond from Andrew Howroyd, Apr 28 2020


STATUS

approved



