Find generating function for the pattern

Question

Denote $p(n)$ is the numbers of any size rectangle count on these pattern

Problem :

Find generating function that $p(n)$ is coefficient of function.

I try to read out for some $p(n)$ and get

$p(1)=1$

$p(2)=2\binom{3}{2}-1 = 5$

$p(3)=(2\binom{4}{2}-1) + \binom{3}{2}^{2} - (2\binom{3}{2}-1) = 15$

$p(4)= (2\binom{5}{2}-1) + (2\binom{3}{2}\binom{4}{2}-\binom{3}{2}^{2}) - (2\binom{4}{2}-1) = 35$ and so on

We found that $p(n) = \frac{1}{3}(2n^{3}-3n^{2}+7n-3)$

The problem is I cannot find a generating function that has $p(n)$ as a coefficient.

Please give me some hint or any advice. Thank you and I appreciate for any helps.

Answer 1

We derive a recurrence relation for $p(n), n\geq 1$ and calculate from it the generating function \begin{align*} P(x)&=\sum_{j=1}^\infty p(j)x^j\\ &=p(1)x+p(2)x^2+p(3)x^3+p(4)x^4\cdots\\ &=x+5x^2+15x^3+35x^4+\cdots \end{align*}

In order to go from $p(n-1)$ to $p(n)$ it is convenient to add squares at the diagonal. See the graphic below.

                               

In each step we add a new square at the diagonal. The rectangles we count in one step do not interfere with rectangles from former steps, since the new square is always part of these rectangles. In fact this way we partition the rectangles we count when going from $p(n-1)$ to $p(n)$, so that we can simply sum them up. In general we have for $n\geq 1$: \begin{align*} \color{blue}{p(n)}&\color{blue}{=p(n-1)+\sum_{j=1}^{n}j(n+1-j)\qquad\qquad n\geq 2}\tag{1}\\ \color{blue}{p(1)}&\color{blue}{=1} \end{align*}

We simplify (1) by using the summation formulas $$\sum_{j=1}^nj=\frac{1}{2}n(n+1), \qquad\qquad\sum_{j=1}^nj^2=\frac{1}{6}n(n+1)(2n+1)$$ and obtain \begin{align*} \color{blue}{p(n)}&\color{blue}{=p(n-1)+\frac{1}{6}n(n+1)(n+2)\qquad\qquad n\geq 2}\tag{2}\\ \color{blue}{p(1)}&\color{blue}{=1} \end{align*}

We obtain from (2) the generating function $P(x)$ as follows \begin{align*} P(x)&=\sum_{n=1}^\infty p(n)x^n=x+\sum_{n=2}^\infty p(n)x^{n}\\ &=x+\sum_{n=2}^\infty \left(p(n-1)+\frac{1}{6}n(n+1)(n+2)\right)x^n\\ &=x+\sum_{n=1}^\infty p(n)x^{n+1}+\frac{1}{6}x\sum_{n=2}^\infty n(n+1)(n+2)x^{n-1}\\ &=x+\sum_{n=1}^\infty p(n)x^{n+1}+\frac{1}{6}xD_x\sum_{n=2}^\infty (n+1)(n+2)x^{n}\tag{3}\\ &=x+\sum_{n=1}^\infty p(n)x^{n+1}+\frac{1}{6}xD_x^2\sum_{n=2}^\infty(n+2)x^{n+1}\\ &=x+xP(x)+\frac{1}{6}xD_x^3\sum_{n=2}^\infty x^{n+2}\tag{4}\\ &=x+xP(x)+\frac{1}{6}xD_x^3\frac{x^4}{1-x}\\ &=x+xP(x)+\frac{x}{(1-x)^4}-x\\ \color{blue}{P(x)}&\color{blue}{=\frac{x}{(1-x)^5}}\tag{5} \end{align*}

In (3) we use the differential operator $D_x=\frac{d}{dx}$ and continue successively till we get a geometric series in (4). It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$.

We finally obtain from (5) for $n\geq 1$ \begin{align*} [x^n]P(x)&=[x^n]\frac{x}{(1-x)^5}\\ &=[x^{n-1}]\sum_{j=0}^\infty\binom{-5}{j}(-x)^j\\ &=[x^{n-1}]\sum_{j=0}^\infty\binom{j+4}{4}x^5\\ &=\binom{n+3}{4}\\ &\,\,\color{blue}{=\frac{1}{24}n(n+1)(n+2)(n+3)} \end{align*}

Answer 2

Hint: $$p(n) = 1 + 2 + 3 + \ldots + n = \sum_{i = 1}^n i = \frac{n(n + 1)}{2},$$ hence you're looking for $$f(x) = \sum_{i = 0}^\infty \frac{i(i + 1)}{2} x^i$$