A173157 a(n) is the number of ways to evaluate a bivariate polynomial of the form p(T,X) = p00 + T * q(X) where q(X) is an univariate polynomial of degree n. Each addition or multiplication takes exactly two arguments, and two parenthesizations which are equal modulo commutativity are considered as a unique way to evaluate p(T,X).

1, 10, 481, 88384, 57363910, 122657263474, 829129658616013, 17125741272619781635, 1055157310305502607244946, 190070917121184028045719056344, 98543690848554380947490522591191672

Offset

0,2

References

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

Links

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

Example

For example, there are 10 ways of evaluating p00 + T * (p10 + p11 * X):
p00 + ((p10*T) + (p11*(X*T)))
p00 + ((p10*T) + ((p11*T)*X))
p00 + ((p10*T) + ((p11*X)*T))
p00 + (p10 + (p11*X)) * T
(p00 + (p10*T)) + (p11*(X*T))
(p00 + (p10*T)) + ((p11*T)*X)
(p00 + (p10*T)) + ((p11*X)*T)
(p00 + (p11*(X*T))) + (p10*T)
(p00 + ((p11*T)*X)) + (p10*T)
(p00 + ((p11*X)*T)) + (p10*T)

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:
f := proc(n) local i; cparen(a[0, 0] + add(a[1, i]*T*X^i, i=0..n)) end:

Crossrefs

This generalizes A169608.

Sequence in context: A257133 A159533 A274760 * A035320 A200458 A223122

Adjacent sequences: A173154 A173155 A173156 * A173158 A173159 A173160

Keyword

nonn

Author

Christophe Mouilleron, Feb 11 2010

Status

approved