Multinomial factor simplification

S

SlipEternal

Junior Member
Joined
Jan 4, 2012
Messages
114
I have solved a problem, but the algorithm is taking too long to process. I was hoping to simplify it a bit. Here is what I know:
\(\displaystyle \sum_{n=0}^{a_1+a_2}{\left(\sum_{i=0}^n{\binom{a_1}{i}\binom{a_2}{n-i}x_1^iy_1^{a_1-i}x_2^{n-i}y_2^{a_2-n+i}}\right)}=(x_1+y_1)^{a_1}(x_2+y_2)^{a_2}\)
Now, for any pair \(\displaystyle (x_i,y_i)\), I know that \(\displaystyle x_i+y_i=c\) where \(\displaystyle x_i, y_i, \text{ and }c\) are all positive integers. I have a function that is supposed to calculate the inner sums (as I am looking for statistical data about these inner sums). So, is there a way to simplify this?
\(\displaystyle \sum_{i=0}^n{\binom{a_1}{i}\binom{a_2}{n-i}x_1^iy_1^{a_1-i}x_2^{n-i}y_2^{a_2-n+i}}\)

Trial and error is not yielding any immediate patterns, and the issue is not when I only have two sets of \(\displaystyle (x_i,y_i)\) but when I have an arbitrarily large number of them.
 
Last edited:
Working with it, I was able to get this mess:
\(\displaystyle (-1)^{a_1+a_2-n}\)\(\displaystyle \sum_{i_0=0}^n{\left(\sum_{i_1=0}^{a_1-i_0}{\left({\sum_{i_2=0}^{a_2-n+i_0}{\binom{a_1}{i_0,i_1}\binom{a_2}{(n-i_0),i_2}(-c)^{a_1+a_2-n-i_1-i_2}x_1^{i_0+i_1}x_2^{i_0+i_2}}\right)}\right)}\)
where
\(\displaystyle \binom{a_1}{i_0,i_1} = \frac{a_1!}{i_0!i_1!(a_1-i_0-i_1)!}\) and \(\displaystyle \binom{a_2}{(n-i_0),i_2} = \frac{a_2!}{(n-i_0)!i_2!(a_2-n+i_0-i_2)!}\)
 
Last edited:
While I did reply to myself, this problem is still open. I simply appended the work I did since then. I have also built a spreadsheet and tried out numbers. If there is a pattern, I don't see it. I am not at all familiar with generating functions in multiple variables. Now that I have created the spreadsheet, though, if anyone has any advice about multi-variable generating functions, I can attempt to figure it out myself. The biggest problem is that it is a function needs to be extendable to an arbitrary number of variables. I don't know if that is even possible.
 
Ok, I just figured out that it should have a simple recursion relation similar to that of Pascal's Triangle:
Fix \(\displaystyle x_1, x_2, c\)
Let \(\displaystyle f(a_1,a_2,n) = \sum_{i=0}^n{\binom{a_1}{i}\binom{a_2}{n-i}x_1^i(c-x_1)^{a_1-i}x_2^{n-i}(c-x_2)^{a_2-n+i}}\)
Then this might also be true (I have yet to actually check it):
\(\displaystyle f(a_1,a_2,n) = f(1,0,0)f(a_1-1,a_2,n)+f(1,0,1)f(a_1-1,a_2,n-1)\)\(\displaystyle = f(0,1,0)f(a_1,a_2-1,n)+f(0,1,1)f(a_1,a_2-1,n-1)\)

Given that recursion, how might I go about setting up a multi-variable generating function?
 
Reading through some texts on generating functions, I think I understand a little bit. I think I am looking for the following generating function:
\(\displaystyle B(z_1,z_2,z_3) = \) \(\displaystyle \sum_{a_1,a_2,n \ge 0}{\left(\sum_{i=0}^n{\binom{a_1}{i}\binom{a_2}{n-i}x_1^i(c-x_1)^{a_1-i}x_2^{n-i}(c-x_2)^{a_2-n+i}}\right)z_1^{a_1}z_2^{a_2}z_3^n}\)
 
So, to solve it, I think I need these definitions and identities:
\(\displaystyle f(a_1,a_2,n) := \sum_{i=0}^n{\binom{a_1}{i}\binom{a_2}{n-i}x_1^i(c-x_1)^{a_1-i}x_2^{n-i}(c-x_2)^{a_2-n+i}}\)
\(\displaystyle f(a_1,a_2,n) = f(1,0,0)f(a_1-1,a_2,n)+f(1,0,1)f(a_1-1,a_2,n-1)\)
\(\displaystyle f(a_1,a_2,n) = f(0,1,0)f(a_1,a_2-1,n)+f(0,1,1)f(a_1,a_2-1,n-1)\)
\(\displaystyle \sum_{n=0}^{a_1+a_2}{f(a_1,a_2,n)} = c^{a_1+a_2}\)

With those, I might be able to get a generating function. I am not sure if I need more equations (since the last one is not linear).
 
By plugging in the following:
\(\displaystyle f(1,0,0) = (c-x_1)\), \(\displaystyle f(1,0,1) = x_1\), \(\displaystyle f(0,1,0) = (c-x_2)\), and \(\displaystyle f(0,1,1) = x_2\)

I get:
\(\displaystyle f(a_1,a_2,n) = (c-x_1)f(a_1-1,a_2,n) + x_1f(a_1-1,a_2,n-1)\)

\(\displaystyle f(a_1-1,a_2,n) = (c-x_2)f(a_1-1,a_2-1,n) + x_2f(a_1-1,a_2-1,n-1)\)

\(\displaystyle f(a_1,a_2,n) = (c-x_2)f(a_1,a_2-1,n) + x_2f(a_1,a_2-1,n-1)\)

\(\displaystyle f(a_1,a_2-1,n) = (c-x_1)f(a_1-1,a_2-1,n) + x_1f(a_1-1,a_2-1,n-1)\)

So,
\(\displaystyle f(a_1,a_2,n) = \) \(\displaystyle (c-x_1)\left((c-x_2)f(a_1-1,a_2-1,n) + x_2f(a_1-1,a_2-1,n-1)\right) +\) \(\displaystyle x_1f(a_1-1,a_2,n-1)\)
\(\displaystyle = (c-x_1)(c-x_2)f(a_1-1,a_2-1,n) +\) \(\displaystyle (c-x_1)x_2f(a_1-1,a_2-1,n-1) + x_1f(a_1-1,a_2,n-1)\)

\(\displaystyle f(a_1,a_2,n) = \) \(\displaystyle (c-x_2)\left((c-x_1)f(a_1-1,a_2-1,n) + x_1f(a_1-1,a_2-1,n-1)\right) +\) \(\displaystyle x_2f(a_1,a_2-1,n-1)\)
\(\displaystyle = (c-x_1)(c-x_2)f(a_1-1,a_2-1,n) +\) \(\displaystyle (c-x_2)x_1f(a_1-1,a_2-1,n-1) + x_2f(a_1,a_2-1,n-1)\)

By setting these two equal, I get:
\(\displaystyle cx_2f(a_1-1,a_2-1,n-1)\text{ } - \) \(\displaystyle x_1x_2f(a_1-1,a_2-1,n-1) + x_1f(a_1-1,a_2,n-1)\)
\(\displaystyle = cx_1f(a_1-1,a_2-1,n-1)\text{ } - \) \(\displaystyle x_1x_2f(a_1-1,a_2-1,n-1) + x_2f(a_1,a_2-1,n-1)\)

Cancelling and rearranging terms, I get:
\(\displaystyle c(x_1-x_2)f(a_1-1,a_2-1,n-1) = \) \(\displaystyle x_1f(a_1-1,a_2,n-1) - x_2f(a_1,a_2-1,n-1)\)
So, by adding 1 to all terms, I get:
\(\displaystyle c(x_1-x_2)f(a_1,a_2,n) = x_1f(a_1,a_2+1,n) - x_2f(a_1+1,a_2,n)\)

Now, using this recurrence relation, I multiply both sides by \(\displaystyle z_1^{a_1}z_2^{a_2}z_3^n\) and sum over \(\displaystyle a_1,a_2,n \ge 0\).
I get:

\(\displaystyle c(x_1-x_2)B(z_1,z_2,z_3) = x_1\sum_{a_1,a_2,n \ge 0}{f(a_1,a_2+1,n)z_1^{a_1}z_2^{a_2}z_3^n}\) \(\displaystyle -x_2\sum_{a_1,a_2,n \ge 0}{f(a_1+1,a_2,n)z_1^{a_1}z_2^{a_2}z_3^n}\)
\(\displaystyle =\frac{x_1}{z_2}\left(B(z_1,z_2,z_3) - \sum_{a_1,n \ge 0}{f(a_1,0,n)z_1^{a_1}z_3^n}\right)\) \(\displaystyle -\frac{x_2}{z_1}\left(B(z_1,z_2,z_3) - \sum_{a_2,n \ge 0}{f(0,a_2,n)z_2^{a_2}z_3^n}\right)\)
\(\displaystyle =\frac{x_1}{z_2}\left(B(z_1,z_2,z_3) - \sum_{a_1,n \ge 0}{\binom{a_1}{n}x_1^{n}(c-x_1)^{a_1-n}z_1^{a_1}z_3^n}\right)\) \(\displaystyle -\frac{x_2}{z_1}\left(B(z_1,z_2,z_3) - \sum_{a_2,n \ge 0}{\binom{a_2}{n}x_2^n(c-x_2)^{a_2-n}z_2^{a_2}z_3^n}\right)\)

From here, I think I need to use the binomial recurrence relation to solve this. Do I seem to be on the right track?
 
Solving the binomial recurrence relation in essentially the same way, I get this:

\(\displaystyle B(z_1,z_2,z_3) = \) \(\displaystyle \frac{\frac{x_2(c-x_2)z_2^2}{(1-z_2)(z_2(c-x_2)+z_2z_3x_2-1)}-\frac{x_1(c-x_1)z_1^2}{(1-z_1)(z_1(c-x_1)+z_1z_3x_1-1)}}{c(x_1-x_2)z_1z_2+x_2z_2-x_1z_1}\)

How do I go about checking to see if I am right? Lol.

Additionally, if I am correct, is there a way to generalize this to an arbitrary number of variables?
 
Last edited:
You must log in or register to reply here.
Top