A176703 Coefficients of a recursive polynomial based on Chaitin's S expressions: a(0)=1; a(1)=x; a(2)=1; a(n)=vector(a(n-1)).reverse(a(n-1)).

1, 0, 1, 1, 0, 2, 0, 1, 4, 2, 2, 9, 8, 4, 2, 22, 24, 14, 8, 56, 70, 52, 24, 5, 146, 208, 176, 84, 30, 388, 624, 574, 320, 120, 14, 1048, 1876, 1868, 1184, 470, 112, 2869, 5648, 6088, 4236, 1900, 560, 42, 7942, 17040, 19804, 14928, 7560, 2492, 420, 22192, 51526, 64232

Offset

0,6

Comments

The result is an alternative way to expand s expressions as a binary rooted tree recursion.

References

G. J. Chaitin, Algorithmic Information Theory, Cambridge Press, 1987, page 169

Links

Table of n, a(n) for n=0..57.

Formula

a(0)=1;a(1)=x;a(2)=1;

a(n)=vector(a(n-1)).reverse(a(n-1));

t(n,m)=coefficients(a(n) in x)

Let b(0) = b(2) = 1, b(1) = x, and b(n) = Sum_{i=1..n} b(i-1) * b(n-i) if n>2. Then T(n, k) = coefficient of x^k in b(n) where 0 <= k <= (n+1)/2.

G.f. A(x,y) satisfies A(x,y) = 1 - x * (1 - x - y + 2*x*y) + x * A(x,y)^2. - Michael Somos, Jan 09 2012

G.f.: ( 1 - sqrt( (1 - 2*x)^2 - 4*x^2 * (x + y - 2*x*y) )) / (2*x). - Michael Somos, Jan 09 2012

Row sums are A025262 if offset 0.

Example

{1},
{0, 1},
{1, 0},
{2, 0, 1},
{4, 2, 2},
{9, 8, 4, 2},
{22, 24, 14, 8},
{56, 70, 52, 24, 5},
{146, 208, 176, 84, 30},
{388, 624, 574, 320, 120, 14},
{1048, 1876, 1868, 1184, 470, 112},
{2869, 5648, 6088, 4236, 1900, 560, 42},
{7942, 17040, 19804, 14928, 7560, 2492, 420},
{22192, 51526, 64232, 52208, 29190, 10864, 2520, 132},
{62510, 156128, 207808, 181320, 110260, 46256, 12684, 1584},
{177308, 473952, 670966, 625408, 410400, 190932, 59976, 11088, 429}

Mathematica

a[0] := 1; a[1] := x; a[2] = 1;
a[n_] := a[n] = Table[a[i], {i, 0, n - 1}].Table[a[n - 1 - i], {i, 0, n - 1}];
Table[ CoefficientList[a[n], x], {n, 0, 15}];
Flatten[%]

Prog

(PARI) {T(n, k) = if( 2*k-1  > n, 0, polcoeff( polcoeff( ( 1 - sqrt( (1 - 2*x)^2 - 4*x^2 * (x + y - 2*x*y) + x^2*O(x^n))) / (2*x), n), k))} /* Michael Somos, Jan 09 2012 */

Crossrefs

Cf. A025227, A025262, A072851, A124027

Sequence in context: A158239 A159819 A030188 * A160648 A124912 A138752

Adjacent sequences: A176700 A176701 A176702 * A176704 A176705 A176706

Keyword

nonn,tabf

Author

Roger L. Bagula, Apr 24 2010

Status

approved