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
Examples
{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}
References
- G. J. Chaitin, Algorithmic Information Theory, Cambridge Press, 1987, page 169
Programs
-
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[%] -
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 */
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.
Comments