Solving multivariate generating functions
December 26, 2022
It seemed appropriate to broach the subject directly today—that is, generating functions. To do this, we will be looking at three functions today: f ( x ) f(x) f ( x ) p ( x , y ) p(x,y) p ( x , y ) g ( x , y ) g(x,y) g ( x , y ) G i , j = 3 G i − 1 , j + 3 G i − 1 , j − 1 − 8 G i − 2 , j − 1 G_{i,j}=3G_{i-1,j}+3G_{i-1,j-1}-8G_{i-2,j-1} G i , j = 3 G i − 1 , j + 3 G i − 1 , j − 1 − 8 G i − 2 , j − 1 G G G A A A
1 3 1 9 4 3 27 15 13 9 81 54 52 42 27 … . \begin{matrix}
1\\
3&1\\
9&4&3\\
27&15&13&9\\
81&54&52&42&27\\
\ldots.
\end{matrix} 1 3 9 27 81 … . 1 4 15 54 3 13 52 9 42 27
1 Deriving the Generating Functions
As in the proof for ζ ( 2 ) \zeta(2) ζ ( 2 ) Taylor Series , we utilize the properties of a polynomial to gain more information on its coefficients. The theory of generating functions begins by assigning the sequence as the coefficients of the polynomial:
f ( x ) = 0 x 0 + 1 x 1 + 1 x 2 + 2 x 3 + 3 x 4 + 5 x 5 + … = ∑ i F i x i , p ( x , y ) = 1 x 0 y 0 + 1 x 1 y 0 + 1 x 0 y 1 + 1 x 2 y 0 + 2 x 1 y 1 + 1 x 0 y 2 + 1 x 3 y 0 + 3 x 2 y 1 + 3 x 1 y 2 + 1 x 0 y 3 + … = ∑ i ∑ j P i , j x i y j , g ( x , y ) = 1 x 0 y 0 + 3 x 1 y 0 + 1 x 0 y 1 + 9 x 2 y 0 + 4 x 1 y 1 + 3 x 0 y 2 + 27 x 3 y 0 + 15 x 2 y 1 + 13 x 1 y 2 + 9 x 0 y 3 + … = ∑ i ∑ j G i , j x i y j . \begin{aligned}
f(x)&=0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+\ldots\\
&=\sum_i F_ix^i,\\
p(x,y)&=1x^0y^0\\
&+1x^1y^0+1x^0y^1\\
&+1x^2y^0+2x^1y^1+1x^0y^2\\
&+1x^3y^0+3x^2y^1+3x^1y^2+1x^0y^3\\
&+\ldots\\
&=\sum_i\sum_j P_{i,j}x^iy^j,\\
g(x,y)&=1x^0y^0\\
&+3x^1y^0+1x^0y^1\\
&+9x^2y^0+4x^1y^1+3x^0y^2\\
&+27x^3y^0+15x^2y^1+13x^1y^2+9x^0y^3\\
&+\ldots\\
&=\sum_i\sum_j G_{i,j}x^iy^j.
\end{aligned} f ( x ) p ( x , y ) g ( x , y ) = 0 x 0 + 1 x 1 + 1 x 2 + 2 x 3 + 3 x 4 + 5 x 5 + … = i ∑ F i x i , = 1 x 0 y 0 + 1 x 1 y 0 + 1 x 0 y 1 + 1 x 2 y 0 + 2 x 1 y 1 + 1 x 0 y 2 + 1 x 3 y 0 + 3 x 2 y 1 + 3 x 1 y 2 + 1 x 0 y 3 + … = i ∑ j ∑ P i , j x i y j , = 1 x 0 y 0 + 3 x 1 y 0 + 1 x 0 y 1 + 9 x 2 y 0 + 4 x 1 y 1 + 3 x 0 y 2 + 27 x 3 y 0 + 15 x 2 y 1 + 13 x 1 y 2 + 9 x 0 y 3 + … = i ∑ j ∑ G i , j x i y j .
We then proceed to reduce the generating function into a recurrent form for easier analysis. This is quite trivial for one-dimensional recurrences, but two-dimensional ones need some care around boundary conditions. As
F i : = F i − 1 + F i − 2 , P i , j : = P i − 1 , j + P i − 1 , j − 1 , G i , j : = 3 G i − 1 , j + 3 G i − 1 , j − 1 − 8 G i − 2 , j − 1 , \begin{aligned}
F_i&:=F_{i-1}+F_{i-2},\\
P_{i,j}&:=P_{i-1,j}+P_{i-1,j-1},\\
G_{i,j}&:=3G_{i-1,j}+3G_{i-1,j-1}-8G_{i-2,j-1},
\end{aligned} F i P i , j G i , j := F i − 1 + F i − 2 , := P i − 1 , j + P i − 1 , j − 1 , := 3 G i − 1 , j + 3 G i − 1 , j − 1 − 8 G i − 2 , j − 1 ,
we have recurrent generating functions
f ( x ) = x + x f ( x ) + x 2 f ( x ) , p ( x , y ) = 1 + x p ( x , y ) + x y p ( x , y ) , g ( x , y ) = 1 − 2 x y + 3 x g ( x , y ) + 3 x y g ( x , y ) − 8 x 2 y g ( x , y ) , \begin{aligned}
f(x)&=x+xf(x)+x^2f(x),\\
p(x,y)&=1+xp(x,y)+xyp(x,y),\\
g(x,y)&=1-2xy+3xg(x,y)+3xyg(x,y)-8x^2yg(x,y),
\end{aligned} f ( x ) p ( x , y ) g ( x , y ) = x + x f ( x ) + x 2 f ( x ) , = 1 + x p ( x , y ) + x y p ( x , y ) , = 1 − 2 x y + 3 xg ( x , y ) + 3 x y g ( x , y ) − 8 x 2 y g ( x , y ) ,
which subsequently solves as
f ( x ) = x 1 − x − x 2 , p ( x , y ) = 1 1 − x − x y , g ( x , y ) = 1 − 2 x y 1 − 3 x − 3 x y + 8 x 2 y . \begin{aligned}
f(x)&=\frac{x}{1-x-x^2},\\[3ex]
p(x,y)&=\frac{1}{1-x-xy},\\[3ex]
g(x,y)&=\frac{1-2xy}{1-3x-3xy+8x^2y}.
\end{aligned} f ( x ) p ( x , y ) g ( x , y ) = 1 − x − x 2 x , = 1 − x − x y 1 , = 1 − 3 x − 3 x y + 8 x 2 y 1 − 2 x y .
2 Solving the Fibonacci
I believe all one-degree one-dimensional generating functions may be partial fraction decomposed (this seems easy to prove):
f ( x ) = x 1 − x − x 2 = ( − 1 − 1 / 5 ) / 2 x − ( − 1 − 5 ) / 2 + ( − 1 + 1 / 5 ) / 2 x − ( − 1 + 5 ) / 2 = ( 1 + 1 / 5 ) / 2 ( − 5 − 1 ) / 2 − x + ( 1 − 1 / 5 ) / 2 ( 5 − 1 ) / 2 − x = − 1 / 5 1 − ( 5 − 1 ) x / 2 + 1 / 5 1 − ( 5 + 1 ) x / 2 = 1 5 ( 1 1 − ( 5 + 1 ) x / 2 − 1 1 − ( 5 − 1 ) x / 2 ) \begin{aligned}
f(x)&=\frac{x}{1-x-x^2}\\[3ex]
&=\frac{(-1-1/\sqrt{5})/2}{x-(-1-\sqrt{5})/2}+\frac{(-1+1/\sqrt{5})/2}{x-(-1+\sqrt{5})/2}\\[3ex]
&=\frac{(1+1/\sqrt{5})/2}{(-\sqrt{5}-1)/2-x}+\frac{(1-1/\sqrt{5})/2}{(\sqrt{5}-1)/2-x}\\[3ex]
&=\frac{-1/\sqrt{5}}{1-(\sqrt{5}-1)x/2}+\frac{1/\sqrt{5}}{1-(\sqrt{5}+1)x/2}\\[3ex]
&=\frac{1}{\sqrt{5}}(\frac{1}{1-(\sqrt{5}+1)x/2}-\frac{1}{1-(\sqrt{5}-1)x/2})\\
\end{aligned} f ( x ) = 1 − x − x 2 x = x − ( − 1 − 5 ) /2 ( − 1 − 1/ 5 ) /2 + x − ( − 1 + 5 ) /2 ( − 1 + 1/ 5 ) /2 = ( − 5 − 1 ) /2 − x ( 1 + 1/ 5 ) /2 + ( 5 − 1 ) /2 − x ( 1 − 1/ 5 ) /2 = 1 − ( 5 − 1 ) x /2 − 1/ 5 + 1 − ( 5 + 1 ) x /2 1/ 5 = 5 1 ( 1 − ( 5 + 1 ) x /2 1 − 1 − ( 5 F i − 2 , := P i − 1 , j + P i − 1 , j − 1 , := 3 G i − 1 , j + 3 G i − 1 , j − 1 − 8 G i − 2 , j − 1 ,
we have recurrent generating functions
f ( x ) = x + x f ( x ) + x 2 f ( x ) , p ( x , y ) = 1 + x p ( x , y ) + x y p ( x , y ) , g ( x , y ) = 1 − 2 x y + 3 x g ( x , y ) + 3 x y g ( x , y ) − 8 x 2 y g ( x , y ) , \begin{aligned}
f(x)&=x+xf(x)+x^2f(x),\\
p(x,y)&=1+xp(x,y)+xyp(x,y),\\
g(x,y)&=1-2xy+3xg(x,y)+3xyg(x,y)-8x^2yg(x,y),
\end{aligned} f ( x ) p ( x , y ) g ( x , y ) = x + x f ( x ) + x 2 f ( x ) , = 1 + x p ( x , y ) + x y p ( x , y ) , = 1 − 2 x y + 3 xg ( x , y ) + 3 x y g ( x , y ) − 8 x 2 y g ( x , y ) ,
which subsequently solves as
f ( x ) = x 1 − x − x 2 , p ( x , y ) = 1 1 − x − x y , g ( x , y ) = 1 − 2 x y 1 − 3 x − 3 x y + 8 x 2 y . \begin{aligned}
f(x)&=\frac{x}{1-x-x^2},\\[3ex]
p(x,y)&=\frac{1}{1-x-xy},\\[3ex]
g(x,y)&=\frac{1-2xy}{1-3x-3xy+8x^2y}.
\end{aligned} f ( x ) p ( x , y ) g ( x , y ) = 1 − x − x 2 x , = 1 − x − x y 1 , = 1 − 3 x − 3 x y + 8 x 2 y 1 − 2 x y .
2 Solving the Fibonacci
I believe all one-degree one-dimensional generating functions may be partial fraction decomposed (this seems easy to prove):
f ( x ) = x 1 − x − x 2 = ( − 1 − 1 / 5 ) / 2 x − ( − 1 − 5 ) / 2 + ( − 1 + 1 / 5 ) / 2 x − ( − 1 + 5 ) / 2 = ( 1 + 1 / 5 ) / 2 ( − 5 − 1 ) / 2 − x + ( 1 − 1 / 5 ) / 2 ( 5 − 1 ) / 2 − x = − 1 / 5 1 − ( 5 − 1 ) x / 2 + 1 / 5 1 − ( 5 + 1 ) x / 2 = 1 5 ( 1 1 − ( 5 + 1 ) x / 2 − 1 1 − ( 5 − 1 ) x / 2 ) \begin{aligned}
f(x)&=\frac{x}{1-x-x^2}\\[3ex]
&=\frac{(-1-1/\sqrt{5})/2}{x-(-1-\sqrt{5})/2}+\frac{(-1+1/\sqrt{5})/2}{x-(-1+\sqrt{5})/2}\\[3ex]
&=\frac{(1+1/\sqrt{5})/2}{(-\sqrt{5}-1)/2-x}+\frac{(1-1/\sqrt{5})/2}{(\sqrt{5}-1)/2-x}\\[3ex]
&=\frac{-1/\sqrt{5}}{1-(\sqrt{5}-1)x/2}+\frac{1/\sqrt{5}}{1-(\sqrt{5}+1)x/2}\\[3ex]
&=\frac{1}{\sqrt{5}}(\frac{1}{1-(\sqrt{5}+1)x/2}-\frac{1}{1-(\sqrt{5}-1)x/2})\\
\end{aligned} f ( x ) = 1 − x − x 2 x = x − ( − 1 − 5 ) /2 ( − 1 − 1/ 5 ) /2 + x − ( − 1 + 5 ) /2 ( − 1 + 1/ 5 ) /2 = ( − 5 − 1 ) /2 − x ( 1 + 1/ 5 ) /2 + ( 5 − 1 ) /2 − x ( 1 − 1/ 5 ) /2 = 1 − ( 5 − 1 ) x /2 − 1/ 5 + 1 − ( 5 + 1 ) x /2 1/ 5 = 5 1 ( 1 − ( 5 + 1 ) x /2 1 − 1 − ( 5 − 1 ) x /2 1 )
which is now the sum of two geometric sequences in x x x x i x^i x i
F i = [ x i ] f ( x ) = 1 5 ( ( 5 + 1 2 ) i + ( 5 − 1 2 ) i ) \begin{aligned}
F_i=[x^i]f(x)=\frac{1}{\sqrt{5}}((\frac{\sqrt{5}+1}{2})^i+(\frac{\sqrt{5}-1}{2})^i)
\end{aligned} F i = [ x i ] f ( x ) = 5 1 (( 2 5 + 1 ) i + ( 2 5 − 1 ) i )
which coincides with Binet’s formula as expected.
3 Solving the Pascal
This one was very tricky for me but I ended up solving it at the end of the day.
The key here is sequential isolation of the variable powers with liberal use of geometric series reinterpretations. Of course, one should expect combinatorial arguments to arise at some point. We use [ x ] [x] [ x ] x x x
p ( x , y ) = 1 1 − x − x y = 1 1 − x ⋅ 1 1 − x 1 − x y , [ y j ] p ( x , y ) = 1 1 − x ⋅ ( x 1 − x ) j , P i , j = [ x i ] [ y j ] p ( x , y ) = [ x i ] ( 1 + x + x 2 + … ) ( x + x 2 + x 3 + … ) j = [ x i − j ] ( 1 + x + x 2 + … ) j + 1 \begin{aligned}
p(x,y)&=\frac{1}{1-x-xy}=\frac{1}{1-x}\cdot\frac{1}{1-\frac{x}{1-x}y},\\[3ex]
[y^j]p(x,y)&=\frac{1}{1-x}\cdot(\frac{x}{1-x})^j,\\[3ex]
P_{i,j}=[x^i][y^j]p(x,y)&=[x^i](1+x+x^2+\ldots)(x+x^2+x^3+\ldots)^j\\
&=[x^{i-j}](1+x+x^2+\ldots)^{j+1}
\end{aligned} p ( x , y ) [ y j ] p ( x , y ) P i , j = [ x i ] [ y j ] p ( x , y ) = 1 − x − x y 1 = 1 − x 1 ⋅ 1 − 1 − x x y 1 , = 1 − x 1 ⋅ ( 1 − x x ) j , = [ x i ] ( 1 + x + x 2 + … ) ( x + x 2 + x 3 + … ) j = [ x i − j ] ( 1 + x + x 2 + … ) j + 1
at which point we must use stars and bars with i − j i-j i − j j j j
P i , j = ( i − j + 1 ) ( i − j + 2 ) ⋯ ( i ) j ! = ( i j ) . \begin{aligned}
P_{i,j}&=\frac{(i-j+1)(i-j+2)\cdots(i)}{j!}\\[3ex]
&={i\choose j}.
\end{aligned} P i , j = j ! ( i − j + 1 ) ( i − j + 2 ) ⋯ ( i ) = ( j i ) .
The reason radicals don’t show up here is likely to due with the degrees of the variables and the dimension of the recurrence. It has to do with how simple the second term 1 / ( 1 − x 1 − x y ) 1/(1-\frac{x}{1-x}y) 1/ ( 1 − 1 − x x y )
4 Solving 1761D
Similarly,
g ( x , y ) = 1 − 2 x y 1 − 3 x − 3 x y + 8 x 2 y = 1 1 − 3 x ⋅ 1 − 2 x y 1 − 3 x − 8 x 2 1 − 3 x y , [ y j ] g ( x , y ) = 1 1 − 3 x ⋅ ( 3 x − 8 x 2 1 − 3 x ) j − 1 ( 3 x − 8 x 2 1 − 3 x − 2 x ) = 1 1 − 3 x ⋅ ( 3 x + x 2 1 − 3 x ) j − 1 ( x − 2 x 2 1 − 3 x ) = x j ⋅ 1 1 − 3 x ⋅ ( 3 + x 1 − 3 x ) j − 1 ( 1 + x 1 − 3 x ) , G i , j = [ x i ] [ y j ] g ( x , y ) = [ x i − j ] ( 1 + 3 x + 9 x 2 + … ) ( 3 + x + 3 x 2 + 9 x 3 + … ) j − 1 ( 1 + x + 3 x 2 + 9 x 3 + … ) = ∑ k = 0 j − 1 3 k ( j − 1 k ) [ x i − j ] ( 1 + 3 x + 9 x 2 + … ) ( x + 3 x 2 + 9 x 3 + … ) j − 1 − k ( 1 + x + 3 x 2 + 9 x 3 + … ) = ∑ k = 0 j − 1 3 k ( j − 1 k ) [ x i − 2 j + 1 + k ] ( 1 + 3 x + 9 x 2 + … ) j − k ( 1 + x + 3 x 2 + 9 x 2 + … ) = ∑ k = 0 j − 1 3 k ( j − 1 k ) ( [ x i − 2 j + 1 + k ] ( 1 + 3 x + 9 x 2 + … ) j − k + [ x i − 2 j + k ] ( 1 + 3 x + 9 x 2 + … ) j − k + 1 ) = ∑ k = 0 j − 1 3 k ( j − 1 k ) ( 3 i − 2 j + 1 + k ( i − j j − k − 1 ) + 3 i − 2 j + k ( i − j j − k ) ) = ∑ k = 0 j − 1 3 i − 2 j + 2 k ( j − 1 k ) ( 3 ( i − j j − k − 1 ) + ( i − j j − k ) ) . \begin{aligned}
g(x,y)&=\frac{1-2xy}{1-3x-3xy+8x^2y}\\[3ex]
&=\frac{1}{1-3x}\cdot\frac{1-2xy}{1-\frac{3x-8x^2}{1-3x}y},\\[3ex]
[y^j]g(x,y)&=\frac{1}{1-3x}\cdot(\frac{3x-8x^2}{1-3x})^{j-1}(\frac{3x-8x^2}{1-3x}-2x)\\[3ex]
&=\frac{1}{1-3x}\cdot(3x+\frac{x^2}{1-3x})^{j-1}(\frac{x-2x^2}{1-3x})\\[3ex]
&=x^j\cdot\frac{1}{1-3x}\cdot(3+\frac{x}{1-3x})^{j-1}(1+\frac{x}{1-3x}),\\[3ex]
G_{i,j}&=[x^i][y^j]g(x,y)\\[3ex]
&=[x^{i-j}](1+3x+9x^2+\ldots)(3+x+3x^2+9x^3+\ldots)^{j-1}(1+x+3x^2+9x^3+\ldots)\\[3ex]
&=\sum_{k=0}^{j-1}3^k{j-1\choose k}[x^{i-j}](1+3x+9x^2+\ldots)(x+3x^2+9x^3+\ldots)^{j-1-k}(1+x+3x^2+9x^3+\ldots)\\[3ex]
&=\sum_{k=0}^{j-1}3^k{j-1\choose k}[x^{i-2j+1+k}](1+3x+9x^2+\ldots)^{j-k}(1+x+3x^2+9x^2+\ldots)\\[3ex]
&=\sum_{k=0}^{j-1}3^k{j-1\choose k}([x^{i-2j+1+k}](1+3x+9x^2+\ldots)^{j-k}+[x^{i-2j+k}](1+3x+9x^2+\ldots)^{j-k+1})\\[3ex]
&=\sum_{k=0}^{j-1}3^k{j-1\choose k}(3^{i-2j+1+k}{i-j\choose j-k-1}+3^{i-2j+k}{i-j\choose j-k})\\[3ex]
&=\sum_{k=0}^{j-1}3^{i-2j+2k}{j-1\choose k}(3{i-j\choose j-k-1}+{i-j\choose j-k}).\\[3ex]
\end{aligned} g ( x , y ) [ y j ] g ( x , y ) G i , j = 1 − 3 x − 3 x y + 8 x 2 y 1 − 2 x y = 1 − 3 x 1 ⋅ 1 − 1 − 3 x 3 x − 8 x 2 y 1 − 2 x y , = 1 − 3 x 1 ⋅ ( 1 − 3 x 3 x − 8 x 2 ) j − 1 ( 1 − 3 x 3 x − 8 x 2 − 2 x ) = 1 − 3 x 1 ⋅ ( 3 x + 1 − 3 x x 2 ) j − 1 ( 1 − 3 x x − 2 x 2 ) = x j ⋅ 1 − 3 x 1 ⋅ ( 3 + 1 − 3 x x ) j − 1 ( 1 + 1 − 3 x x ) , = [ x i ] [ y j ] g ( x , y ) = [ x i − j ] ( 1 + 3 x + 9 x 2 + … ) ( 3 + x + 3 x 2 + 9 x 3 + … ) j − 1 ( 1 + x + 3 x 2 + 9 x 3 + … ) = k = 0 ∑ j − 1 3 k ( k j − 1 ) [ x i − j ] ( 1 + 3 x + 9 x 2 + … ) ( x + 3 x 2 + 9 x 3 + … ) j − 1 − k ( 1 + x + 3 x 2 + 9 x 3 + … ) = k = 0 ∑ j − 1 3