A032128 Number of dyslexic planted planar trees with n nodes.

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

Offset: 1

Author

Christian G. Bower

Keywords

• nonn
• eigen

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)/(1-A(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 sub-rooted 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 sub-rooted 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 "sub-rooted 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 sub-rooted dyslexic planar trees (= boxes on a reversible line) with a total of n-1 nodes in all subtrees (the n-th node is the single root of the whole tree). This means that b(n-1) = a(n) for n >= 2.

(End)

Examples

			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 sub-rooted 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 sub-rooted trees each with 1 node (1 possibility). Hence, b(4) = 4 + 2 + 1 + 2 + 1 = 10 = a(5).
(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

Crossrefs

Cf. A001224, A038035.

When a(1) = 2, we get sequence A032130.

Programs

Mathematica

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

PARI

BIK(p)={(1/(1-p) + (1+p)/subst(1-p, 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

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)/(1-A(x)) + (A(x) + A(x^2))/(1-A(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)

Extensions

a(28)-a(33) from Petros Hadjicostas, Jan 13 2018

Name edited by Petros Hadjicostas, Jan 14 2018