Combinatorial Enumeration of Partitions of a Convex Polygon

Dong Zhang and Dongyi Wei Peking University Beijing 100871 P. R. China

                dongzhang@pku.edu.cn
                   jnwdyi@163.com

Demin Zhang Xinxiang Henan P. R. China

                 winlxm1972@sina.cn

Abstract We establish a class of polynomials on convex polygons, which provides a new counting formula to all partitions of a convex polygon by non-intersecting diagonals.

1 Introduction

Counting partitions of a convex polygon of a specified type by using its non-intersecting diagonals is a problem which can go back to Euler, Catalan, Cayley [1] and Przytycki and Sikora [2]. Recently, Floater and Lyche [3] showed a way to enumerate all partitions of a convex polygon of a certain type as follows.

Proposition 1 (Floater, Lyche [3]). A partition of a convex (n + 1)-gon is said to be of type b = (b_{2}, b_{3}, …, b_{n}) if it contains b_{2} triangles, b_{3} quadrilaterals, and so on, and in general b_{i} (i+1)-gons. Then the number of partitions of a convex (n+1)-gon of type b = (b_{2}, b_{3}, …, b_{n}) with b_{2} + b_{3} + ⋯ + b_{n} = k and 2b_{2} + 3b_{3} + ⋯ + nb_{n} = n + k − 1, is

C(b) = \frac{(n + k − 1)(n + k − 2) ⋯ (n + 1)}{b_{2}!b_{3}! ⋯ b_{n}!}.

Inspired by Lee’s result [4], Shephard [5] got an interesting equality on convex polygons with n + 2 sides as follows.

Proposition 2 (Lee [4], Shephard [5]). Given a (n+2)-gon, let d_{1} be the number of diagonals, d_{2} be the number of disjoint pairs of diagonals, and, in general, d_{i} be the number of sets of i diagonals of the polygon which are pairwise disjoint. Then we have

d_{1} − d_{2} + d_{3} − ⋯ + (−1)^{n}d_{n−1} = 1 + (−1)^{n}

The original proof [4] of Proposition 2 is very complicated. We will provide a rather simple proof in the last part.

We organize this paper as follows. Section 2 shows the main result (Theorem 5) via the properties of a derivation acting on a special polynomial algebra. In Section 3, we prove Propositions 1 and 2 by our main result.

2 Main results

We call a vector space A := (A, +) an algebra over the real field ℝ, if A possesses a bilinear product satisfying (ab)c = a(bc), (a + b)(c + d) = ac + bc + ad + bd and (λμ)(ab) = (λa)(μb), for all λ, μ ∈ ℝ, a, b, c, d ∈ A. Recall that a linear map D mapping A into itself is called a derivation if D(xy) = (Dx)y + x(Dy) for all x, y ∈ A.

Definition 3. Let A be a polynomial algebra generated by {x_{i} : i ∈ ℕ^{+}}, i.e., the collection of the polynomials with the form ∑_{k=1}^{m} ∑_{i_{1},...,i_{k}∈ℕ^{+}} a_{i_{1},...,i_{k}}x_{i_{1}} ⋯ x_{i_{k}}, where a_{i_{1},...,i_{k}} ∈ ℝ and m ∈ ℕ^{+}. For given y_{i} ∈ A, i ∈ ℕ^{+}, let D′ : {x_{i} : i ∈ ℕ^{+}} → A be such that x_{i} ↦ y_{i}, i ∈ ℕ^{+}. The unique extension of D′ to A via Leibniz’s law determines a derivation D on A, which is called the derivation defined by D′.

Lemma 4. Let A be a polynomial algebra generated by {X_{1}, X_{2}, …, X_{n}, …}. Assume D is a derivation with action defined by

DX_{n} = (an + b) ∑_{i=1}^{n−1} X_{i}X_{n−i}, n ≥ 2, DX_{1} = 0,  (1)

where a and b are given real numbers. Then we have

D^{m}X_{n} = \frac{∏_{k=1}^{m}(2an + (k + 1)b)}{m + 1} ∑_{i_{1}+i_{2}+···+i_{m+1}=n} X_{i_{1}}X_{i_{2}} ⋯ X_{i_{m+1}}.  (2)

Proof. Let X(t) = ∑_{i≥1} X_{i}t^{i} be a generating function. It follows from

X(t)^{2} = ∑_{n≥2} (∑_{i=1}^{n−1} X_{i}X_{n−i}) t^{n}

that

(at\frac{d}{dt} + b) X(t)^{2} = ∑_{n≥2} (∑_{i=1}^{n−1} X_{i}X_{n−i}) (at\frac{d}{dt} + b) t^{n} = ∑_{n≥2} (∑_{i=1}^{n−1} X_{i}X_{n−i}) (an + b)t^{n}

= ∑_{n≥1}(DX_{n})t^{n} = DX(t).

Similarly, the statement (2) becomes

D^{m}X = \frac{1}{m + 1} ∏_{i=1}^{m} (2at\frac{d}{dt} + (i + 1)b) X^{m+1},  (3)

where X := X(t). It is evident that (3) holds for m = 1. Assume that (3) holds for m = k. Now we show that (3) holds for m = k + 1. In fact, together with (3) for m = k and the fact

DX^{m} = mX^{m−1}DX = mX^{m−1} (at\frac{d}{dt} + b) X^{2}

= 2amX^{m}t\frac{d}{dt}X + bmX^{m+1}

= \frac{m}{m + 1} (2at\frac{d}{dt} + (m + 1)b) X^{m+1},

we immediately obtain

D^{k+1}X = D(D^{k}X) = D (\frac{1}{k + 1} ∏_{i=1}^{k} (2a\frac{d}{dt} + (i + 1)b) X^{k+1})

= \frac{1}{k + 1} ∏_{i=1}^{k} (2at\frac{d}{dt} + (i + 1)b) DX^{k+1}

= \frac{1}{k + 1} ∏_{i=1}^{k} (2at\frac{d}{dt} + (i + 1)b) \frac{k + 1}{k + 2} (2at\frac{d}{dt} + (k + 2)b) X^{k+2}

= \frac{1}{k + 2} ∏_{i=1}^{k+1} (2at\frac{d}{dt} + (i + 1)b) X^{k+2}.

Therefore, by mathematical induction, we have completed the proof.

We call a strictly convex polygon with n + 2 sides a (n + 2)-gon, denoted by X_{n}, where n ∈ ℕ^{+}. Given an integer n ≥ 2, we use Δ to denote a set of diagonals of X_{n} which are pairwise disjoint. It should be noted that a Δ with m elements divides X_{n} into m+1 convex polygons, X_{i_{1}}, X_{i_{2}}, …, X_{i_{m}} and X_{i_{m+1}} for some i_{1}, i_{2}, …, i_{m} and i_{m+1} in {1, 2, …, n}. The set of such convex polygons is said to be a partition of the original convex polygon. We symbolically set f(Δ) = ∏_{j=1}^{m+1} X_{i_{j}} and Card Δ = m. Figure 1 provides two examples of X_{n} for n = 8 and n = 10, respectively.

Figure 1: The left figure shows X_{8} with Δ = {AD, AG, DG} and the corresponding partition {ABCD, DEF G, AGHIJ, ADG}, where Card Δ = 3, f(Δ) = X_{1}X_{2}X_{2}X_{3}. The right figure shows X_{10} with Δ = {AE, AJ, EJ, EG, GJ} and the corresponding partition {ABCDE, EF G, GHIJ, AJKL, EGJ, AEJ}, where Card Δ = 5, f(Δ) = X_{1}X_{1}X_{1}X_{2}X_{2}X_{3}.

Theorem 5. Given n ∈ ℕ^{+} and m ∈ ℕ, we have

∑_{Card Δ=m} f(Δ) = \frac{1}{m + 1}\binom{n + m + 1}{m} ∑_{i_{1}+i_{2}+···+i_{m+1}=n} X_{i_{1}}X_{i_{2}} ⋯ X_{i_{m+1}}.  (4)

Proof. Consider partitions of X_{n} with m diagonals, in which the diagonals are labelled, say with integers 1, 2, ⋯, m. Then the derivation D is an operator that acts as an analogue combinatorial device for splitting the polygon on a labelled diagonal; consequently, D^{m} is an operator that splits the polygon (with m diagonals) into m + 1 polygons. We then divide by m! to remove the effect of labelling the diagonals, so that \frac{D^{m}}{m!} is the operator that produces the counting series for partitioning a polygon into m + 1 parts.

Next, we calculate DX_{n}. Notice that there are n − 1 diagonals starting from a vertex, and each diagonal divides X_{n} into two parts. So we have n − 1 ways to divide X_{n}, which can be expressed as X_{1}X_{n−1} +X_{2}X_{n−2} +⋯+X_{n−1}X_{1} by using our notation. Since X_{n} has n+2 vertices, the whole set of partitions of X_{n} can be written as (n + 2) ∑_{i=1}^{n−1} X_{i}X_{n−i}. However, each diagonal has two ends, and will be counted twice. Consequently, we should divide it by 2, and get DX_{n} = \frac{n+2}{2} ∑_{i=1}^{n−1} X_{i}X_{n−i}. Taking a = \frac{1}{2} and b = 1 in Lemma 4, we have

∑_{Card Δ=m} f(Δ) = \frac{1}{m!}D^{m}X_{n} = \frac{1}{m + 1}\binom{n + m + 1}{m} ∑_{i_{1}+i_{2}+···+i_{m+1}=n} X_{i_{1}}X_{i_{2}} ⋯ X_{i_{m+1}}.

3 Applications

A result about partitioning polygons is as follows.

Corollary 6. Given i_{1}, i_{2}, …, i_{m+1} with i_{1}+i_{2}+⋯+i_{m+1} = n. Then the number of different ways of cutting X_{n} into sub-polygons X_{i_{1}}, X_{i_{2}}, …, X_{i_{m+1}} by diagonals is \frac{S}{m+1} \binom{n+m+1}{m}, where S is the number of permutations of i_{1}, i_{2}, …, i_{m+1}.

Proof. By Theorem 5, we obtain that there exist \frac{S}{m+1} \binom{n+m+1}{m} ways to divide X_{n} into X_{i_{1}}, X_{i_{2}}, …, X_{i_{m+1}}, where S is the number of permutations of i_{1}, i_{2}, …, i_{m+1}.

One can easily verify that Proposition 1 is equivalent to Corollary 6.

Example 7 (Catalan numbers). Let m = n − 1. Then i_{1} = i_{2} = ⋯ = i_{m+1} = 1 is the only positive integer solution of i_{1} + i_{2} + ⋯ + i_{m+1} = n. Hence S = 1, and we get the Catalan numbers \frac{1}{n} \binom{2n}{n−1} = \frac{1}{n+1} \binom{2n}{n}.

Next we give a new proof for Proposition 2 by using Theorem 5 and the residue theorem.

Proof of Proposition 2. Consider X_{n}. Notice that the number of positive integer solutions

of i_{1} + i_{2} + ⋯ + i_{m+1} = n is \binom{n−1}{m}. By Theorem 5, there are ∑_{i_{1}+i_{2}+···+i_{m+1}=n} \frac{1}{m+1} \binom{n+m+1}{m}

monomials on the right-hand side of (4). Thus we get d_{m} = \frac{1}{m+1} \binom{n−1}{m}\binom{n+m+1}{m}, and then

∑_{k=1}^{n−1}(−1)^{k}d_{k} = ∑_{k=1}^{n−1}(−1)^{k−1} \frac{\binom{n−1}{k}}{k + 1}\binom{n + k + 1}{k}

= ∑_{k=1}^{n−1}(−1)^{k−1} \frac{\binom{n}{k+1}}{n}Res (\frac{(1 + u)^{n+k+1}}{u^{k+1}} , 0)

= \frac{1}{n}Res ((1 + u)^{n} ∑_{k=1}^{n−1}(−1)^{k−1}\binom{n}{k + 1}\frac{(1 + u)^{k+1}}{u^{k+1}} , 0)

= \frac{1}{n}Res ((1 + u)^{n} ((1 − \frac{u + 1}{u})^{n} − (1 − n\frac{u + 1}{u})) , 0)

= \frac{1}{n}Res ((1 + u)^{n} ((−\frac{1}{u})^{n} − 1 + n\frac{u + 1}{u}) , 0)

= \frac{1}{n} ((−1)^{n}Res (\frac{(1 + u)^{n}}{u^{n}} , 0) + nRes (\frac{(1 + u)^{n+1}}{u} , 0))

= \frac{1}{n} ((−1)^{n}\binom{n}{n − 1} + n · 1)

= 1 + (−1)^{n},

where Res(f(u), 0) means the residue of function f(u) at u = 0.

Remark 8. Proposition 2 also follows immediately from the hypergeometric summation formula, by

∑_{k=1}^{n−1}(−1)^{k}d_{k} = ∑_{k=1}^{n−1}(−1)^{k−1} \frac{\binom{n−1}{k}}{k + 1}\binom{n + k + 1}{k} = \frac{1}{n} (n − ∑_{i=1}^{n−1} \binom{n}{n − k − 1}\binom{−n − 2}{k})

= \frac{1}{n} (n − \binom{−2}{n − 1}) = \frac{1}{n}(n + (−1)^{n}n) = 1 + (−1)^{n}.

4 Acknowledgments

The authors thank the anonymous referee for his/her careful reading and helpful comments. The proofs of Lemma 4 and Theorem 5, were effectively simplified by the referee. Moreover, he/she also gave the above remark.

References

[1] A. Cayley, On the partition of a polygon, Proc. Lond. Math. Soc. (3) 22 (1890), 237–262.

[2] J. H. Przytycki and A. S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A 92 (2000), 68–76.

[3] M. S. Floater and T. Lyche, Divided differences of inverse functions and partitions of a convex polygon, Math. Comp. 77 (2008), 2295–2308.

[4] C. W. Lee, The associahedron and triangulations of the n-gon, European J. Combin. 10 (1989), 551–560.

[5] G. C. Shephard, A polygon problem, Amer. Math. Monthly 102 (1995), 505–507.

2010 Mathematics Subject Classification: Primary 51E12; Secondary 05A15, 13N15, 16W25. Keywords: polygon, diagonal, combinatorial enumeration, derivation, generating function.

(Concerned with sequence \underline{A000108}.)

Received April 9 2014; revised versions received April 26 2014; February 4 2015; March 14 2015; July 29 2015; August 6 2015. Published in Journal of Integer Sequences, August 18 2015.

Return to Journal of Integer Sequences home page.