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

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, 40, 40, 30, 30, 30, 30, 30, 24, 20, 20, 20, 20, 20, 15, 15, 15, 15, 12, 12, 12, 10, 10, 10, 10, 8, 8, 6, 6, 5, 5, 4, 4, 3, 3, 2, 1, 720

Offset

0,3

Comments

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.

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

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

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

Links

Table of n, a(n) for n=0..65.

W. Lang, First 6 rows.

W. Lang, Rooted ordered trees with n=5 non-root vertices and number of labelings.

Example

[0! ]; [1! ]; [2!,1]; [3!,3,3,2,1], [4!,12,12,12,8,8,6,6,4,4,3,3,2,1];...
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.
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.

Crossrefs

Sequence in context: A165908 A121281 A232467 * A289869 A334595 A350684

Adjacent sequences: A131446 A131447 A131448 * A131450 A131451 A131452

Keyword

nonn,more,tabf

Author

Wolfdieter Lang, Aug 07 2007

Status

approved