A055327 - OEIS

%I #26 Aug 28 2018 23:38:33

%S 1,1,1,1,1,1,2,1,4,1,1,6,5,1,9,13,2,1,12,28,11,1,16,53,40,3,1,20,91,

%T 109,26,1,25,146,254,116,6,1,30,223,524,387,61,1,36,326,998,1068,329,

%U 12,1,42,461,1774,2587,1289,145,1,49,634,2995,5678,4133,911,25,1,56

%N Triangle of rooted identity trees with n nodes and k leaves.

%C Row lengths are 1,1,1,2,2,3,3,4,4,5,5,6,6,...

%H Andrew Howroyd, <a href="/A055327/b055327.txt">Table of n, a(n) for n = 1..1226</a> (first 70 rows)

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F G.f. satisfies A(x,y) = x*y + x*WEIGH(A(x,y)) - x. Shifts up under WEIGH transform.

%e Triangle begins:

%e 1;

%e 1;

%e 1;

%e 1,  1;

%e 1,  2;

%e 1,  4,  1;

%e 1,  6,  5;

%e 1,  9, 13,  2;

%e 1, 12, 28, 11;

%e 1, 16, 53, 40, 3;

%e ...

%e From _Joerg Arndt_, Aug 18 2014: (Start)

%e The identity trees with n=6 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:

%e :

%e :     1:  [ 0 1 2 3 4 5 ]   1

%e :  O--o--o--o--o--o

%e :

%e :     2:  [ 0 1 2 3 4 3 ]   2

%e :  O--o--o--o--o

%e :        .--o

%e :

%e :     3:  [ 0 1 2 3 4 2 ]   2

%e :  O--o--o--o--o

%e :     .--o

%e :

%e :     4:  [ 0 1 2 3 4 1 ]   2

%e :  O--o--o--o--o

%e :  .--o

%e :

%e :     5:  [ 0 1 2 3 2 1 ]   3

%e :  O--o--o--o

%e :     .--o

%e :  .--o

%e :

%e :     6:  [ 0 1 2 3 1 2 ]   2

%e :  O--o--o--o

%e :  .--o--o

%e :

%e This gives [1, 4, 1], row n=6 of the triangle.

%e (End)

%o (PARI)

%o WeighMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, (-1)^(i-1)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}

%o A(n)={my(v=[y]); for(n=2, n, v=concat([y], WeighMT(v))); apply(p->Vecrev(p/y), v)}

%o { my(T=A(15)); for(n=1, #T, print(T[n])) } \\ _Andrew Howroyd_, Aug 28 2018

%Y Row sums give A004111.

%Y Columns 2 to 8: A002620(n-2), A055328, A055329, A055330, A055331, A055332, A055333.

%Y A regular version is A301342.

%Y Cf. A055334.

%K nonn,tabf,eigen

%O 1,7

%A _Christian G. Bower_, May 12 2000