[seqfan] A179454 Permutation trees of power n and height k

peter.luschny peter.luschny at googlemail.com
Sun Jul 18 21:28:28 CEST 2010

!! The sequence is not yet submitted !!

Bonjour à tous!

I am contemplating the connection between trees and
permutations. There is a famous one which is numerically
expressed by the Eulerian numbers.

There is another one which does not yet show up in OEIS.
If I had to choose a catchy name I would call them
the Eulerian numbers of the second kind. (But of course
I will not use this name.)

My problem is a good wording of the definition.
Any suggestions and corrections are welcome.

Especially I am looking for the right name of the
natural correspondence between the permutation and
the tree. It is easily described, though. Imagine the
caterpillar crawling around the periphery of the
tree. But not 'western style' starting at the left
hand side but starting on the right hand side.

More information can be found on my user pages [1][2].

A179454 Permutation trees of power n and height k.

A permutation tree is a rooted tree that has vertex set {0,1,2,..,n}
and root 0, and in which each child is larger than its parent. The
power of a permutation tree is the number of descendants of the root.
The height of a permutation tree is the number of descendants of the
root on the longest chain starting at the root of the tree and ending
at a leaf. The correspondence with the permutation is given by
traversing the tree in ?reflected preorder?.

Offset 1


1, 1,
1, 4,     1,
1, 14,    8,      1,
1, 51,    54,     13,     1,
1, 202,   365,    132,    19,    1,
1, 876,   2582,   1289,   265,   26,   1,
1, 4139,  19404,  12859,  3409,  473,  34,  1,
1, 21146, 155703, 134001, 43540, 7666, 779, 43, 1

[1] http://www.oeis.org/wiki/User:Peter_Luschny/PermutationTrees
[2] http://www.oeis.org/wiki/User:Peter_Luschny/PermutationTypes

More information about the SeqFan mailing list