A169608 a(n) is the number of ways to evaluate a polynomial of degree n, say p0 + p1*x + ... + pn*x^n, where each addition or multiplication takes exactly two arguments.

1, 1, 7, 163, 11602, 2334244, 1304066578, 1972869433837, 8012682343669366, 86298937651093314877, 2449381767217281163362301

Offset

0,3

References

Guillaume Revy, Implementation of binary floating-point arithmetic on embedded integer processors, Ph D Thesis, University Lyon - ENS Lyon, December 2009, Table 6.1 in Section 6.1.6

Links

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

Example

For example, there are 7 ways to evaluate a polynomial of degree 2:
((a0+(x*a1))+(x*(x*a2)))
((a0+(x*a1))+((x*x)*a2))
(a0+(x*(a1+(x*a2))))
(a0+((x*a1)+(x*(x*a2))))
(a0+((x*a1)+((x*x)*a2)))
((x*a1)+(a0+(x*(x*a2))))
((x*a1)+(a0+((x*x)*a2)))

Maple

cparen := proc(e)
local i, l, s, a, b, pa, pb, la, ee, e1, v, t, g;
option remember;
if type(e, name) then 1
elif type(e, `+`) then
s := 0; ee := convert(e, list); e1 := ee[1]; ee := subsop(1=NULL, ee);
for i from 0 to nops(ee)-1 do
for la in combinat[choose](ee, i) do
a := e1+convert(la, `+`); b := e-a; pa := procname(a); pb := procname(b); s := s + pa * pb;
od
od;
g := 0;
for a in e while g<>1 do g:=gcd(g, a) od;
if g=1 then g:=[] elif type(g, `*`) then g:=convert(g, list) else g:=[g] fi;
g := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, g);
for i from 1 to nops(g) do
for v in combinat[choose](g, i) do
a := convert(v, `*`); t := expand(e/a); s := s + procname(a)*procname(t);
od
od;
s
elif type(e, `*`) or type(e, `^`) then
s := 0;
if type(e, `*`) then ee := convert(e, list) else ee:=[e] fi;
ee := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, ee);
for i from 1 to iquo(nops(ee), 2) do
for la in combinat[choose](ee, i) do
a := convert(la, `*`); b := e/a;
if 2*i=nops(ee) and op(1, {a, b})<>a then next fi;
if a=b then s := s + (procname(a) * (1+procname(a))) / 2;
else s := s + procname(a)*procname(b);
fi
od
od;
s
else ERROR("unexpected type", whattype(e), e)
fi
end:
A169608 := proc(n) cparen(sum(p[i] * x^i, i=0..n)); end:

Crossrefs

Sequence in context: A027549 A212856 A351610 * A184754 A160241 A020998

Adjacent sequences: A169605 A169606 A169607 * A169609 A169610 A169611

Keyword

nice,nonn

Author

Christophe Mouilleron, Dec 03 2009, Jan 23 2010

Extensions

Author's name changed by N. J. A. Sloane, Dec 17 2009, at the request of Paul Zimmermann

Minor editing of definition by N. J. A. Sloane, Dec 19 2009

Add a(7) to a(10) Christophe Mouilleron, Jan 04 2010

Status

approved