

A032128


Number of dyslexic planted planar trees with n nodes.


6



1, 1, 2, 4, 10, 25, 69, 193, 565, 1680, 5113, 15757, 49223, 155228, 493937, 1583002, 5106386, 16563542, 53995678, 176797966, 581196445, 1917446630, 6346554919, 21068877925, 70133571797, 234043258802, 782831380626, 2624022529690, 8813080348897, 29654400681966, 99953565213645, 337447946046906, 1140961171059563
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

From Petros Hadjicostas, Jan 14 2018: (Start)
For this sequence, if (b(n): n>=1) = BIK((a(n): n>=1)), then b(n) = a(n+1) for n>=1.
Let A(x) = Sum_{n>=1} a(n)*x^n be the g.f. for this sequence. For an explanation on how to derive the formula BIK(A(x)) = (1/2)*(A(x)/(1A(x)) + (A(x) + A(x^2))/(1  A(x^2))) from Bower's formulae in the link below about transforms, see the comments for sequence A001224. (For that sequence, the roles of sequences (a(n): n>=1) and (b(n): n>=1) are reversed.)
According to Bower's theory in the link below, we have boxes of different sizes and colors. The size of a box is determined by the number of balls it can hold. Two boxes of the same size and color are considered identical (indistinct and unlabeled). We place the boxes on a line that can be read in either direction; i.e., we have a reversible line.
Here, a(n) = number of colors a box holding n balls can be, while b(n) = number of ways of placing boxes in a line that can be read in either direction when the total number of balls is n.
According to C. G. Bower in the weblink below, a "[d]yslexic planar tree is a planar tree where each subrooted tree extending from a node can be read from left to right or right to left." A dyslexic planar tree "can be thought of as viewed by an observer who does not know left from right or as subrooted trees that can be turned around independent of the rest of the tree."
Given the above definition, a "ball" is a "node", a "box" is a "subrooted tree" (without the single root of the whole planar tree), and a "set of colors" for a "box" with n "balls" (= "nodes") is "the set of all dyslexic trees with n nodes". Hence, a(n) = number of all dyslexic planar trees with n nodes. On the other hand, b(n) = number of "reversible" arrangements of having subrooted dyslexic planar trees (= boxes on a reversible line) with a total of n1 nodes in all subtrees (the nth node is the single root of the whole tree). This means that b(n1) = a(n) for n >= 2.
(End)


LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2)
Index entries for sequences related to rooted trees


FORMULA

Shifts left under "BIK" (reversible, indistinct, unlabeled) transform.
From Petros Hadjicostas, Jan 13 2018: (Start)
G.f.: If A(x) = Sum_{n>=1} a(n)*x^n, then a(1) + A(x)/x = BIK(A(x)) = (1/2)*(A(x)/(1A(x)) + (A(x) + A(x^2))/(1A(x^2))). Here a(1) = 1.
In general, if we let a(1) = c, we get:
a(2) = c,
a(3) = (1/2)*(c + 3)*c,
a(4) = (1/2)*(c + 3)*(c + 1)*c,
a(5) = (1/2)*(c^3 + 5*c^2 + 10*c + 4)*c,
a(6) = (1/4)*(2*c^4 + 15*c^3 + 38*c^2 + 37*c + 8)*c,
a(7) = (1/8)*(4*c^4 + 38*c^3 + 103*c^2 + 109*c + 22)*(c + 1)*c,
a(8) = (1/8)*(4*c^6 + 56*c^5 + 251*c^4 + 511*c^3 + 499*c^2 + 201*c + 22)*c,
and so on. No pattern is apparent in these formulae.
(End)


EXAMPLE

From Petros Hadjicostas, Jan 13 2018: (Start)
For this sequence, if (b(n): n>=1) = BIK((a(n): n>=1)), then b(n) = a(n+1) for n>=1.
Since a(1) = 1, a(2) = 1, a(3) = 2, a(4) = 4, etc., a box with 1 ball can be of 1 color only, a box with 2 balls can be of 1 color only, a box with 3 balls can be of 2 colors only, a box with 4 balls can be of 4 colors, and so on.
When we have n=2 balls, we have b(2) = a(3) = 2 because we either have two identical boxes on a line each holding 1 ball or a single box holding 2 balls (and all these boxes can be of 1 color only).
When we have n=3 balls, we have b(3) = a(4) = 4. Here, we consider three cases. In the first case, we have one box holding 3 balls and we have 2 possibilities. In the second case, we have a box with 2 balls and a box with 1 ball, and we have 1 possibility here because the line is reversible (i.e., 21 is considered the same as 12). In the third case, we have three identical boxes each holding 1 ball. Thus, b(3) = 2 + 1 + 1 = 4 = a(4).
When we have n=4 balls, we have b(4) = a(5) = 10. Here we consider 5 cases: a single box with 4 balls (a(4) = 4 possibilities); a box with 3 balls and a box with 1 ball (a(3) x a(1) = 2 x 1 = 2 possibilities); two identical boxes each with 2 balls (1 possibility because a(2) = 1); a box with 2 balls and two identical boxes each with 1 ball (2 possibilities because we have the cases 121 and 112); and 4 identical boxes each with 1 ball (1 possibility). Hence, b(4) = 4 + 2 + 1 + 2 + 1 = 10 = a(5).
Let us now switch the discussion to the counting of dyslexic planar trees. We explain why a(5) = 10. We have five nodes, but one of them is used for the single root of the whole tree. The other 4 nodes are used to create subrooted dyslexic planar trees. There are b(4) = 10 ways of doing that. As above, we consider 5 cases: a single subtree with 4 nodes (with a(4) = 4 possibilities); a subtree with 3 nodes and subtree with 1 node both connected to the single root (with a(3) x a(1) = 2 x 1 = 2 possibilities); two identical subtrees each with 2 nodes and connected to the single root (with a(2) = 1 possibilities); a subtree with 2 nodes and two identical subtrees each with 1 nodes, all connected to the single root (with 2 possibilities because we have the cases 121 and 112); and 4 identical subrooted trees each with 1 node (1 possibility). Hence, b(4) = 4 + 2 + 1 + 2 + 1 = 10 = a(5).
(End)


MATHEMATICA

m = 34; a[1] = 1; A[_] = 0;
Do[A[x_] = x(a[1]+(1/2)(A[x]/(1A[x])+(A[x]+A[x^2])/(1A[x^2]))) + O[x]^m // Normal, {m}];
CoefficientList[A[x], x] // Rest (* JeanFrançois Alcover, Sep 17 2019 *)


PROG

(PARI)
BIK(p)={(1/(1p) + (1+p)/subst(1p, x, x^2))/2}
seq(n)={my(p=O(1)); for(i=1, n, p=BIK(x*p)); Vec(p)} \\ Andrew Howroyd, Aug 30 2018


CROSSREFS

Cf. A001224, A038035.
When a(1) = 2, we get sequence A032130.
Sequence in context: A049125 A191768 A027432 * A052829 A001998 A005817
Adjacent sequences: A032125 A032126 A032127 * A032129 A032130 A032131


KEYWORD

nonn,eigen


AUTHOR

Christian G. Bower


EXTENSIONS

a(28)a(33) from Petros Hadjicostas, Jan 13 2018
Name edited by Petros Hadjicostas, Jan 14 2018


STATUS

approved



