Touchard’s Drunkard

Nachum Dershowitz^{1} School of Computer Science

Tel Aviv University

Ramat Aviv

Israel

nachum@cs.tau.ac.il

Abstract

Based on Touchard’s identity, we give a simple derivation for the enumeration of the N/S/E/W walks that remain on the north side of the origin.

You’re a baby and as stupid as a Frenchman. You persist in thinking that it’s the same as it was at Touchard’s, and that I’m as stupid as at Touchard’s. … But I’m not so silly as I was at Touchard’s. … I was drunk yesterday, but not from wine,

but because I was excited.

—Fyodor Dostoyevsky, The Raw Youth (1875)

1 Introduction: drunken walks

An inebriated person in Nice (see Figure 1) takes a walk, each step in one of the four cardinal directions, north (N), south (S), east (E), and west (W). We are interested in those walks beginning at the center of the Promenade des Anglais (at the southern end of town^{2}) and ending anywhere on the promenade—all the while remaining on land (in other words, not

1This research benefitted from a fellowship at the Paris Institute for Advanced Studies (France), with the financial support of the French state, managed by the French National Research Agency’s “Investissements d’avenir” program (ANR-11-LABX-0027-01 Labex RFIEA+).

2And site of recent carnage.

Figure 1: Center of Nice, France, with the promenade at its southern end.

venturing south of the promenade). In how many possible ways can such walks meander? Let

D_{n} = { the number of Touchard walks, consisting of a sequence of n steps, each of which is one of N/S/E/W, such that at each point along the way the number of N-steps that have been taken is never less than the number of S-steps, and, further- more, in the end they are equal (with no restrictions on the distribution of E- or W-steps).

These are walks that remain in the half-plane and return to the boundary. Table 1 lists valid and invalid walks of length n = 4. For an example of a longer walk, see Figure 2.

Theorem 1. The number of Touchard walks with a total of n steps is

D_{n} = C_{n+1},

where C_{i} is the ith Catalan number, \frac{1}{i+1} \binom{2i}{i} (sequence \underline{A000108} in Sloane’s Encyclopedia of Integer Sequences [22]).

There are, for instance, C_{5} = 42 valid 4-step walks, listed in Table 1.

Guy [11] points out that this equality “is not well known! … nor can we immediately see any correspondence between [Touchard] walks and any of the manifestations [of Catalan objects].” We aim to fill this lacuna.

For a history of Catalan enumerations, see [23, Appendix B].

Valid  Invalid
N N S S N S \underline{S} N
N S N S \underline{S} N N S
N S E E \underline{S} N E E
N S E W \underline{S} N E W
N S W E \underline{S} N W E
N S W W \underline{S} N W W
N E S E \underline{S} \underline{E} N E
N E S W \underline{S} \underline{E} N W
N W S E \underline{S} \underline{W} N E
N W S W \underline{S} \underline{W} N W
N E E S \underline{S} \underline{E} \underline{E} N
N E W S \underline{S} \underline{E} \underline{W} N
N W E S \underline{S} \underline{W} \underline{E} N
N W W S \underline{S} \underline{W} \underline{W} N

Valid  Invalid
\underline{S} N \underline{S} N
\underline{S} \underline{S} \underline{N} N
E N S E E \underline{S} N E
E N S W E \underline{S} N W
W N S E W \underline{S} N E
W N S W W \underline{S} N W
E N E S E \underline{S} \underline{E} N
E N W S E \underline{S} \underline{W} N
W N E S W \underline{S} \underline{E} N
W N W S W \underline{S} \underline{W} N
E E N S E E \underline{S} N
E W N S E W \underline{S} N
W E N S W E \underline{S} N
W W N S W W \underline{S} N

Table 1: All Touchard walks of length 4 with equal quantities of N-steps and S-steps, 26 valid and 28 not, besides 16 valid E/W walks with no N/S-steps at all. The illegal steps in the Mediterranean are \underline{underlined}. Walks with unequal numbers of N- and S-steps are always invalid.

Figure 2: A valid walk, N E W W N N E E S E N N S S S S E E, consisting of 18 steps, 5 N, 5 S, 6 E, and 2 W.

Figure 3: The ten N/S-steps of Figure 2, stretched out on a timeline: N N N S N N S S S S. Connecting the tails of the steps yields a Dyck path of NE/SE steps.

Figure 4: The eight E/W-steps of Figure 2: E W W E E E E E.

2 Enumeration: Touchard’s identity

Touchard’s [26] identity (see, for example, [14, p. 319]) states that

C_{n+1} = ∑_{i} C_{i}2^{n−2i}\binom{n}{2i}.

For a nice proof of this, see [21].

Considering the above theorem and this identity, we can understand the drunken walks in Table 1, for n = 4, as comprising \frac{1}{1} \binom{0}{0}2^{4}\binom{4}{0} = 16 valid walks with no (i = 0) north-south steps, \frac{1}{2} \binom{2}{1}2^{2}\binom{4}{2} = 24 walks containing one (i = 1) north-step followed at some point by one south-step, and \frac{1}{3} \binom{4}{2}2^{0}\binom{4}{4} = 2 walks with two (i = 2) north-steps and two matching south-steps.

With Touchard’s identity, the proof of the theorem is immediate:

1. Suppose there are i N-steps and i S-steps, for some i in the range [0 .. n/2], leaving n − 2i steps of type E or W.

2. The factor C_{i} counts the patterns consisting of i N-steps and an equal number of Ssteps, starting and ending on the promenade, and never venturing further south (see Figure 3). This is one of the many well-known instances of Catalan enumerations, and is a special case of the famous “ballot problem,” stated and solved by Whitworth back in 1878 [27].

3. The factor 2^{n−2i} counts the patterns of the remaining unconstrained E/W-steps (see Figure 4).

4. The factor \binom{n}{2i} is the number of ways of interspersing 2i N/S-steps among n − 2i E/W-steps.

3 Bijection: Dyck paths

Walks whose steps are only north or south and stay on land (as in step 2 in the above proof) correspond to the well-known Dyck (monotonic lattice) paths ([9], [14, pp. 151–153]), which spread out the steps over a timeline that runs from west to east. Dyck paths are usually depicted as consisting of equal numbers of NE- and SE-steps, staying the whole time north of the origin. They are counted by the Catalan numbers. For an example, see the dashed line in Figure 3. Alternatively, such paths may be viewed as consisting of N- and E-steps, never going below the y = x diagonal; see [16, pp. 1–4].

Alternatively, Dyck paths may be viewed as consisting of N/S-steps meeting the requirements that (a) the number of south steps—throughout the walk—never exceeds the number of north ones and (b) that—at the end—they be equal. The enumeration D_{n} counts walks in any of the four directions (N/S/E/W) abiding by the identical constraints.

N E W W N N E E S E N N S S S S E E ⇔ N NN NS SN SN NN NN NS NS SS NS NN NN SS SS SS SS NS NS S

Figure 5: The Dyck path corresponding to the Touchard walk of Figure 2.

To relate the two kinds of walks, consider a Dyck path of length 2n + 2, of which there are C_{n+1}. It must start with N and end with S. Forget those two steps. Then start from the beginning and replace as follows: NN ↦ N, SS ↦ S, NS ↦ E, SN ↦ W. The result is a Touchard walk of length n. The reverse direction of this bijection is straightforward. See Figure 5.

This construction is similar to one used in [6, 12]. Touchard walks are also easily seen to be in bijection with two-colored Motzkin paths [3] (the two colors being E and W). These in turn are in bijection with ballot sequences [25] or Dyck paths [9] in a manner similar to the above; see [23, item 40].

4 Extension: more dimensions

Walks can be entertained in more dimensions with varying degrees of restriction.

a. For each dimension with its two opposing directions (like N and S above) that must stay to one side of the origin and return to zero (the promenade in our example) at the end, there is a Catalan factor

C_{i} = \frac{1}{i + 1}\binom{2i}{i},

accounting for 2i steps, i in each direction (\underline{A000108}). This component represents ballot sequences or Dyck paths.

b. For each dimension that must return to zero at the end (but need not stay on one side of the origin), there is a central binomial factor

A_{2i} = \binom{2i}{i}

for i steps in each of the two directions, in any order (\underline{A000984}). These are the linear “drunken walks” studied by Polyá [19], also called “grand-Dyck” paths [18].

c. For each dimension that must stay on one side of the origin (but need not return to zero at the end), there is a central binomial factor

A_{j} = \binom{j}{⌊j/2⌋}

for a total of j steps (\underline{A001405}). This component represents ballot sequences with an uneven number of votes for the two candidates or prefixes of Dyck paths.

d. For any remaining r unrestricted directions (like E and W above), there is an exponential factor

r^{n−m}

covering the n − m steps that are not yet accounted for, where m = 2i_{1} + 2i_{2} + ⋯ + j_{1} + ⋯, the i_{k} for each case (a) or (b) and the j_{k} for cases (c). When all directions are accounted for by cases (a–c) and r = 0, we must have m = n and this factor is 1.

• To fix which of the n steps belong to which category, there is a multinomial choice

\binom{n}{2i_{1}, …, j_{1}, …, n − m}.

The steps in dimensions adhering to cases (a) and (b) have an even number 2i_{k} of steps; cases (c) and (d) can have an odd number j_{k} of steps.

• All the factors are summed for all possible values of the indices:

∑_{i_{1},i_{2},...,j_{1},j_{2},...}r^{n−m}C_{i_{1}}C_{i_{2}} ⋯ A_{2i_{ℓ}} ⋯ A_{j_{1}} ⋯ \binom{n}{2i_{1}, 2i_{2}, …, j_{1}, …, n − m},

where m = 2i_{1} + 2i_{2} + ⋯ + j_{1} + j_{2} + · · ·. If r = 0, however, the sum is

∑_{m=n}C_{i_{1}}C_{i_{2}} ⋯ A_{2i_{ℓ}} ⋯ A_{j_{1}} ⋯ \binom{n}{2i_{1}, 2i_{2}, …, j_{1}, …}.

We can indicate the type of walk by a multiset of letters for the relevant cases. Each dimension contributes a letter a–e, where e is short for dd, meaning that there are no restrictions on steps in that dimension, whereas d means that the dimension is one-way only. Our drunkard’s walk, then, is of type ae, being confined to the northern half of the plane but unrestricted longitudinally.

One-dimensional paths of types a, b, c, ee are classified in [2] as excursions, bridges, meanders, and walks, respectively, based on terminology of the theory of Brownian motion.

Whenever there are only dimensions of types a and b, the number of walks is 0 for an odd number n of steps.

Motzkin paths [1, pp. 300–301] are like Dyck paths but allow arbitrary horizontal E-steps in addition to NE and SE. They are equivalent to walks of type ad and are enumerated by the Motzkin numbers (\underline{A001006}),

M_{n} = ∑_{i} C_{i}\binom{n}{2i}.

Were we to insist that our drunkard return to the origin at the end of an evening of wanderings, then those would be walks of type ab, which are counted by

∑_{i} C_{\frac{n}{2} −i}\binom{n}{2i}\binom{2i}{i} = C\frac{n}{2} \binom{n + 1}{n/2}

for even n [24]. This is \underline{A000891}(n/2). When n is odd, there is—of course—no way home. (Nagy [17] finds related formulæ for the case when an N/S-walk crosses the abscissa an even number of times going south.)

The simplification of the above sum for walks of type ab, as well as the next three, may be seen as the result of a few applications of binomial cancellation (the “subset of subsets equation”) [13, eq. 1.2.6(20)] followed by Vandermonde’s convolution [10, eq. 3.1]:

∑_{i} \frac{1}{\frac{n}{2} − i + 1}\binom{n − 2i}{n/2 − i}\binom{n}{2i}\binom{2i}{i} = ∑_{i} \frac{1}{\frac{n}{2} − i + 1}\binom{n − 2i}{n/2 − i}\binom{n}{i}\binom{n − i}{i}

= ∑_{i} \frac{1}{\frac{n}{2} − i + 1}\binom{n}{i}\binom{n − i}{n/2 − i}\binom{n/2}{i}

= ∑_{i} \frac{1}{\frac{n}{2} − i + 1}\binom{n}{n/2}\binom{n/2}{i}\binom{n/2}{i}

= \frac{1}{\frac{n}{2} + 1}\binom{n}{n/2} ∑_{i} \binom{n/2}{i}\binom{n/2 + 1}{n/2 − i}

= \frac{1}{\frac{n}{2} + 1}\binom{n}{n/2}\binom{n + 1}{n/2}.

Walks of type aa stay in one quadrant and return to the origin. They are counted by \underline{A005568} [11, §4],

∑_{i} C_{i}C_{\frac{n}{2} −i}\binom{n}{2i} = C\frac{n}{2} C_{\frac{n}{2} +1},

a  b  c  d  e
a \underline{A005568}* \underline{A000891}* \underline{A001700} \underline{A001006} \underline{A000108}
b  \underline{A002894}* \underline{A018224} \underline{A002426} \underline{A000984}
c  \underline{A005566} \underline{A005773} \underline{A001700}
d  \underline{A000079} \underline{A000244}
e  \underline{A000302}

Table 2: Two-dimensional walks. The types a–e are as explained in the text. Each square gives the enumeration of walks with one dimension according to the row and the other according to column. (*The three starred sequences enumerate walks of even length only, returning to the point of origin.)

again for even n.

Walks of type ac stay in one quadrant but return to the abscissa (the promenade) and are counted by \underline{A001700},

∑_{i} C_{i}A_{n−2i}\binom{n}{2i} = \binom{2n + 1}{n}.

They are discussed at length in [11, §4].

Walks of type ce are just restricted to the half-plane. These are Guy’s “Sandsteps” [11], introduced by Sands [20], and are also counted by \underline{A001700}:

∑_{i} C_{i}A_{n−2i}\binom{n}{2i} = \binom{2n + 1}{n}.

These and the remaining two-dimensional cases are summarized in Table 2. Most of these were investigated in [8, 7, 12]. Their asymptotics were derived in [4]. More complicated walks involving diagonal steps have also been considered in the literature (e.g. [15, 5]).

5 Restriction: three dimensions

Suppose that the swaggering pedestrian (or an intoxicated bird) can also move up (U) or down (D) at any point (and continue moving on those levels), never venturing underground. Suppose further that the path taken need only end up on the ground, not necessarily on the promenade. The number of n-step walks of this type (ace) is, by the general formula of the previous section,

∑_{i,j} \frac{2^{n−2i−j}}{i + 1} \binom{2i}{i}\binom{j}{⌊j/2⌋}\binom{n}{2i, j, n − 2i − j} = ∑_{i,j} \frac{2^{n−2i−j}}{i + 1} \binom{n}{i, i, ⌊j/2⌋, ⌈j/2⌉, n − 2i − j}.

Table 3 provides computed initial terms for all three-dimensional walks with steps in all six directions (N/S/E/W/U/D) and with some requirement or other to return towards the origin.

Type Space Back  Sequence
aaa octant origin 1, 0, 3, 0, 24, 0, 285, 0, 4242, 0, 73206, 0, 1403028, 0, 29082339, … (\underline{A064037}*)
aab quad. origin 1, 0, 4, 0, 40, 0, 570, 0, 9898, 0, 195216, 0, 4209084, 0, 96941130, …
aac octant axis 1, 1, 4, 9, 40, 120, 570, 1995, 9898, 38178, 195216, 805266, 4209084, …
aad octant axis 1, 1, 3, 7, 23, 71, 251, 883, 3305, 12505, 48895, 193755, 783355, 3205931, …
aae quad. axis 1, 2, 6, 20, 74, 292, 1214, 5252, 23468, 107672, 505048, 2413776, … (\underline{A145867})
abb half origin 1, 0, 5, 0, 62, 0, 1065, 0, 21714, 0, 492366, 0, 12004740, 0, 308559537, …
abc quad. axis 1, 1, 5, 12, 62, 200, 1065, 3990, 21714, 89082, 492366, 2147376, 12004740, …
abd quad. axis 1, 1, 4, 10, 39, 131, 521, 1989, 8149, 33205, 139870, 592120, 2552155, …
abe half axis 1, 2, 7, 26, 108, 472, 2159, 10194, 49396, 244328, 1229308, 6273896, …
acc octant plane 1, 2, 7, 24, 98, 400, 1785, 7980, 37674, 178164, 874146, 4294752, 21667932, …
acd octant plane 1, 2, 6, 19, 67, 246, 947, 3746, 15213, 62950, 264920, 1129965, … (\underline{A145847})
ace quad. plane 1, 3, 11, 44, 188, 842, 3911, 18692, 91412, 455540, 2306028, 11829424, …
add octant plane 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, … (\underline{A000108})
ade quad. plane 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, 751236, 3328218, … (\underline{A002212})
aee half plane 1, 4, 17, 76, 354, 1704, 8421, 42508, 218318, 1137400, 5996938, … (\underline{A005572})
bbb full origin 1, 0, 6, 0, 90, 0, 1860, 0, 44730, 0, 1172556, 0, 32496156, … (\underline{A002896}*)
bbc half axis 1, 1, 6, 15, 90, 310, 1860, 7455, 44730, 195426, 1172556, … (|\underline{A138547}|)
bbd half axis 1, 1, 5, 13, 61, 221, 1001, 4145, 18733, 82381, 375745, 1703945, 7858225, …
bbe full axis 1, 2, 8, 32, 148, 712, 3584, 18496, 97444, 521096, 2820448, … (\underline{A202814})
bcc quad. plane 1, 2, 8, 30, 138, 620, 3060, 14910, 76650, 390852, 2063376, 10832052, …
bcd quad. plane 1, 2, 7, 25, 101, 416, 1787, 7792, 34645, 155722, 707795, 3242515, … (\underline{A150500})
bce half plane 1, 3, 12, 53, 252, 1252, 6416, 33609, 178996, 965660, 5263728, 28936404 …
bdd quad. plane 1, 3, 11, 45, 195, 873, 3989, 18483, 86515, 408105, 1936881, … (\underline{A000984})
bde half plane 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, … (\underline{A026375})
bee full plane 1, 4, 18, 88, 454, 2424, 13236, 73392, 411462, 2325976, … (\underline{A081671})

Table 3: Three-dimensional walks, required to return to the origin (three dimensions of type a or b), axis of origin (two), or plane of origin (one). They may be constrained to a fraction of the space—octant (three of a, c, or d), quadrant (two), or half-space (one), or else allowed the full space (zero). The types are as explained in the text. (*The four starred sequences enumerate walks of even length only. In one case, bbc, the cited sequence, \underline{A138547}, has alternating signs.)

5.1 Acknowledgments

I thank Jeffrey Shallit and a referee for helpful suggestions.

References

[1] M. Aigner, A Course in Enumeration, Graduate Texts in Mathematics, Vol. 238, Springer, 2007.

[2] C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci. 281 (2002), 37–80.

[3] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, A construction for enumerating k-coloured Motzkin paths, in Proc. 1st Annual Intl. Conf. on Computing and Combinatorics, Springer, 1995, pp. 254–263.

[4] A. Bostan and M. Kauers, Automatic classification of restricted lattice walks, Proc. 21st Intl. Conf. on Formal Power Series and Algebraic Combinatorics, Discrete Mathematics and Theoretical Computer Science, 2009, pp. 201–215. Available at

http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAK0117/2679.

[5] M. Bousquet-Mélou, Counting walks in the quarter plane, in B. Chauvin, P. Flajolet, D. Gardy, and A. Mokkadem, eds., Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Birkhäuser, 2002, pp. 49–67.

[6] W. Breckenridge, H. Gastineau-Hills, A. Nelson, P. Bos, G. Calvert, and K. Wehrhahn, Lattice paths and Catalan numbers, Bull. Inst. Combin. Appl. 1 (1991), 41–55.

[7] E. Csáki, S. G. Mohanty, and S. Saran, On random walks in a plane, Ars Combin. 29 (1990), 309–318.

[8] D. W. DeTemple and J. M. Robertson, Equally likely fixed length paths in graphs, Ars Combin. 17 (1984), 243–254.

[9] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[10] H. W. Gould, Combinatorial Identities: A Standardized Set of Tables Listing 500 Binomial Coefficient Summations, rev. ed., self-published, Morgantown, WV, 1972.

[11] R. K. Guy, Catwalks, Sandsteps and Pascal pyramids, J. Integer Seq. 3 (2000), Article 00.1.6.

[12] R. K. Guy, C. Krattenthaler, and B. E. Sagan, Lattice paths, reflections, & dimensionchanging bijections, Ars Combin. 34 (1992), 3–15.

[13] D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997.

[14] T. Koshy, Catalan Numbers with Applications, Oxford University Press, 2009.

[15] G. Kreweras, Sur une classe de problèmes liés au treillis des partitions d’entiers, Cahiers du B.U.R.O. 6 (1965), 5–105.

[16] G. Mohanty, Lattice Path Counting and Applications, Academic Press, 1979.

[17] G. V. Nagy, A combinatorial proof of Shapiro’s Catalan convolution, Adv. in Appl. Math. 49 (2012), 391–396.

[18] E. Pergola, Two bijections for the area of Dyck paths, Discrete Math. 241 (2001), 435–447.

[19] G. Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz, Math. Annalen 84 (1921), 149–160. Reprinted in G.-C. Rota, ed., George Pólya: Collected Papers, Vol. 4: Probability; Combinatorics; Teaching and Learning in Mathematics, MIT Press, 1984, pp 69–80, 609.

[20] B. Sands, Problem 1517^{∗}, Crux Mathematicorum 16 (1990), 44.

[21] L. W. Shapiro, A short proof of an identity of Touchard’s concerning Catalan numbers, J. Combin. Theory, Series A 20 (1976), 375–376.

[22] N. J. Sloane, ed., The on-line encyclopedia of integer sequences, http://oeis.org, 2016.

[23] R. P. Stanley, Catalan Numbers, Cambridge Univ. Press, 2015. Appendix B (History of Catalan numbers) by I. Pak.

[24] A. V. Sutherland, Comment to sequence \underline{A000891} in [22] (2008).

[25] L. Takács, Ballot problems, Z. Wahrscheinlichkeitstheorie Verw. Gebiete 1 (1962), 154– 158.

[26] J. Touchard, Sur certaines équations fonctionnelles, in Proc. Intl. Math. Congress (Toronto, 1924), Vol. 1, 1928, pp. 465–472. Available at

    http://www.mathunion.org/ICM/ICM1924.1/Main/icm1924.1.0465.0472.ocr.pdf.

[27] W. A. Whitworth, Arrangements of m things of one sort and n things of another sort, under certain conditions of priority, Messenger Math. 8 (1878), 105–114.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: path enumerations, drunken walk, random walk, Dyck path, lattice path, Touchard’s identity, Catalan number, Motzkin number, central binomial factor.

(Concerned with sequences \underline{A000079}, \underline{A000108}, \underline{A000244}, \underline{A000302}, \underline{A000891}, \underline{A000984}, \underline{A001006}, \underline{A001405}, \underline{A001700}, \underline{A002212}, \underline{A002426}, \underline{A002894}, \underline{A002896}, \underline{A005566}, \underline{A005568}, \underline{A005572}, \underline{A005773}, \underline{A018224}, \underline{A026375}, \underline{A064037}, \underline{A081671}, \underline{A138547}, \underline{A145847}, \underline{A145867}, \underline{A150500}, and \underline{A202814}.)

Received March 15 2016; revised versions received June 1 2016; December 18 2016; December 21 2016. Published in Journal of Integer Sequences, December 26 2016.

Return to Journal of Integer Sequences home page.