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.

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

Author

Roger L. Bagula, Oct 31 2006

Keywords

• nonn
• tabf
• easy

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}

Examples

			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}
		

References

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

Crossrefs

See A097610 for another version. Cf. A072851.

Programs

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]

Formula

p(k, x) = Sum[p(j, x)*p(k - j, x), {j, 2, k - 1}].

Extensions

Edited by N. J. A. Sloane, Oct 07 2007

More terms from R. J. Mathar, Oct 08 2007