# Recurrence relation for multivariate polynomials

I am trying to define a function which recursively computes a polynomial associated to every binary string:

ComputePoly[s_]:=(** Recurse on the string s**)


For example, suppose my initial conditions were the following:

ComputePoly[""]:=1;
ComputePoly["0"]:=x_1;
ComputePoly["1"]:=x_2;


And suppose my recurrence relation was:

ComputePoly[u concatenated with v]:=ComputePoly[u]*ComputePoly[v]


Then this would describe a homomorphism from the monoid of binary strings to the multiplicative monoid of a polynomial ring in $x_1,x_2$.

How would I implement something like this? Should I even use strings, or is there a better data structure for working with binary sequences?

• What are x_1 and x_2? – David G. Stork Jun 25 '15 at 0:06
• Indeterminates, which generate the polynomial ring. – pre-kidney Jun 25 '15 at 0:22
• Maybe I am missing something, but do you just want $x_1^\text{# of 0s} x_2^\text{# of 1s}$? – wxffles Jun 25 '15 at 1:10
• In the example I've given, that is what it reduces to. There is a much more complicated recurrence that I am currently working with. – pre-kidney Jun 25 '15 at 4:06

As a recurrence:

ComputePoly[{}] := 1;
ComputePoly[{0}] := x1
ComputePoly[{1}] := x2
ComputePoly[l_List] := ComputePoly[l[[1 ;; 1]]]*ComputePoly[Rest@l]

ComputePoly[{0, 1, 0, 1, 1, 1, 1}]

(* x1^2 x2^5 *)


Of course different recurrence relationships need different implementations. As you don't mention your actual one it's very difficult to provide more insight