10.2 Two-variable examples

Consider selecting $r$ integers from $n$ such that no two are successive. Let these be . Then $x_1\ge 1$, $x_i-x_{i-1}\ge 2,2\le i\le r$. Setting $y_1=x_1,y_i=x_i-x_{i-1}-1$, $y_{r+1}=n-x_r+1$, we have that $y_1,\mathrm{\dots },y_{r+1}$ form a partition of $n-r+2$. Thus the number of solutions are $\left(\genfrac{}{}{0pt}{}{n-r+1}{r}\right)$.

We now give a generating function approach. It is a 2-parameter problem. Let $a(r,n)$ denote the number of solutions. Set $a(0,0)=1$. Divide the solutions into $x_1=1$ and $x_1>1$. If $x_1=1$, then $x_2\ge 3$ and the rest of the sequence is from $3,\mathrm{\dots },n$ satisfying original condition. So there are $a(r-1,n-2)$ many solutions with $x_1=1$. Now if $x_1>1$, then $x_i-1$’s form a solution for $r,n-1$. Thus such solutions are $a(r,n-1)$. So

$$a(r,n)=a(r,n-1)+a(r-1,n-2),n\ge 2.$$

Easy to derive solution from this recursion too. But what about generating functions ?

Set $f(x,y)={\sum }_{n=0}{\sum }_{r=0}a(r,n)x^n{y}^r$. Trivially $a(0,1)=a(1,1)=1$ and $a(r,n)=0$ if $r>n$ and even $r=n$ if $n\ge 2$. Also set $a(r,n)=0$ if or . Thus,

	$f(x,y)$	$=1+x+xy+{\displaystyle \sum _{n=2}}{\displaystyle \sum _{r=0}}a(r,n-1)x^n{y}^r+{\displaystyle \sum _{n=2}}{\displaystyle \sum _{r=0}}a(r-1,n-2)x^n{y}^r$
		$=1+x+xy+x{\displaystyle \sum _{n=2}}{\displaystyle \sum _{r=0}}a(r,n-1)x^{n-1}{y}^r+x^{2}y{\displaystyle \sum _{n=2}}{\displaystyle \sum _{r=0}}a(r-1,n-2)x^{n-2}{y}^{r-1}$
		$=1+x+xy+x(f(x,y)-1)+x^{2}yf(x,y).$

This gives that $f(x,y)=\frac{1+xy}{1-x-x^{2}y}$.

Let $a_n$ be the number of horizontally convex (HC) polyominoes of area $n$. This consists of layers of squares such that successive layers overlap with $n$ squares in total. Let $a_n$ be the number of $n$-HC polyominoes.

Let $a(m,n)$ be number of HC polyominoes with $m$ cells at the bottom. Then $a(n,n)=1$, $a(m,n)=0$ for and $a(m,0)=0$. Suppose there are $l$ cells in the second layer, there are $(m+l-1)$-ways in which these cells can be placed on top of the first layer such that they overlap. This reasoning gives rise to the following recursion.

$$a(m,n)=\sum _{l=1}^{\mathrm{\infty }}(m+l-1)a(l,n-m),n>m.$$

Define $F(x,y)={\sum }_{m,n}{a}_{m,n}{x}^n{y}^m.$ Then $F(x,1)=f(x)$. Set $g(x)={\sum }_{m,n}m{a}_{m,n}{x}^n={(\frac{\partial F}{\partial y})}_{y=1}.$ Thus we derive that

	${\displaystyle \sum _{n>m,l}}la(l,n-m)x^n{y}^m$	$={\displaystyle \sum _m}{(xy)}^m{\displaystyle \sum _{n,l}}l{a}_{l,n-m}{x}^{n-m}={\displaystyle \frac{xy}{1-xy}}g(x);$
	${\displaystyle \sum _{n>m,l}}(m-1)a(l,n-m)x^n{y}^m$	$={\displaystyle \sum _m}(m-1){(xy)}^m{\displaystyle \sum _{n,l}}l{a}_{l,n-m}{x}^{n-m}={\displaystyle \sum _m}(m-1){(xy)}^{m}f(x)={\displaystyle \frac{{(xy)}^2}{{(1-xy)}^2}}f(x)$

So

$$F(x,y)=\sum _n{a}_{n,n}{(xy)}^n+\sum _{n>m}{a}_{n,m}{x}^n{y}^m=\frac{xy}{1-xy}+\frac{{(xy)}^2}{{(1-xy)}^2}f(x)+\frac{xy}{1-xy}g(x).$$

Differentiating w.r.t. $y$ and taking $y=1$ gives,

$$g(x)=\frac{x}{{(1-x)}^2}+\frac{2x^2}{{(1-x)}^3}f(x)+\frac{x}{{(1-x)}^2}g(x).$$

Find $g(x)$ and substitute in $F(x,y)$ and set $y=1$. Then we derive that

$$f(x)=\frac{x{(1-x)}^3}{1-5x+7x^2-4x^3}.$$

Thus $(1-5x+7x^2-4x^3)f(x)=x{(1-x)}^3$. Matching up coefficients of $x^n$ for $n\ge 5$ on both sides, we have

$$a_n-5a_{n-1}+7a_{n-2}-4a_{n-3}=0.$$