A173157 - OEIS

%I #2 Mar 31 2012 10:25:33

%S 1,10,481,88384,57363910,122657263474,829129658616013,

%T 17125741272619781635,1055157310305502607244946,

%U 190070917121184028045719056344,98543690848554380947490522591191672

%N 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).

%D 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

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

%e p00 + ((p10*T) + (p11*(X*T)))

%e p00 + ((p10*T) + ((p11*T)*X))

%e p00 + ((p10*T) + ((p11*X)*T))

%e p00 + (p10 + (p11*X)) * T

%e (p00 + (p10*T)) + (p11*(X*T))

%e (p00 + (p10*T)) + ((p11*T)*X)

%e (p00 + (p10*T)) + ((p11*X)*T)

%e (p00 + (p11*(X*T))) + (p10*T)

%e (p00 + ((p11*T)*X)) + (p10*T)

%e (p00 + ((p11*X)*T)) + (p10*T)

%p cparen := proc(e)

%p local i, l, s, a, b, pa, pb, la, ee, e1, v, t, g;

%p option remember;

%p if type(e, name) then 1

%p elif type(e, `+`) then

%p s := 0; ee := convert(e, list); e1 := ee[1]; ee := subsop(1=NULL, ee);

%p for i from 0 to nops(ee)-1 do

%p for la in combinat[choose](ee, i) do

%p a := e1+convert(la, `+`); b := e-a; pa := procname(a); pb := procname(b); s := s + pa * pb;

%p od

%p od;

%p g := 0;

%p for a in e while g<>1 do g:=gcd(g, a) od;

%p if g=1 then g:=[] elif type(g, `*`) then g:=convert(g, list) else g:=[g] fi;

%p g := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, g);

%p for i from 1 to nops(g) do

%p for v in combinat[choose](g, i) do

%p a := convert(v, `*`); t := expand(e/a); s := s + procname(a)*procname(t);

%p od

%p od;

%p s

%p elif type(e, `*`) or type(e, `^`) then

%p s := 0;

%p if type(e, `*`) then ee := convert(e, list) else ee:=[e] fi;

%p ee := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, ee);

%p for i from 1 to iquo(nops(ee), 2) do

%p for la in combinat[choose](ee, i) do

%p a := convert(la, `*`); b := e/a;

%p if 2*i=nops(ee) and op(1, {a, b})<>a then next fi;

%p if a=b then s := s + (procname(a) * (1+procname(a))) / 2;

%p else s := s + procname(a)*procname(b);

%p fi

%p od

%p od;

%p s

%p else ERROR("unexpected type", whattype(e), e)

%p fi

%p end:

%p f := proc(n) local i; cparen(a[0,0] + add(a[1,i]*T*X^i, i=0..n)) end:

%Y This generalizes A169608.

%K nonn

%O 0,2

%A _Christophe Mouilleron_, Feb 11 2010