login
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.
2
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
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
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