login
A124027
G. J. Chaitin's numbers of s-expressions of size n are given by the coefficients of polynomials p(k, x) satisfying p(k, x) = Sum[p(j, x)*p(k - j, x), {j, 2, k - 1}]. The coefficients of these polynomials give the triangle shown here.
5
0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 3, 0, 1, 2, 0, 6, 0, 1, 0, 10, 0, 10, 0, 1, 5, 0, 30, 0, 15, 0, 1, 0, 35, 0, 70, 0, 21, 0, 1, 14, 0, 140, 0, 140, 0, 28, 0, 1, 0, 126, 0, 420, 0, 252, 0, 36, 0, 1, 42, 0, 630, 0, 1050, 0, 420, 0, 45, 0, 1, 0, 462, 0, 2310, 0, 2310, 0, 660, 0, 55, 0, 1, 132, 0
OFFSET
1,11
COMMENTS
Row sum sequence: Table[Sum[CoefficientList[p[n, x], x][[m]], {m, 1, Length[CoefficientList[p[n, x], x]]}], {n, 0, 15}] {0, 1, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835}
REFERENCES
G. J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987, page 169.
FORMULA
p(k, x) = Sum[p(j, x)*p(k - j, x), {j, 2, k - 1}].
EXAMPLE
Triangular sequence
{0},
{0, 1},
{1},
{0, 1},
{1, 0, 1},
{0, 3, 0, 1},
{2, 0, 6, 0, 1},
{0, 10, 0, 10, 0, 1},
{5, 0, 30, 0, 15, 0, 1},
{0, 35, 0, 70, 0, 21, 0, 1},
{14, 0, 140, 0, 140, 0, 28, 0, 1}
MAPLE
p := proc(k, x) option remember ; if k = 0 then 0 ; elif k= 1 then x; elif k= 2 then 1; else add(p(j, x)*p(k-j, x), j=2..k-1) ; fi ; end: A124027 := proc(n, k) coeftayl( p(n, x), x=0, k) ; end: printf("0, 0, 1, ") ; for n from 0 to 18 do for k from 0 to n-2 do printf("%d, ", A124027(n, k)) ; od: od: # R. J. Mathar, Oct 08 2007
MATHEMATICA
p[0, x] = 0; p[1, x] = x; p[2, x] = 1; p[k_, x_] := p[k, x] = Sum[p[j, x]*p[k - j, x], {j, 2, k - 1}]; w = Table[CoefficientList[p[n, x], x], {n, 0, 10}]; Flatten[w]
CROSSREFS
See A097610 for another version. Cf. A072851.
Sequence in context: A199176 A021336 A100749 * A097610 A161556 A317302
KEYWORD
nonn,tabf,easy
AUTHOR
Roger L. Bagula, Oct 31 2006
EXTENSIONS
Edited by N. J. A. Sloane, Oct 07 2007
More terms from R. J. Mathar, Oct 08 2007
STATUS
approved