A202019 Triangle by rows, related to the numbers of binary trees of height less than n, derived from the Mandelbrot set.

1, 1, 1, 1, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 8, 28, 60, 94, 116, 114, 94, 69, 44, 26, 14, 5, 2, 1, 1, 1, 16, 120, 568, 1932, 5096, 10948, 19788, 30782, 41944, 50788, 55308, 54746, 49700, 41658, 32398, 23461, 15864, 10068, 6036, 3434, 1860, 958, 470, 221, 100, 42, 14, 5, 2, 1, 1

Offset: 1

Author

Gary W. Adamson, Dec 08 2011

Keywords

• nonn
• tabf

Comments

As shown on p. 74 [Diaconis & Graham], n-th row polynomials are cyclic with period n, given real roots, if the polynomials are divided through by n. For example, taking x^3 + 2x^2 + x + 1 = 0, the real root = -1.75487766... = c. Then using x^2 + c, we obtain the period three trajectory: -1.75487... -> 1.32471...-> 0.

The shuffling connection [p.75], resulting in a permutation that is the Gilbreath shuffle: "To make the connection with shuffling cards, write down a periodic sequence starting at zero. Write a one above the smallest point, a two above the next smallest point and so on. For example, if c = -1.75486...(a period three point), we have:

2.............1.............3......

0........-1.75487........1.32471... For a fixed value of c, the numbers written on top code up a permutation that is a Gilbreath shuffle".

Row sums = A003095: (1, 2, 5, 26, 677,...) relating to the number of binary trees of height less than n.

Let f(z) = z^2 + c, then row k lists the expansion of the n-fold composition f(f(...f(0)...)) in falling powers of c (with the coefficients for c^0 omitted). The n initial terms of the reversed n-th row are the Catalan numbers (cf. A137560). - Joerg Arndt, Jun 04 2016

Examples

			Row 4 = (1, 4, 6, 6, 5, 2, 1, 1) since (x^4 + 2x^3 + x^2 + x)^2 + x = x^8 + 4x^7 + 6x^6 + 6x^5 + 5x^4 + 2x^3 + x^2 + x.
Triangle begins:
  1;
  1, 1;
  1, 2,  1,  1;
  1, 4,  6,  6,  5,   2,   1,  1;
  1, 8, 28, 60, 94, 116, 114, 94, 69, 44, 26, 14, 5, 2, 1, 1;
  ...
		

References

• Persi Diaconis & R. L. Graham, "Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks", Princeton University Press, 2012; pp. 73-83.

Links

• Alois P. Heinz, Rows n = 1..13, flattened
• Juan Carlos Nuño and Francisco J. Muñoz, Entropy-Variance curves of binary sequences generated by random substitutions of constant length, arXiv:2112.15563 [math.PR], 2021.

Crossrefs

Row sums are A003095.

Cf. A137560 (reversed rows).

Cf. A309049.

Programs

Maple

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(2^(n-1)-1)):
seq(T(n), n=1..7);  # Alois P. Heinz, Jul 11 2019

Mathematica

b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*
     b[n-1-f]]][Min[g-1, n-g/2]]][2^(Length[IntegerDigits[n, 2]]-1)]];
T[n_] := CoefficientList[b[2^(n-1)-1], x];
Array[T, 7] // Flatten (* Jean-François Alcover, Feb 19 2021, after Alois P. Heinz *)

Formula

Coefficients of x by rows such that given n-th row p(x), the next row is (p(x))^2 + x; starting x -> (x^2 + x) -> (x^4 + 2*x^3 + x^2 + x)...

T(n,k) = A309049(2^(n-1)-1,k-1). - Alois P. Heinz, Jul 11 2019