login
Number of organic (also called increasing) vertex labelings of rooted ordered trees with n non-root vertices.
1

%I #12 Aug 29 2019 08:52:29

%S 1,1,2,1,6,3,3,2,1,24,12,12,12,8,8,6,6,4,4,3,3,2,1,120,60,60,60,60,40,

%T 40,40,30,30,30,30,30,24,20,20,20,20,20,15,15,15,15,12,12,12,10,10,10,

%U 10,8,8,6,6,5,5,4,4,3,3,2,1,720

%N Number of organic (also called increasing) vertex labelings of rooted ordered trees with n non-root vertices.

%C Organic vertex labeling with numbers 1,2,...,n means that the sequence of vertex labels along the (unique) path from the root with label 0 to any leaf (non-root vertex of degree 1) is increasing.

%C Row lengths sequence, i.e. the number of rooted ordered trees, C(n):=A000108(n) (Catalan numbers): [1,1,2,5,14,42,...].

%C Number of rooted trees with n non-root vertices [1,1,2,4,9,20,...]=A000081(n+1).

%C Row sums give [1,1,3,155,105,945,...]= A001147(n), n>=0. A035342(n,1), n>=1, first column of triangle S2(3).

%H W. Lang, <a href="/A131449/a131449.txt">First 6 rows</a>.

%H W. Lang, <a href="/A131449/a131449fig5.pdf">Rooted ordered trees with n=5 non-root vertices and number of labelings</a>.

%e [0! ]; [1! ]; [2!,1]; [3!,3,3,2,1], [4!,12,12,12,8,8,6,6,4,4,3,3,2,1];...

%e n=3: 3 labelings (0,1,2)(0,3), (0,1,3) (0,2) and (0,2,3) (0,1) for the rooted tree o-o-x-o.

%e n=3: 3 labelings (0,3)(0,1,2), (0,2)(0,1,3) and (0,1)(0,2,3) for the rooted tree o-x-o-o.

%K nonn,more,tabf

%O 0,3

%A _Wolfdieter Lang_, Aug 07 2007