The number of convex polyominoes and the generating function of Jacobi polynomials (Q2489952): Difference between revisions

A polyomino is a connected union of squares in the plane whose vertices are lattice points such that the interior is also connected. A polyomino is called convex if its intersection with any horizontal or vertical line is either empty or a line segment. Any convex polyomino has a minimal bounding rectangle whose perimeter is the same as that of the polyomino. \textit{M. O. Delest} and \textit{G. Viennot} [Theoret. Comput. Sci. 34, 169--206 (1984; Zbl 0985.68516)] found a generating function for convex polyominoes by perimeter and derived that the number of convex polyominoes with perimeter \(2n+8\) is \((2n+11)4^n-4(2n+1){2n \choose n}\). An elementary proof of this result has been found by \textit{D. S. Kim} [Discrete Math. 70, 47--51 (1988; Zbl 0723.05043)]. I. Gessel refined the formula above showing that the number of convex polyominoes with an \((n+1)\times (m+1)\) bounding rectangle is \[ {m+n+mn\over m+n} {2m+2n\choose 2m}-{2mn\over m+n} {m+n\choose m}^2. \] The present paper shows that Kim's elementary approach can be used to prove the displayed formula, and the resulting identities of binomial coefficients are related to the generating function of Jacobi polynomials.