A Famous Identity of Hajós in Terms of Sets

Rui Duarte

Center for Research and Development in Mathematics and Applications

Department of Mathematics

University of Aveiro

3810-193 Aveiro

Portugal

rduarte@ua.pt

António Guedes de Oliveira CMUP and Mathematics Department

Faculty of Sciences University of Porto

4169-007 Porto

Portugal

agoliv@fc.up.pt

Abstract

By considering the famous identity on the convolution of the central binomial coefficients

∑_{i+j=n} \binom{2i}{i}\binom{2j}{j} = 4^{n}

in terms of pairs of ℓ-subsets of 2ℓ-sets, we obtain a new bijective proof and new identities that can be seen as refinements.

1 Introduction

Thirty years ago, at the end of a captivating article on “natural interpretations” of special identities dealing with natural numbers, Marta Sved confesses herself defeated by the following identity

∑_{i+j=n} \binom{2i}{i}\binom{2j}{j} = 4^{n} ,  (1)

which she could not prove combinatorially, and “invites the reader to try his bit” [6]. Afterwards, in a “recount of the letters” received “offering solutions to the problem”, she tells us that Paul Erdős “was quick to point out to [her] that Hungarian mathematicians tackled it in the thirties: P. Veress proposing and G. Hajós solving it” [7] and that “all solutions are based, with some variations, on the count of lattice paths, or equivalently (1, 0) sequences”.

In fact, it is well-known that \binom{2ℓ}{ℓ} counts the number of paths from (0, 0) to (ℓ, ℓ), where ℓ is a positive integer and each step in the path is of the form (1, 0) or (0, 1) (see, for instance, the book of Stanley [5, Exercise 1.3]). But there is another way of looking at this identity, perhaps even more natural, where \binom{2ℓ}{ℓ} really (and naturally) stands for the number of ℓsubsets of a 2ℓ-set, and so where in the left-hand side of (1) we count the pairs (A, B) such that A is an i-subset of {1, …, 2i} and B is a j-subset of {1, …, 2j}.

In the meantime, different types of proofs appeared [1, 2, 3]. Yet, after thirty years, we believe we present here the first bijective proof of (1) not based on lattice paths. Instead, it is based on properties of these pairs; and it is of algorithmic nature.

We represent such pairs graphically. For example, we have the representation

R = 1 O O O 5 1 X X X 5 6 6 7 O O 10 X X 9 X 11 12 for ({2, 3, 4, 8, 9}, {2, 3, 4, 7, 8, 10}) ,

formed by a 5-subset of {1, …, 10} and a 6-subset of {1, …, 12}. In this example, there are two “towers” with two symbols O, in the third and fourth column of the left-hand side, and two “towers” with two symbols X, in the second and fourth column of the six remaining

columns. If there were no towers, all columns would be of one of four types ( O , O ,

X or X ). But not all the 4^{n} choices of n of such columns would occur, since in our case

they are ordered, meaning that any column with an O must precede any column with an X.

The idea behind our proof is to show that there are exactly as many ordered configurations with towers as there are configurations without towers where at least one column marked with an X precedes one column marked with an O. More precisely, we build a bijection φ that maps an ordered configuration with k towers to a configuration without towers where exactly k columns marked with one X precede a column with one O.

The number of configurations with p columns and i towers is 2^{p−2i}\binom{p}{i}\binom{p−i}{i}. When p ∈ ℕ_{0} and i is an integer with 0 ≤ 2i ≤ p, these numbers form the triangle read by rows in sequence \underline{A051288} of [8], whereas the triangle T defined by

T (p, i) = \binom{p}{i}\binom{p − i}{i} ,

for p ∈ ℕ_{0} and i ≤ p, is read by rows in \underline{A089627}. The first eleven rows of T (for n = 0, 1, …, 10) are as follows:

1

1, 0
1, 2,  0
1, 6,  0,  0
1, 12,  6,  0,  0
1, 20, 30,  0,  0, 0
1, 30, 90, 20,  0, 0, 0
1, 42, 210, 140,  0, 0, 0, 0
1, 56, 420, 560, 70, 0, 0, 0, 0
1, 72, 756, 1680, 630, 0, 0, 0, 0, 0
1, 90, 1260, 4200, 3150, 252, 0, 0, 0, 0, 0

As a consequence of our bijection, we shall see in Corollary 8 that, for any fixed natural number n, if we define sequence A_{p} as the convolution of sequence (T (p, i))_{i∈ℕ_{0}} with (T (n − p, i))_{i∈ℕ_{0}}, the sum S_{n} of A_{p} for 0 ≤ p ≤ n is row n of \underline{A229032} of [8], given by S_{n}(k) = 4^{k}\binom{n+1}{2k+1}. In other words, if 0 ≤ 2k ≤ n,

∑_{p=0}^{n} ∑_{i=0}^{k} \binom{p}{i}\binom{p − i}{i}\binom{n − p}{k − i}\binom{n − p − k + i}{k − i} = 4^{k}\binom{n + 1}{2k + 1}.  (2)

Note that if T (n, k) is defined as in \underline{A085841} of [8] and n is even then S_{n}(k) = T (n/2, k). On the other hand, if T (n, k) is defined as in \underline{A105070} then S_{n}(k) = 2^{k}T (n + 1, k).

Example 1 (n = 10).

\begin{matrix}A_{0} = & ( 1, & 90, & 1260, & 4200, & 3150, & 252, & 0, & ⋯) \\ A_{1} = & ( 1, & 72, & 756, & 1680, & 630, & 0, & 0, & ⋯) \\ A_{2} = & ( 1, & 58, & 532, & 1400, & 1190, & 140, & 0, & ⋯) \\ A_{3} = & ( 1, & 48, & 462, & 1400, & 840, & 0, & 0, & ⋯) \\ A_{4} = & ( 1, & 42, & 456, & 1280, & 780, & 120, & 0, & ⋯) \\ A_{5} = & ( 1, & 40, & 460, & 1200, & 900, & 0, & 0, & ⋯) \\ A_{6} = & ( 1, & 42, & 456, & 1280, & 780, & 120, & 0, & ⋯) \\ A_{7} = & ( 1, & 48, & 462, & 1400, & 840, & 0, & 0, & ⋯) \\ A_{8} = & ( 1, & 58, & 532, & 1400, & 1190, & 140, & 0, & ⋯) \\ A_{9} = & ( 1, & 72, & 756, & 1680, & 630, & 0, & 0, & ⋯) \\ A_{10} = & ( 1, & 90, & 1260, & 4200, & 3150, & 252, & 0, & ⋯) \\ S_{10} = & (11, & 660, & 7392, & 21120, & 14080, & 1024, & 0, & ⋯) \end{matrix}

2 The main theorem

Let [0] = ∅, and [n] = {1, 2, …, n} for a positive integer n. For every pair (A, B) such that A is an i-subset of [2i], B is a j-subset of [2j], and i + j = n, represent each element of A by a naught (O) in a 2 × i rectangle of cells numbered from left to right and from top to bottom, and each element of B similarly by a cross (X) in a 2 × j rectangle. Finally, join the rectangles in a 2 × n rectangle R. Note that we consider also the cases with i = 0 or j = 0, where the respective symbol does not appear.

Definition 2. A 2 × n rectangle, where exactly n of the 2n cells are marked with one of two symbols, O and X, with the restriction that columns with both symbols do not exist, is called a configuration (or n-configuration). The columns with no marked cells are empty columns and the columns with two marked cells are towers. Both are called even columns and the columns with exactly one marked cell are called odd. We say that a pair of consecutive columns with cells marked X and O, respectively, is a descent. An ordered configuration C of type (i, j) is the concatenation of an i-configuration with no cells marked with an X with a j-configuration with no cells marked with an O, where i and j are nonnegative integers. The i-configuration is the O-region of C and the j-configuration is the X-region. Finally, the set of ordered n-configurations is denoted by O_{n} and the set of n-configurations without towers is denoted by N T_{n}.

Note that the ordered configurations are exactly the configurations that represent the pairs (A, B) as defined above. By definition, the number of towers and the number of empty columns in each of the two original subrectangles are equal. Since there are four types of odd columns, |N T_{n}| = 4^{n} and (1) states that |O_{n}| = |N T_{n}|.

In this article we define (recursively) a bijection φ : O_{n} → N T_{n} that leaves the ordered configurations without towers invariant. More precisely, we prove that if R is an ordered configuration with k towers, then φ(R) is a configuration without towers with exactly k descents.

The main idea behind the proof is simple: suppose that k = 1, so that we have only one tower and one empty column or one empty column and one tower, in positions ℓ and m, say, respectively (ℓ < m), necessarily both in the O-region or both in the X-region, and possibly some odd columns between them, also necessarily with the symbol of the region. We want to transform R into φ(R) where there is exactly one descent, in a way that will allow us to retrieve R.

The columns with position p ∈ {ℓ, ℓ + 1, …, m} form the coding region. We assume that the cells outside this region will not be changed. Note that we must encode, first, the symbol of the tower/region; second, whether the tower precedes the empty column or the empty column precedes the tower; third, the values of ℓ and m; and last, the position, above or below, of the marked cell in each odd column of the coding region. For the first two requirements, in first analysis we follow the scheme below (see rules (a)–(c) of Definition 4) for replacing the pair tower/empty column by the descent

φ : O O  ↦ X O ;  O O ↦ O X ; X X  ↦ X O ;  X X ↦ X O . (3)

Then, in the coding region, after encoding, before the cross of the descent there should only be crosses, and after the naught only naughts. But note that in the O-region there might also be naughts after the coding region, and that in the X-region there might also be crosses before it. Hence, we must define two procedures, ϕ_{O} and ϕ_{X}, where the descent will occupy the last cells of the coding region if the original cells are naughts, and the first ones if they are crosses. This meets the third requirement. Finally, in both cases, we could simply keep the positions of the odd cells in their columns in the coding region, except that this might change our encoding of the descent. In this case we should reverse these positions (see rule 1(f) and 1(g) of Definition 4).

It is easy to see that these rules, formalized below, are sufficient for encoding the cases where the towers and the empty columns can be organized in consecutive pairs tower/empty column or empty column/tower.

But we may have, for instance, _{O O}^{O O O} . There is a beautiful solution for encod-

ing these configurations, where we first look only at the even columns and apply recursively the previous procedure. Consider, for a k-configuration C, the 2k-configuration formed only of odd columns D, where each column of C of form \frac{X}{Y} is “expanded” in D so as to obtain \frac{X}{X} \frac{Y}{Y} . Let us say that D is “compressed” in C. Then, C is a configuration without towers if and only if in D the even columns, if any, occur in consecutive pairs tower/empty column or empty column/tower. This means that we may apply recursively the previous procedure to any configuration R. First, consider only the even columns of R, forming S, say. S is compressed in S′. Suppose that now we may apply the previous procedure to S′, being its even columns already organized in consecutive pairs tower/empty column or empty column/tower, and that, by doing it, we obtain T′. Now, expand the columns of T′ in T as before and replace every odd column of R by the corresponding column of T. Finally, use the former procedure throughout the new configuration, coding zone by coding zone. For instance,

O O O O  ↦ O O  ↦^{by(3)} X O ↦  X  O X  O
O O O O O  ↦  X O  O X  O ↦^{by(3)} X O O  O X

We formalize all these concepts in the following definitions.

Definition 3. Given an n-configuration R with k towers, let R′ be the 2k-configuration obtained from R by removing all the odd columns. For a 2k-configuration S without odd columns, if we delete one of the two equal rows of S and then rearrange the remaining 2k cells by placing, for every 1 ≤ i ≤ k, cell 2i under cell 2i − 1, we obtain a k-configuration S_{↓} called the compression of S. The depth of R, d(R), is defined recursively by d(R) = 0 if R has no towers, and by d(R) = d(R′_{↓}) + 1 otherwise. In the opposite direction, given a k-configuration T, we form a string of 2k cells by reading the cells of T top-to-bottom, left-to-right. Then we form a 2k-configuration, called the expansion of T and denoted T^{↑}, by taking this string as its first and its second row.

For example, for the 11-configuration R above, R′ = 1 O O 4 X X 3 4 O O X X , R′_{↓} =

1 O X 3 O 4 X 4 and (R′_{↓})′_{↓} = ^{X} . On the other side, X O ^{↑} = X  O X  O . Note

that all these three last operations, when applied to an ordered configuration, still give an ordered configuration. Note also that we have d(R) = 1 exactly in the cases where, as before, the towers and the empty columns can be organized in consecutive pairs tower/empty

column or empty column/tower. On the other hand, for example, d ( \begin{matrix}O & O & O \\ O & O \end{matrix} ) =

d ( \begin{matrix}O \\ O \end{matrix} ) + 1 = 2.

Definition 4. Let R be an n-configuration where the internal columns, all but the first and the last columns, if they exist, are odd and marked with the same symbol, either O or X. Use the following rules to define, in each column of ϕ_{O}(R) and ϕ_{X}(R), the position and symbol of the marked cell, where we denote the ith-column of an n-configuration R by (R)_{i}. Note that if an internal column is marked with X we do not define ϕ_{O}(R), and if an internal column is marked with O we do not define ϕ_{X}(R).

(a) Let ϕ_{O}(R) := R and ϕ_{X}(R) := R.

(b) Replace both (ϕ_{O}(R))_{1} and (ϕ_{X}(R))_{1} by X if the tower of R is O O , or by X if the

tower of R is X X .

(c) Replace both (ϕ_{O}(R))_{n} and (ϕ_{X}(R))_{n} by O if the last column of R is empty, or by

O if the last column of R is a tower.

(d) For 1 < i < n, replace the O in (ϕ_{O}(R))_{i} by an X in the same position.

(e) For 1 < i < n, replace the X in (ϕ_{X}(R))_{i} by an O in the same position.

(f) If (ϕ_{O}(R))_{n−1} ≠ (ϕ_{O}(R))_{1}, reverse the position of the marked cell in (ϕ_{O}(R))_{i} (from top to bottom and from bottom to top), for each i ∈ {1, …, n − 1}.

(g) If (ϕ_{X}(R))_{2} ≠ (ϕ_{X}(R))_{n}, reverse the position of the marked cell in (ϕ_{X}(R))_{i} (from top to bottom and from bottom to top), for each i ∈ {2, …, n}.

It is important to note that if R is formed by a tower and an empty column, in either order, then both ϕ_{O}(R) and ϕ_{X}(R) are φ(R) as defined in (3), namely

φ : O O  ↦ X O ;  O O ↦ O X ; X X  ↦ X O ;  X X ↦ X O .

Definition 5. Suppose that T is a configuration without towers. Remember that a pair of consecutive (odd) columns marked with X and O, in this order, is a descent; the number of descents is desc T. Hence, T is ordered exactly when desc T = 0. Let T^{∗} be the (2 desc T)- configuration formed by the consecutive descents. For example,

O X X  X O  X X  X O  X  O  O O ^{∗}= X O X O .

Given a descent of T, the O-interval of the descent is the subrectangle that contains the descent and all consecutive columns marked with X on the left-hand side, and the X-interval of the descent is the subrectangle that contains the descent and all consecutive columns marked with O on the right-hand side. In the former example, the O-interval of the first descent is X X X O X whereas the X-interval is X O O . Note that if we apply ϕ_{O},

for example, to a suitable configuration R and obtain T, then desc(T) = 1, the (two) even columns of R are encoded in T^{∗} according to (3), and their position in R, as well as the odd columns of R, follow from rules (d) and (f). In other words, we may invert ϕ_{O} and ϕ_{X}. For

example, ϕ_{O}^{−1}( \begin{matrix}X & X & & X & O \\ & & X \end{matrix} ) =  O  O X O  X and ϕ_{X}^{−1}( \begin{matrix}X & O \\ & & O \end{matrix} ) =  X X X .

Theorem 6. For every natural number n there is a bijection φ = φ_{n} : O_{n} → T_{n} that maps the ordered configurations with k towers, where 0 ≤ 2k ≤ n, to the configurations without towers with exactly k descents.

Proof. Definition of φ. Let R ∈ O_{n} be of type t = (i, j). If R has no towers (i.e., d(R) = 0), we define φ(R) = R.

If d(R) ≥ 1, we first consider a configuration T defined as follows. If d(R) = 1, then T = R. Otherwise, we consider φ(R′_{↓}), which, having no towers, has depth zero. Note that d(R′_{↓}) < d(R) and, if S = (φ(R′_{↓}))^{↑} and T is the configuration obtained from R by replacing each even column by the corresponding even column of S, then d(T) = d(S) = 1. Finally φ(R) is obtained by applying ϕ_{O} to each segment tower-empty column or empty columntower of T, according to Definition 4, in the first i columns, and by applying ϕ_{X} likewise in the last j columns. See Example 7.

Bijectivity of φ. Given a configuration U without towers, we show that there exists a unique ordered configuration R such that U = φ(R) as defined above. The proof proceeds by induction on desc(U). Note that if desc(U) = 0 then U is ordered (and without towers), and so U = φ(U); on the other hand, if R has any tower than desc (φ(R)) ≠ 0, by the previous definition.

Suppose that desc(U) ≥ 1 and let V be obtained from U^{∗} by using φ^{−1} (as defined in (3)) in each descent. Consider Ũ = V_{↓} and note that desc Ũ < desc U, and so, by induction, Ũ = φ(R̃) for a unique ordered configuration R̃ of type (ℓ, m). Now, note that if U = φ(R) for some ordered configuration R then R′_{↓} = R̃ and V = S as defined above, since φ(V) = U^{∗}. Thus we may recover T by considering the O-intervals of the first ℓ descents of U and by replacing it by its image by ϕ_{O}^{−1}, and similarly by considering the X-intervals of the remaining m descents and by replacing it by its image by ϕ_{X}^{−1}. Finally, R is obtained from T by replacing the even columns by the corresponding even columns of R′.

Example 7. Let again R =  O O O  X X X O O  X X  X  . Then, as before, R′_{↓} =
O X O  X  and so φ(R′_{↓}) = O X O  O and S =  O O  X  O O O  X  O . Now,
T =  O O O  X X  O O O  X X  O and

φ(R) = X  O  X  O  O X  X O X  O  X .

Let now U = X X O  X  O X X X O  O O  X  X . Then U^{∗} = X O  O X
encodes V =  X  O X  O since Ũ = _{X O} encodes \begin{matrix}O \\ O \end{matrix}  (note the double bars), which

contains no descents. Hence, we have

φ^{−1}( \begin{matrix}& X & X & O & & & X & & O & X & X & X \\ O & & & & O & O & & X & & & & & X \end{matrix} ) =
O O O  O  X X X
O O  O O O  X

The algorithm behind the proof has been implemented in Mathematica [4].

3 Consequences

As pointed out before, we obtain directly (1) from Theorem 6.

Corollary 8. For every non-negative integer number n,

∑_{\begin{matrix}i+j=n \\ i,j≥0 \end{matrix}} \binom{2i}{i}\binom{2j}{j} = 4^{n}. _{□}  (1)

Corollary 9. For every integer numbers n and k, if 0 ≤ 2k < n then

∑_{p=0}^{n} ∑_{i=0}^{k} \binom{p}{i}\binom{p − i}{i}\binom{n − p}{k − i}\binom{n − p − k + i}{k − i} = 4^{k}\binom{n + 1}{2k + 1}  (2)

and for every integer i with 0 ≤ i ≤ k,

∑_{p=0}^{n} \binom{p}{i}\binom{p − i}{i}\binom{n − p}{k − i}\binom{n − p − k + i}{k − i} = \binom{2i}{i}\binom{2k − 2i}{k − i}\binom{n + 1}{2k + 1} .  (4)

Proof. By considering all the possible positions of the i white towers and of the corresponding i empty columns within the p columns of the white region, where 2i ≤ p ≤ n, and proceeding similarly for the black region, we obtain that the number of ordered configurations with k towers is

T_{k}(n) = ∑_{p=0}^{n} ∑_{i=0}^{k} 2^{p−2i}\binom{p}{i}\binom{p − i}{i} 2^{n−p−2(k−i)}\binom{n − p}{k − i}\binom{n − p − k + i}{k − i}

= 2^{n−2k} ∑_{p=0}^{n} ∑_{i=0}^{k} \binom{p}{i, i, 2p − 2i}\binom{n − p}{k − i, k − i, n − p − 2k + 2i} .

On the other hand, the number of configurations without towers and with exactly k descents is

2^{n}\binom{n + 1}{2k + 1},

since we may mark in each column either the top cell or the bottom one, and since the marked cells may be characterized by a subset of [n + 1], either the set S ⊆ [n] of positions of the first cell marked with X, the first cell marked with O on its right-hand side, and so on, if the last column of the configuration is marked with X, or the set S ∪ {n + 1} if the last column of the configuration is marked with O. This number equals T_{k}(n) by Theorem 6, which proves combinatorially (2).

For proving (4), note that U = φ(R) if and only if U^{∗} = φ(R′), and that when R runs through the set of ordered configurations with a given number i of O-towers (and k − i X-towers) then R′_{↓} runs through all \binom{2i}{i}\binom{2k−2i}{k−i} ordered configurations of type (i, k − i).

It is perhaps worth noting that Corollary 9 may be thought of as a refinement of Corollary 8, in the precise sense that, since an n-configuration can have at most ⌊n/2⌋ towers, ∑_{i+j=n} \binom{2i}{i}\binom{2j}{j} = ∑_{k=0}^{⌊n/2⌋} T_{k}(n). In particular, ∑_{k=0}^{⌊n/2⌋} \binom{n+1}{2k+1} = 2^{n}. In fact, the expression on the left-hand side counts the number of subsets of {1, 2, …, n + 1} of odd size, and, by Pascal’s formula, \binom{n+1}{2k+1} = \binom{n}{2k+1} + \binom{n}{2k}.

4 Acknowledgments

We thank the referee for his/her very valuable suggestions, namely the inclusion of Equation (4). The work of both authors was supported in part by the European Regional Development Fund through the program COMPETE — Operational Program Factors of Competitiveness (“Programa Operacional Factores de Competitividade”) and by the Portuguese Government through FCT — Fundação para a Ciência e a Tecnologia, under the projects PEst-C/MAT/UI0144/2014 (CMUP) and PEst-C/MAT/UI4106/2014 (CIDMA).

References

[1] V. De Angelis, Pairings and signed permutations, Amer. Math. Monthly 113 (2006) 642–644.

[2] G. Chang and C. Xu, Generalization and probabilistic proof of a combinatorial identity, Amer. Math. Monthly 118 (2011) 175–177.

[3] R. Duarte and A. Guedes de Oliveira, A short proof of a famous combinatorial identity,

   2013. Preprint available at http://arxiv.org/abs/1307.6693.
[4] A. Guedes de Oliveira, http://www.fc.up.pt/pessoas/agoliv/OCvsCwT/OCvsCwT.nb.

[5] R. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 1997.

[6] M. Sved, Counting and recounting, Math. Intelligencer 5 (1983) 21–26.

[7] M. Sved, Counting and recounting: the aftermath, Math. Intelligencer 6 (1984) 44–45.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences (2013), available elec-

   tronically at http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A10. Keywords: combinatorial identity, binomial coefficient, combinatorial proof.

(Concerned with sequences \underline{A051288}, \underline{A085841}, \underline{A089627}, \underline{A105070}, and \underline{A229032}.)

Received September 11 2013; revised version received June 6 2014; August 7 2014. Published in Journal of Integer Sequences, August 12 2014.

Return to Journal of Integer Sequences home page.