|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,tabf,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
