A Combinatorial Model for Lane Merging

Viktoriya Bardenova, Erik Insko, Katie Johnson, and Shaun Sullivan Department of Mathematics Florida Gulf Coast University Fort Myers, FL 33901 USA

                  bardenovav@vcu.edu
                    einsko@fgcu.edu
                   kjohnson@fgcu.edu
                  ssullivan@fgcu.edu

Abstract

A two-lane road approaches a stoplight. The left lane merges into the right just past the intersection. Vehicles approach the intersection one at a time, with some drivers always choosing the right lane, while others always choose the shorter lane, giving preference to the right lane to break ties. An arrival sequence of vehicles can be represented as a binary string, where the zeros represent drivers always choosing the right lane, and the ones represent drivers choosing the shorter lane. From each arrival sequence we construct a merging path, which is a lattice path determined by the lane chosen by each car. We give closed formulas for the number of merging paths reaching the point (n, m) with exactly k zeros in the arrival sequence, and the expected length of the right lane for all arrival sequences with exactly k zeros. Proofs involve an adaptation of André’s reflection principle. Other interesting connections also emerge, including to: ballot numbers, the expected maximum number of heads or tails appearing in a sequence of n coin flips, the largest domino snake that can be made using pieces up to [n : n], and the longest trail on the complete graph K_{n} with loops.

1 Introduction

Imagine you are driving on a road with two lanes where there is a stoplight and soon after, the left lane will have to merge into the right. Some drivers will move to the right lane before the traffic light, regardless of its length. Others will choose the shortest lane, giving preference to the right lane when the lengths are equal.

We model this situation using a binary string called an arrival sequence, assuming cars approach the stoplight one at a time with plenty of time to choose their preferred lane. Cars that do not want to merge and that will always choose the right lane are denoted with 0 and colored red in diagrams. Cars that prefer the shortest lane (with ties going to the right lane) are denoted by 1 and colored green.

In Figure 1, the arrival sequence is b = 0011\underline{1}001. The first car will always choose the right lane, no matter what. In this case, the second car is red and will also choose the right lane. The next three cars are green; two will choose the left lane and the third will choose the right as the lanes will be equal in length at that point. (Green cars that end up in the right lane anyway will appear as underlined blue digits in arrival sequences throughout the paper, for extra clarity.) Cars 6 and 7 are red and will choose the right lane. Finally, car 8 is green and will choose the left lane.

1 2 5 6 7 3 4 8

Direction of traffic

Figure 1: Eight cars waiting to merge and the corresponding merging path for b = 0011\underline{1}001.

To each arrival sequence, we can assign a (decorated) lattice path, which we call a merging path. For instance, the merging path for the arrival sequence b = 0011\underline{1}001 is also shown in Figure 1. When a green car ends up staying in the right lane, we say that the merging path bounces off the diagonal, and we decorate the corresponding upward step by highlighting it with a bold blue arrow. Merging paths with no bounces are the famous ballot paths (i.e., lattice paths that do not cross below the diagonal). Hence, merging paths generalize the ballot paths which are used to enumerate the number of ways the ballots in a two-candidate election can be counted so that the winning candidate remains in the lead at all times [1, 2, 12, 14].

An excellent and thorough history of lattice path enumeration is available in Humphreys’ survey paper from 2010 [4], which also includes a discussion of the reflection principle that is used in this paper. Humphreys provides context and further reading for applications as wide-ranging as games [18] to electrostatics [9], number theory [8, 15] to statistics [5, 11]. We remark that there is a rich history of discovering bijections between lattice paths and other mathematical objects [6, 10, 17].

The original motivating questions we answer in this paper are:

Question 1. What is the expected length 𝔼[ℓ] of the right lane when we consider all possible arrival sequences of length ℓ?

Question 2. What is the expected length 𝔼[ℓ, k] of the right lane when we consider all possible arrival sequences of length ℓ containing exactly k zeros?

Throughout this paper, we let B_{ℓ} denote the set of ℓ-bit binary strings that represent arrival sequences, and for each b ∈ B_{ℓ}, we let r(b) denote the length of the right-hand lane.

Example 3. When ℓ = 2 the collection of arrival sequences is B_{2} = \{00, \underline{1}0, 01, \underline{1}1\}, and we calculate the sum of the right lane lengths as R(B_{2}) = ∑_{b∈B_{2}} r(b) = 2 + 2 + 1 + 1 = 6. So, 𝔼[2] = \frac{R(B_{2})}{2^{2}} = 1.5. When ℓ = 3, R(B_{3}) = ∑_{b∈B_{3}} r(b) = 18, and the expected length of the right lane in a randomly selected arrival sequence is 𝔼[3] = \frac{R(B_{3})}{2^{3}} = 2.25.

Example 4. The collection of arrival sequences of length ℓ = 4 with exactly k = 2 zeros is B_{4,2} = {0011, 0101, 0110, 1001, 1010, 1100}. In this case,

R(B_{4,2}) = ∑_{b∈B_{4,2}} r(b) = 2 + 2 + 3 + 3 + 3 + 3 = 16.

The expected length of the right lane of a randomly selected arrival sequence in B_{4,2} is

𝔼[4, 2] = \frac{R(B_{4,2})}{\binom{4}{2}} = \frac{8}{3}.

Section 2 is dedicated to answering Question 1. To do this, we count the number of merging paths that begin at (0, 0) and end at (n, m). We call the number of such merging paths M_{n}(m). Our first main result, Theorem 6, describes closed formulas for the numbers M_{n}(m) in terms of binomial coefficients. We then use Theorem 6 to prove Theorem 7 which answers Question 1. We show that as ℓ tends to infinity, 𝔼[ℓ]/ℓ tends to \frac{1}{2} in Corollary 8.

Figure 2: Merging paths for b = \underline{1}001110011 and b = 01\underline{1}101\underline{1}011.

We find that the sum of right lane lengths R(B_{ℓ}) = ∑_{b∈B_{ℓ}} r(b) when summing over all arrival sequences of length ℓ results in the integer sequence A230137:

0, 2, 6, 18, 44, 110, 252, 588, 1304, 2934, 6380, 14036, 30120, 65260, 138712, …  (1)

Sloane’s On-Line Encyclopedia of Integer Sequences notes that the sequence in (1) divided by 2^{ℓ}, which we denote 𝔼[ℓ] = R(B_{ℓ})/2^{ℓ}, is also the expected value of the maximum of the number of heads and the number of tails when ℓ fair coins are tossed [16]. This fact suggests there is an explicit bijection between the set of merging paths of length ℓ and the sets of ℓ coin flips that sends the length of the right lane in a merging path to the maximum number of heads or tails in the corresponding sequence. In Section 3 we define a map with this property and prove it is indeed a bijection. This bijection also gives a combinatorial proof of Theorem 6.

Section 4 is dedicated to answering Question 2, where we show that as ℓ tends to ∞, 𝔼[ℓ, k]/ℓ tends to \frac{1}{2} when ℓ ≥ 2k, and when ℓ < 2k the expected value 𝔼[ℓ, k]/ℓ tends to the ratio k/ℓ.

In Section 5 we explore a curious correspondence between the collection of arrival sequences with 1 red car, longest domino snakes, and longest trails in complete graphs with loops. We describe an explicit bijection that maps each arrival sequence to a subset of edges in a longest trail in the complete graph with loops or equivalently, a subset of dominoes in the longest domino snake with dominoes.

In Section 6 we consider the final structure of an arrival sequence determined by the right lane vector that records the order of the cars in the right lane, disregarding their color. We then partition the collection of arrival sequences into color-blind equivalence classes based on their right lane vector, show that each color-blind equivalence class has even number of elements, and moreover, that the number of elements in each class is a power of 2. We end this paper with a list of open problems and future directions.

2 Merging paths

We record the information of an arrival sequence with a decorated lattice path where right steps represent green cars (1s), up steps represent red cars (0s), and decorated upward steps (or bounces) represent green cars choosing the right lane when the lanes are even. (Recall that when a green car is forced to choose the right lane, we call this a “bounce”, since the corresponding merging path bounces up off the line y = x when it would normally head right.) Let M_{n}(m) be the number of such lattice paths reaching the point (n, m), where the lattice path starts at the origin. Each of these merging paths represents a sequence of cars that ends with n cars in the right lane and m cars in the left lane. As we remarked earlier, these paths never cross the diagonal y = x, so they are ballot paths. As an example, two merging paths are depicted above in Figure 2, and places where they bounce off the diagonal are highlighted with a bold blue arrow.

The following table counts these paths for small values of m and n, and the subsequent lemma gives a recurrence relation for these numbers.

m n 0 1 2 3 4 5  6  7
0  1
1  2 2
2  2 6 6
3  2 8 20 20
4  2 10 30 70 70
5  2 12 42 112 252 252
6  2 14 56 168 420 924 924
7  2 16 72 240 660 1584 3432 3432

Table 1: Number of merging paths ending at (n, m).

Lemma 5. The numbers M_{n}(m) satisfy the following recurrence relation.

M_{n}(m) = M_{n−1}(m) + M_{n}(m − 1) for m > n + 1, n > 0,
M_{n}(n + 1) = M_{n−1}(n + 1) + 2M_{n}(n) for n > 0,
M_{n}(n) = M_{n−1}(n)  for n > 0,
M_{0}(0) = 1, and M_{0}(m) = 2  for m > 0.

Proof. We prove the recurrence relation by induction on n. If n = 0 then the only merging paths reaching (0, m) are 00 ⋯ 0 and 10 ⋯ 0. Thus, M_{0}(m) = 2 for m > 0. The empty path is the only path reaching (0, 0), thus M_{0}(0) = 1.

Now suppose the recurrence relation is true for n < j and consider paths reaching (j, m). We now start a second induction argument on m ≥ j. If m = j, then the only paths reaching (j, j) come from paths reaching (j − 1, j) by appending a 1; thus

M_{j}(j) = M_{j−1}(j).

If m = j + 1, then the paths reaching (j, j + 1) either come from paths reaching (j − 1, j + 1) by appending a 1, or from paths reaching (j, j) by appending either a 0 or a 1, since both would result in an up step in this case. Thus,

M_{j}(j + 1) = M_{j−1}(j + 1) + 2M_{j}(j).

Finally, if m > j + 1, then the paths reaching (j, m) either come from paths reaching (j − 1, m) by appending a 1, or from paths reaching (j, m − 1) by appending a 0. Thus,

M_{j}(m) = M_{j−1}(m) + M_{j}(m),

completing both induction arguments.

Notice that “folding” Pascal’s triangle in half, i.e., doubling the off-center values, gives the values in Table 1. The following theorem provides a closed formula for the numbers M_{n}(m) based on this observation.

Theorem 6. The numbers M_{n}(m) have the following closed formulas:

M_{n}(m) = 2\binom{m + n}{n} for m > n, and  (2)
M_{n}(n) = \binom{2n}{n}.  (3)

Proof. We prove that Equations (2) and (3) satisfy the recurrence relation in Lemma 5. First, notice that if n = 0, then 2\binom{m+0}{0} = 2 for m > 0 and \binom{2·0}{0} = 1.

From Equation (2), we use the identity

2\binom{2n + 1}{n} = 2\binom{2n}{n − 1} + 2\binom{2n}{n}

to conclude that M_{n}(m) = M_{n−1}(m) + 2M_{n}(m − 1) for m = n + 1 and n > 0. Next, using the identity

\binom{2n}{n} = 2\binom{2n − 1}{n − 1}

for n > 0, we get that M_{n}(n) = M_{n−1}(n) for n > 0.

One may reasonably ask for a combinatorial proof of Theorem 6, and in fact, one will be provided in Corollary 15.

We can now consider the expected length of the right lane for an arrival sequence of ℓ cars, which we denote 𝔼[ℓ] = R(B_{ℓ})/2^{ℓ}. The following theorem gives a closed formula for 𝔼[ℓ].

Theorem 7. Let ℓ ∈ ℕ. If ℓ is odd, then

𝔼[ℓ] = \frac{ℓ}{2^{ℓ}} (2^{ℓ−1} + \binom{ℓ − 1}{(ℓ − 1)/2}) .

If ℓ is even, then

𝔼[ℓ] = \frac{ℓ}{2^{ℓ+1}} (2^{ℓ} + \binom{ℓ}{ℓ/2}) .

Proof. Suppose ℓ is odd, then a path of length ℓ does not end on the diagonal. There are M_{ℓ−i}(i) = 2\binom{ℓ}{i} arrival sequences with right lane length i, so

2^{ℓ}𝔼[ℓ] = R(B_{ℓ}) = ∑_{b∈B_{ℓ}} r(b)

= 2 ∑_{i=(ℓ+1)/2}^{ℓ} i\binom{ℓ}{i}

= 2ℓ ∑_{i=(ℓ−1)/2}^{ℓ−1} \binom{ℓ − 1}{i}

= ℓ (2^{ℓ−1} + \binom{ℓ − 1}{(ℓ − 1)/2}) .

A similar argument shows the case when ℓ is even.

We can simplify this result as the number of cars grows large by using Stirling’s approximation n! ∼ \sqrt{2πn} (\frac{n}{e})^{n} [13] to derive an approximation for the central binomial coefficient \binom{2n}{n} ∼ \frac{2^{2n}}{\sqrt{nπ}}, which results in the following corollary.

Corollary 8.

lim_{ℓ→∞} \frac{𝔼[ℓ]}{ℓ} = \frac{1}{2}.

This means that for large ℓ, the lanes tend to even out, and the effect of the bouncing is not very large. We will see in Section 4 that this limit will change, depending on the ratio of red cars to green cars.

3 A length-preserving bijection between merging paths and coin flips

Sloane’s On-Line Encyclopedia of Integer Sequences notes that the sequence A230137 in (1) divided by 2^{ℓ} is also the expected value of the maximum of the number of heads and the number of tails when ℓ fair coins are tossed [16]. This fact suggests there is an explicit bijection between the set of merging paths of length ℓ and the sets of ℓ coin flips that sends the length of the right lane in a merging path to the maximum number of heads or tails in the corresponding sequence. In this section, we define a map with this property and prove it is indeed a bijection. This bijection also gives a combinatorial proof of Theorem 6.

Let B_{ℓ} denote the set of ℓ-bit binary strings that represent arrival sequences. For each b ∈ B_{ℓ}, let r(b) denote the length of the right-hand lane. Let z(b) = k denote the number of zeros in b and o(b) = ℓ − z(b) denote the number of ones in b. Let C_{ℓ} denote the collection of all possible events when ℓ coins are flipped. To differentiate them from arrival sequences, we will represent elements of C_{ℓ} as bold binary strings with 0 representing a head and 1 representing a tail. For each c ∈ C_{ℓ}, let z(c) denote the number of 0s (heads) in c, o(c) denote the number of 1s (tails) in c, and let max(c) := max{z(c), o(c)}.

In this section we define a function ϕ : B_{ℓ} → C_{ℓ} that satisfies r(b) = max(c) whenever ϕ(b) = c; that is, ϕ sends each arrival sequence b with right lane length r(b) to a sequence of coin flips c whose maximum number max(c) of heads or tails equals r(b). Then we show that ϕ is in fact a bijection. Before proceeding, we give a small example in Table 2 to help illustrate how the map is defined.

b r(b) p  c max(c)
0000 4 0000 0000  4
0100 3 0000 0100  3
0010 3 0000 0010  3
0001 3 0000 0001  3
0011 2 0000 0011  2
01\underline{1}0 3 0001 0111  3
0101 2 0000 0101  2
01\underline{1}1 2 0001 0110  2
\underline{1}000 4 0111 1111  4
\underline{1}100 3 0111 1011  3
\underline{1}010 3 0111 1101  3
\underline{1}001 3 0111 1110  3
\underline{1}011 2 0111 1100  2
\underline{1}1\underline{1}0 3 0110 1001  3
\underline{1}101 2 0111 1010  2
\underline{1}1\underline{1}1 2 0110 1001  2

Table 2: An example of the length preserving bijection given by ϕ.

In order to define the function ϕ : B_{ℓ} → C_{ℓ} we define a vector p that records where the merging path of b bounces off the diagonal. The vector p will work like a light switch, being toggled on to 1 directly after a bounce occurs and staying that way until another bounce toggles it back to 0.

Definition 9. The parity vector p(b) (or p = p_{1}p_{2} ⋯ p_{ℓ} if b is understood) is defined from b as follows:

• The first entry in p is always zero p_{1} = 0.

• If the merging path of b bounces off the diagonal (in particular b_{i} = 1), then p_{i+1} = \overline{p_{i}} := p_{i} + 1 (mod 2).

• Otherwise p_{i+1} = p_{i} for all 1 ≤ i ≤ ℓ − 1.

In terms of the arrival sequences, the parity of p changes one step after a car that is labeled with a 1 goes into the right lane. In terms of lattice paths, the parity vector changes parity after the path bounces off the diagonal.

Here are a few examples to help clarify these definitions:

• If b = 01\underline{1}101\underline{1}1, then p = 00011110, and c = 01101001.

• If b = \underline{1}001110011, then p = 0111111111, and c = 1110001100.

• If b = \underline{1}01011\underline{1}0, then p = 01111110, and c = 11010000.

We are ready to define the function ϕ using the parity vector p. The map ϕ : B_{ℓ} → C_{ℓ} is given by ϕ(b) = b + p (mod 2) = c for all b ∈ B_{ℓ}. Note that to define this map, we think of b and p as elements of ℤ_{2}^{ℓ} and complete the addition modulo 2.

Continuing with the three examples above, we compute ϕ(b) = b + p (mod 2) = c

• 01\underline{1}101\underline{1}1 + 00011110 = 01101001.

• \underline{1}001110011 + 0111111111 = 1110001100.

• \underline{1}01011\underline{1}0 + 01111110 = 11010000.

Remark 10. We also note that the parity vector p can easily be defined from c as well as b. The parity vector p starts with 0, and its parity changes the first time that the number of 1s (tails) in c outnumbers the number of 0s (heads), then the parity changes back when the number of 0s (heads) outnumbers the number of 1s (tails) and so on.

Proposition 11. The function ϕ : B_{ℓ} → C_{ℓ} is one-to-one.

Proof. Suppose b, b′ ∈ B are distinct elements of B_{ℓ}. Let i be the minimum index for which b_{i} ≠ b′_{i}. Then by definition of p, p_{i} = p′_{i} and so b_{i} + p_{i} ≢ b′_{i} + p′_{i} (mod 2). Therefore, ϕ(b) ≠ ϕ(b′), and we conclude that ϕ is one-to-one.

We will soon show that r(b) = max(ϕ(b)) in Theorem 14, and the following lemma provides the base case for the induction argument in that proof. In Definition 9, we defined p so it always starts with a zero, but that choice was somewhat arbitary, and in the process of proving Theorem 14 by induction, we will often break a parity vector up into smaller pieces starting with either 0 or 1, possibly changing parity in position 2, and remaining constant after that. (For example, if b = 01\underline{1}101\underline{1}1, then p = 00011110 and we will consider the following subvectors 00, 0111, and 10 of p.) The important thing here is that each of these parity vectors changes its value when the corresponding merging path bounces; the actual initial value is somewhat arbitrary.

Lemma 12. Suppose b = b_{1}b_{2} ⋯ b_{ℓ} is an arrival sequence whose merging path leaves the diagonal and never has a bounce in positions b_{2} ⋯ b_{ℓ}, i.e., its parity vector is constant from p_{2} ⋯ p_{ℓ}. If ϕ(b) = c, then max(c) = r(b).

Proof. There are four cases to consider: p = 00 ⋯ 0, p = 01 ⋯ 1, p = 10 ⋯ 0, and p = 11 ⋯ 1. First, if p = 00 ⋯ 0, then r(b) = z(b) because otherwise there would be more 1s than 0s in b which would force a 1 to be in the right lane, contradicting the assumption that p = 00 ⋯ 0. Additionally, b + p = b = c and r(b) = z(b) = z(c) = max(c).

If p = 01 ⋯ 1 then b bounces off the diagonal at b_{1} = 1 and nowhere else. In this case, r(b) = z(b) + 1 is the number of zeros in b plus 1 because that first entry b_{1} = 1 ended up in the right lane, but all other 1s will choose the left lane. Since p = 01 ⋯ 1, we have o(c) = z(b) + 1 because b_{1} + p_{1} = 1 + 0 = 1, and b_{i} + p_{i} = \overline{b_{i}} for 2 ≤ i ≤ n, so the first 1 in b corresponds to a tail in c, all other 1s in b correspond to heads in c, and every zero in b corresponds to a tail in c. Finally, since b never bounces back off the diagonal r(b) = z(b) + 1 = o(c) = max(c).

If p = 10 ⋯ 0 then b bounces off the diagonal at b_{1} = 1 and nowhere else. Hence, c = \overline{b_{1}}b_{2} ⋯ b_{ℓ}. Then r(b) = z(b)+1 because if o(b_{1} ⋯ b_{j}) > z(b_{1}b_{2} ⋯ b_{j})+1 for all 2 ≤ j ≤ ℓ then p would switch its parity more than once. Hence, r(b) = z(b) + 1 = z(c) = max(c) because c = \overline{b_{1}}b_{2} ⋯ b_{ℓ} = 0b_{2} ⋯ b_{ℓ} and there is one more zero/head in c than zeros in b.

Lastly, if p = 11 ⋯ 1, then r(b) = z(b) because otherwise there would be more 1s than 0s in b which would force a 1 to be in the right lane, which would contradict the assumption that p = 11 ⋯ 1. Additionally c = b + p = \overline{b} so r(b) = z(b) = o(c) = max(c).

We note that the previous lemma does allow for the merging path to touch the diagonal again after b_{1}, but it does not allow the merging path to bounce off the diagonal anywhere in b_{2} ⋯ b_{ℓ}. For instance, Figure 3 shows two such paths. The first path corresponds to b = \underline{1}001110011 where p = 0111111111 and c = 1110001100. Note that since b_{1} = 1 in this example r(b) = z(b) + 1 = 5 = o(c) = max(c). The second path corresponds to b = 0001110011, for which p = 0000000000 and c = 0001110011. Since b_{1} = 0 in this example, r(b) = z(b) = 5 = z(c) = max(c).

The next lemma shows that if a lattice path corresponding to a merging path b = b_{1} ⋯ b_{ℓ} ends on the diagonal, then r(b) = max(ϕ(b)) = \frac{ℓ}{2}.

Lemma 13. If b = b_{1}b_{2} ⋯ b_{ℓ} is an arrival sequence whose merging path ends on the diagonal, then r(b) = max(c) = \frac{ℓ}{2}.

Proof. We prove the claim by induction on the number of times the merging path bounces off the diagonal after originally leaving the diagonal (or equivalently, the number of times

Figure 3: Two merging paths satisfying the hypotheses of Lemma 12.

the parity vector changes its parity in p_{2} ⋯ p_{ℓ}). The base case was proven in Lemma 12. (To reiterate, if b_{1} = 0, then z(b) = z(c) = o(c) = max(c) = \frac{ℓ}{2}. If b_{1} = 1, then z(b) = o(b) − 2, and r(b) = z(b) + 1 = o(c) = o(b) − 1 = z(c) = max(c) = \frac{ℓ}{2}.)

Now suppose that the claim holds if the merging path returns and bounces off the diagonal i times. Let b denote an arrival sequence whose merging path returns and bounces off the diagonal a total of i + 1 times, and let j be the index where the merging path of b bounces of the diagonal for the last time. Then by induction we know

r(b_{1} ⋯ b_{j}) = o(c_{1} ⋯ c_{j}) = z(c_{1} ⋯ c_{j}) = max(c_{1} ⋯ c_{j}) = \frac{j}{2}

and b_{j+1} ⋯ b_{ℓ} corresponds to a merging path that satisfies the hypotheses of Lemma 12. So r(b_{j+1} ⋯ b_{ℓ}) = o(c_{j+1} ⋯ c_{ℓ}) = z(c_{j+1} ⋯ c_{ℓ}) = max(c_{j+1} ⋯ c_{ℓ}) = \frac{ℓ−j}{2} . Hence,

r(b) = r(b_{1} ⋯ b_{j}) + r(b_{j+1} ⋯ b_{ℓ})

= \frac{j}{2} + \frac{ℓ − j}{2}

= max(c_{1} ⋯ c_{j}) + max(c_{j+1} ⋯ c_{ℓ}) = max(c).

By the principal of mathematical induction the claim holds in general.

The lattice path depicted in Figure 4 shows a path that satisfies the hypotheses of Lemma 13. That path corresponds to b = 010011\underline{1}011\underline{1}1 and bounces off the diagonal twice. We note that p = 000000011110 and c = 010011110001, so r(b) = 6 = z(b) + 2, z(b) = 4, and max(c) = 6.

We are now ready to state the main result of this section.

Theorem 14. The function ϕ : B_{ℓ} → C_{ℓ} takes an arrival sequence b with right lane length r(b) to a sequence of coin flips ϕ(b) = c with a max number of heads (0s) or tails (1s) satisfying max(c) = r(b).

Figure 4: A merging path satisfying the hypotheses of Lemma 13.

Proof. Let b be an arrival sequence in B_{ℓ} and c = ϕ(b). Let j denote the last index where the merging path defined by b touches the diagonal. Then by Lemma 13 we know that r(b_{1} ⋯ b_{j}) = max(c_{1} ⋯ c_{j}) = \frac{j}{2}. Moreover, the path corresponding to b_{j+1} ⋯ b_{ℓ} satisfies the hypotheses of Lemma 12 so r(b_{j+1} ⋯ b_{ℓ}) = max(c_{j+1} ⋯ c_{ℓ}). We conclude that

r(b) = r(b_{1} ⋯ b_{j}) + r(b_{j+1} ⋯ b_{ℓ}) = max(c_{1} ⋯ c_{j}) + max(c_{j+1} ⋯ c_{ℓ}) = max(c).

Figure 5 illustrates how we break a merging path into two parts. The first part is the longest subpath corresponding to b_{1} ⋯ b_{j} that ends on the diagonal and then bounces off with b_{j+1} = 1, and the second part is the remaining subpath corresponding to b_{j+1} ⋯ b_{ℓ} that satisfies the hypotheses of Lemma 12. This specific merging path corresponds to the merging sequence b = 010011\underline{1}011\underline{1}001, and in this case j = 10. The subpath corresponding to b_{1} ⋯ b_{j} = 010011\underline{1}011 ends up on the diagonal at (5, 5). The path corresponding to \underline{b_{j+1}}b_{j+2} ⋯ b_{ℓ} = \underline{1}001 has r(\underline{b_{j+1}}b_{j+2} ⋯ b_{ℓ}) = 3 = z(b_{j+1}b_{j+2} ⋯ b_{ℓ}) + 1. For this particular b = 010011\underline{1}011\underline{1}001, one can confirm that the parity vector is p = 00000001111000 and ϕ(b) = b + p = c = 01001111000001. Moreover, r(b) = r(b_{1} ⋯ b_{j}) + r(b_{j+1} ⋯ b_{ℓ}) = 5 + 3 = max(c_{1} ⋯ c_{j}) + max(c_{j+1} ⋯ c_{ℓ}) = max(c).

We use Theorem 14 to give a combinatorial proof of Theorem 6 in the following corollary.

Corollary 15. The function ϕ is a bijection. That is, the merging paths reaching the point (n, m) are in one-to-one correspondence with heads/tails sequences c with m = max(c).

Proof. Let m = max(c), where c ∈ C_{ℓ}, and let n = ℓ − m. Then the number of coin flips with maximum of m heads or tails is 2\binom{m+n}{m}, when m > n, and \binom{2n}{n} when m = n. Since these match the formulas given in Theorem 6 and ϕ is one-to-one by Proposition 11, ϕ must be a bijection. Thus, ϕ provides a combinatorial proof of Theorem 6.

Figure 5: An example of a general merging path.

4 Merging paths with exactly k red cars

We now analyze Question 2: what is the expected length of the right lane when we consider all possible arrival sequences with exactly k red cars? The following table gives the numbers R_{ℓ,k}, which is the total number of cars in the right lane when summed over all binary sequences of length ℓ and exactly k zeros.

ℓ k 0 1 2 3 4 5 6 7 8
0  0
1  1 1
2  1 3 2
3  2 6 7 3
4  2 9 16 13 4
5  3 15 31 35 21 5
6  3 19 51 76 66 31 6
7  4 28 85 147 162 112 43 7
8  4 33 120 253 344 309 176 57 8

Table 3: Sum of right lane lengths for all merging paths of length ℓ with k zeros.

To calculate the above numbers, we consider merging paths with exactly k red cars. Let W_{n,m,k} denote the set of all merging paths reaching the point (n, m) with exactly k red cars, and M_{n,k}(m) = |W_{n,m,k}| be the number of such merging paths.

Table 4 counts these paths for small values of m, n, and k, and the following lemma describes some recursive formulas for the values M_{n,k}(m). The proof is straightforward and is essentially the same as that of Lemma 5 so we omit it.

Lemma 16. The values M_{n,k}(m) satisfy the following recursive formulas:

• M_{n,k}(m) = M_{n−1,k}(m) + M_{n,k−1}(m − 1) for m > n + 1, n > 0,

• M_{n,k}(n + 1) = M_{n−1,k}(n + 1) + M_{n,k−1}(n) + M_{n,k}(n) for n > 0,

• M_{n,k}(n) = M_{n−1,k}(n) for n > 0, and

• M_{0,k}(m) = 1 when m = k or k + 1, and k > 1; and when k = 0 and m = 1.

• Otherwise, M_{0,k}(m) = 0.

k  0  1  2  3
m n 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
0  0  0  0  0
1  1 1  1 1  0 0  0 0
2  0 1 1  1 3 3  1 2 2  0 0 0
3  0 0 1 1  0 1 5 5  1 4 9 9  1 3 5 5
4  0 0 0 1 1  0 0 1 7 7  0 1 6 20 20  1 5 14 28 28
5  0 0 0 0 1 1 0 0 0 1 9 9 0 0 1 8 35 35 0 1 7 27 75 75
6  0 0 0 0 0 1 0 0 0 0 1 11 0 0 0 1 10 54 0 0 1 9 44 154

Table 4: Values of M_{n,k}(m) for small values of m, n, and k.

Let T_{ℓ,b,k} denote the set of all arrival sequences that have length ℓ, contain exactly k zeros, and whose corresponding merging path contains at least b bounces. The following proposition gives the connections between W_{n,m,k} and T_{ℓ,b,k}.

Proposition 17.

T_{m+n,m−k,k} = ⋃_{i=0}^{n} W_{n−i,m+i,k} and |T_{m+n,m−k,k}| = ∑_{i=0}^{n} M_{n−i,k}(m + i).

W_{n,m,k} = T_{m+n,m−k,k} − T_{m+n,m−k+1,k}.

Proof. For the first formula, since each sequence in T_{m+n,m−k,k} has at least m − k bounces and exactly k zeros, each merging path takes at least m steps up. Thus each such path ends weakly northwest of (n, m). The second formula follows since the number of merging paths with k zeros that end up weakly northwest of (n − 1, m + 1) is

T_{m+1+n−1,m+1−k,k} = T_{m+n,m−k+1,k}.

Let B_{ℓ,k} denote the set of binary sequences of length ℓ with exactly k zeros. The following lemma gives bounds on the number of bounces in a merging path with exactly k zeros.

Lemma 18. Let b ∈ B_{ℓ,k} be a binary string of length ℓ with k zeros, and whose merging path contains b bounces. Then

\frac{ℓ − 2k}{2} ≤ b ≤ \frac{ℓ − k + 1}{2}.

Proof. Suppose the merging path reaches the point (n, m). Then m = k+b and n = ℓ−k−b. The lower bound results from the fact that m ≥ n. For the upper bound, we note that, with the exception of an initial bounce, each bounce is preceded by a 1. Thus

b ≤ \frac{o(b) + 1}{2} = \frac{ℓ − k + 1}{2}.

Now we are ready to prove the connection between the sets T_{m+n,m−k,k} and B_{m+n,n−(m−k)+1} through an argument similar to André’s reflection method [2]. Given an arrival sequence b, let \overline{b} denote the sequence satisfying \overline{b_{i}} = (b_{i} + 1) mod 2 for all 1 ≤ i ≤ m + n. If m > k, we can write each arrival sequence b ∈ T_{m+n,m−k,k} as b = b_{1}b_{2} where the last element of b_{1} is where the (m − k)th bounce off the diagonal occurs in the corresponding merging path. We can define a map ψ : T_{m+n,m−k,k} → B_{m+n,n−(m−k)+1} that sends each b = b_{1}b_{2} to b′ = b_{1}\overline{b_{2}}. The following lemma shows that ψ is a bijection, and gives us a formula for the numbers T_{m+n,m−k,k}.

Lemma 19. If m > k and m > n, then the map ψ : T_{m+n,m−k,k} → B_{m+n,n−(m−k)+1} that sends each b = b_{1}b_{2} to b′ = b_{1}\overline{b_{2}} is a bijection. Hence

|T_{m+n,m−k,k}| = \binom{m + n}{n − (m − k) + 1}.

Proof. We start by showing that ψ is well-defined; that is, ψ sends each arrival sequence b = b_{1}b_{2} in T_{m+n,m−k,k} to an arrival sequence b′ = b_{1}\overline{b_{2}} in B_{m+n,n−(m−k)+1}. Let b = b_{1}b_{2} ∈ T_{m+n,m−k,k} be an arrival sequence of length m + n, containing exactly k zeros, and whose merging path contains at least m−k bounces. Suppose b_{1} contains j zeros for some 0 ≤ j ≤ k. In order for the last entry in b_{1} to be the (m − k)th bounce in b_{1}, it must be the case that b_{1} contains 2(m − k) − 1 + j ones. We calculate the number of ones in b_{2} as

o(b_{2}) = m + n − o(b_{1}) − z(b)
= m + n − (2(m − k) − 1 + j) − k
= n − m + k + 1 − j.

Now we calculate that the number of zeros in b′ = ψ(b) is

z(ψ(b)) = z(b_{1}\overline{b_{2}}) = z(b_{1}) + o(b_{2}) = j + (n − m + k + 1 − j) = n − (m − k) + 1.

Hence ψ sends each b = b_{1}b_{2} ∈ T_{m+n,m−k,k} to a sequence b′ = b_{1}\overline{b_{2}} with exactly n−(m−k)+1 zeros in B_{m+n,n−(m−k)+1}.

Next we show that ψ is injective. Suppose that b^{1} and b^{2} are distinct arrival sequences in T_{m+n,m−k,k}. Then either b_{1}^{1} ≠ b_{1}^{2} or b_{2}^{1} ≠ b_{2}^{2}. In either case, we see that b^{1} ≠ b^{2} implies that

ψ(b^{1}) = b_{1}^{1}\overline{b_{2}^{1}} ≠ b_{1}^{2}\overline{b_{2}^{2}} = ψ(b^{2}).

We now argue that ψ : T_{m+n,m−k,k} → B_{m+n,n−(m−k)+1} is surjective. Let b ∈ B_{m+n,n−(m−k)+1} be an arrival sequence with n − (m − k) + 1 zeros. Lemma 18 guarantees that the merging path for b will have at least m − k bounces when m > n, (we leave this as an exercise for the reader). Write b = b_{1}b_{2} where the (m − k)th bounce of its merging path is the last entry in b_{1}. Then b_{1}\overline{b_{2}} is an arrival sequence in T_{m+n,m−k,k} as it contains at least m − k bounces, and we calculate that it has exactly k zeros as follows:

• z(b_{1}) = j.

• o(b_{1}) = 2(m − k) − 1 + j.

• o(b_{2}) = m + n − o(b_{1}) − z(b) = m + n − (2(m − k) − 1 + j) − (n − (m − k) + 1) = k − j.

• z(b_{1}\overline{b_{2}}) = z(b_{1}) + o(b_{2}) = j + (k − j) = k.

Hence ψ(b_{1}\overline{b_{2}}) = b, and so ψ is a surjective map. Therefore, ψ is a bijection.

The following theorem follows from Lemma 19 and Proposition 17 and gives us one of the formulas for the merging paths M_{n,k}(m).

Theorem 20. If m > k and m > n, then

M_{n,k}(m) = \binom{m + n}{n − (m − k) + 1} − \binom{m + n}{n − (m − k) − 1}.

The previous results leave out merging paths that reach the diagonal where m = n, and merging paths where m = k. For the case when m = n, the corresponding set T_{2n,n−k,k} has size \binom{2n}{k}. The following corollary gives the formula for the merging paths reaching the diagonal M_{n,k}(n).

Corollary 21. If n ≥ k, then

M_{n,k}(n) = \binom{2n}{k} − \binom{2n}{k − 1}.

Proof. By Lemma 17 and Lemma 19, we have

M_{n,k}(n) = |W_{n,n,k}| = |T_{2n,n−k,k}| − |T_{2n,n−k+1,k}| = \binom{2n}{k} − \binom{2n}{k − 1}.

m n 0 1 2 3 4 5 6  7  8  9  10  11
6  1 6 20 48 90 132 132
7  1 8 35 110 275 572 1001 1001
8  0 1 10 54 208 637 1638 3640 3640
9  0 0 1 12 77 350 1260 3808 9996 9996
10  0 0 0 1 14 104 544 2244 7752 23256 23256
11  0 0 0 0 1 16 135 798 3705 14364 48279 48279

Table 5: Values of M_{n,k}(m) for k = 6 where the numbers along the diagonal in green are given by Corollary 21, the ballot numbers along the bottom in blue are given by Theorem 22, and the remaining numbers are given by Theorem 20.

The final case is when m = k which corresponds to the set of merging paths with zero bounces. These paths are counted by the ballot numbers [12], so we record the formula for them as the following Theorem. The proof is the original André reflection method [14].

Theorem 22.

M_{n,k}(k) = \frac{k − n + 1}{k + 1}\binom{k + n}{n} = \binom{k + n}{n} − \binom{k + n}{n − 1}.

Many of the values of M_{n,k}(m) repeat periodically. The following lemma shows where that repetition occurs, and gives a bijective proof. (The formulas above would give a trivial proof of this result.)

Lemma 23. If m > k + 1 and m > n > 0, then the number of merging paths from (0, 0) to (n, m) with exactly k zeros is equal to the number of paths from (0, 0) to (n − 1, m + 1) with exactly k + 2 zeros. In other words,

M_{n,k}(m) = M_{n−1,k+2}(m + 1).

Proof. Let b ∈ W_{n,m,k}. Since we assume that m > k + 1, the number of bounces in b is m − k > 1. Hence there is at least one bounce not at the origin. The last of these bounces off the diagonal in b comes from two consecutive 1s (the first of which occurs at one entry off the diagonal), changing those 1s to 0s creates a merging path b′ ∈ W_{n−1,m+1,k+2} that ends at (n − 1, m + 1) and has two more zeros than b. To reverse this process simply look for the last place a path b′ from (0, 0) to (n − 1, m + 1) is distance one from the diagonal. There must follow two consecutive 0s, so we replace those two entries with 1s, giving us a path to (n, m) with exactly k zeros.

Figure 6 illustrates the bijection in Lemma 23. It shows a path in W_{3,3,5} and its corresponding path in W_{2,5,7}.

Figure 6: A merging path 01\underline{1}011\underline{1}0 ending at (3,5) and a path 01\underline{1}01000 ending at (2,6).

Using the formulas in Theorem 20, Corollary 21, and Theorem 22, we can write down the formulas for the expected length of the right lane for ℓ cars with k red cars. The formula breaks into 3 cases, as illustrated in the next theorem.

Theorem 24. The expected length 𝔼[ℓ, k] of the right lane for ℓ cars with k red cars is

𝔼[ℓ, k] = (\frac{ℓ + 1}{2}\binom{ℓ}{k} + ∑_{i=0}^{k/2−1} \binom{ℓ}{k − 2i − 2})/\binom{ℓ}{k}  (4)

for ℓ ≥ 2k + 1 and ℓ odd,

𝔼[ℓ, k] = (\frac{ℓ}{2}\binom{ℓ}{k} + ∑_{i=0}^{(k−1)/2} \binom{ℓ}{k − 2i − 1})/\binom{ℓ}{k}  (5)

for ℓ ≥ 2k and ℓ even, and

𝔼[ℓ, k] = (k\binom{ℓ}{k} + ∑_{i=0}^{(ℓ−k−1)/2} \binom{ℓ}{k + 2i + 1})/\binom{ℓ}{k}  (6)

for ℓ < 2k.

Note that if we let k′ = ℓ − k in the last equation above, we get

𝔼[ℓ, k] = (k\binom{ℓ}{k} + ∑_{i=0}^{(k′−1)/2} \binom{ℓ}{k′ − 2i − 1})/\binom{ℓ}{k}

for ℓ > 2k′.

Proof. We prove only the first case when ℓ ≥ 2k + 1 and ℓ is odd, as the other cases are similar. When ℓ is odd, the minimum height of a merging path is \frac{ℓ+1}{2}, and the maximum height by Lemma 18 is m = k + b = \frac{ℓ+k+1}{2}. So,

\binom{ℓ}{k}𝔼[ℓ, k] = ∑_{i=0}^{k/2} (\frac{ℓ + 1}{2} + i) M_{\frac{ℓ−1}{2} −i,k} (\frac{ℓ + 1}{2} + i)

= ∑_{i=0}^{k/2} (\frac{ℓ + 1}{2} + i) (\binom{ℓ}{k − 2i} − \binom{ℓ}{k − 2i − 2}) .

The result follows as the sum telescopes.

Our next goal is to state a corollary similar to Corollary 8 when ℓ and k get large. For this we let the ratio k/ℓ equal a fixed constant b/a and consider the limit as ℓ and k approach infinity. In the context of the merging problem, this is saying the percentage of red cars in a certain area is constant. Before stating this corollary, we need a helpful lemma first.

Lemma 25. If a ≥ 2b, then

lim_{r→∞} ∑_{i=0}^{br} \binom{ar}{i}/r\binom{ar}{br} = 0.

Proof. First, suppose a > 2b, then

∑_{i=0}^{br} \binom{ar}{i}/\binom{ar}{br} = 1 + \frac{br}{ar − br + 1} + \frac{br(br − 1)}{(ar − br + 1)(ar − br + 2)} + ⋯

≤ 1 + \frac{br}{ar − br + 1} + (\frac{br}{ar − br + 1})^{2} + ⋯

= \frac{ar − br + 1}{ar − 2br + 1}.

Thus,

lim_{r→∞} ∑_{i=0}^{br} \binom{ar}{i}/r\binom{ar}{br} ≤ lim_{r→∞} \frac{ar − br + 1}{r(ar − 2br + 1)} = 0.

Now suppose that a = 2b. The above limit is not 0 in this case, so we handle it separately as follows. We see

∑_{i=0}^{br} \binom{2br}{i}/\binom{2br}{br} = (2^{2br−1} + \frac{1}{2}\binom{2br}{br})/\binom{2br}{br}

= 2^{2br−1}/\binom{2br}{br} + \frac{1}{2}

∼ \frac{\sqrt{brπ} + 1}{2}

using Stirling’s approximation. Thus,

lim_{r→∞} ∑_{i=0}^{br} \binom{2br}{i}/r\binom{2br}{br} = lim_{r→∞} \frac{\sqrt{brπ} + 1}{2r} = 0.

Corollary 26. Let ℓ = ar and k = br for positive integers a, b, and r. Then

lim_{ℓ→∞} \frac{𝔼[ℓ, k]}{ℓ} = \frac{1}{2}

when ℓ ≥ 2k, and

lim_{ℓ→∞} \frac{𝔼[ℓ, k]}{ℓ} = \frac{b}{a}

when ℓ < 2k.

The proof follows as the sums in Theorem 24 are partial sums of the sum in Lemma 25.

Example 27. Consider the case where there are the same even number of red and green cars; let ℓ = 4n and k = 2n. Equation (5) in Theorem 24 simplifies to

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

The same simplification occurs when k is odd.

5 A connection to domino snakes

Recall that we let B_{ℓ,k} denote the set of arrival sequences with exactly k zeros, and we let R_{ℓ,k} denote the sum of the number of cars in the right lane for all arrival sequences in B_{ℓ,k}. We noted in Section 4 that the second column of Table 3, is the sequence R_{ℓ,1} that begins:

1, 3, 6, 9, 15, 19, 28, 33, 45, 51, 66, 73, 91, 99.

These numbers are listed in the On-line Encyclopedia of Integer Sequences (OEIS) as sequence A031940, and that entry states (without proof or citations) that this sequence describes the length of the longest legal domino snake using a full set of dominoes up to [ℓ : ℓ], which we denote D_{ℓ}, and the number T_{ℓ} of edges in a longest trail on the complete graph on ℓ vertices with loops, which we denote K_{ℓ}^{∘} [16]. A domino snake is a single line of dominoes laid out so that the ends match. Example 28 shows an example of a domino snake and its corresponding trail in K_{4}^{∘}.

Example 28. Let n = 4. There will always be one domino leftover. Here is one possible longest snake of length 9, and its corresponding path in K_{4}^{∘}.

[4 : 1][1 : 1][1 : 3][3 : 2][2 : 2][2 : 4][4 : 4][4 : 3][3 : 3]

1 2 4 3

4 → 1 → 1 → 3 → 2 → 2 → 4 → 4 → 3 → 3

In this section, we prove the following result, and we give an explicit bijection between the set of cars in the right lane of all arrival sequences of length ℓ with exactly one red car and the edges in a longest trail in the complete graph with loops K_{ℓ}^{∘}.

Theorem 29. All of these sequences can be computed as:

R_{ℓ,1} = D_{ℓ} = T_{ℓ} = \begin{cases}\binom{ℓ}{2} + ℓ, & if ℓ is odd; \\ \binom{ℓ}{2} + \frac{ℓ}{2} + 1, & if ℓ is even. \end{cases}

Proof. When ℓ is odd, the degree of every vertex of K_{ℓ} is even, so there exists an Eulerian circuit of K_{ℓ}. To include the loops, simply follow the loop each time a vertex is encountered for the first time in the trail. In K_{ℓ} with loops, there are \binom{ℓ}{2} + ℓ edges and all are used in the longest trail.

When ℓ is even, construct a subgraph H_{ℓ} ≤ K_{ℓ} by removing the edges (1, 2), (3, 4), … (ℓ − 3, ℓ − 2). Then every vertex has even degree except the vertices ℓ − 1 and ℓ. There exists an Eulerian trail of H_{ℓ} with \frac{ℓ(ℓ−2)}{2} + 1 edges. The complete graph K_{ℓ} could not have a longer trail because every interior vertex of the trail must have even degree. When we add in the loops like above, we have a total of \binom{ℓ}{2}+ \frac{ℓ}{2} +1 edges. We conclude that T_{ℓ} is described by the polynomials stated above.

Next consider the ℓ arrival sequences in B_{ℓ,1}, the set of arrival sequences with exactly 1 zero (or red car). When ℓ = 2k + 1, each has \frac{ℓ+1}{2} cars in the right lane. Hence,

R_{ℓ,1} = ℓ (\frac{ℓ + 1}{2}) = \frac{ℓ^{2} + ℓ}{2} = \binom{ℓ}{2} + ℓ.

When ℓ = 2k, ℓ − 1 arrival sequences result in \frac{ℓ}{2} cars in the right lane, and one results in \frac{ℓ}{2} + 1 cars. Hence we calculate the right lane length R_{ℓ,1} = (ℓ − 1) (\frac{ℓ}{2}) + \frac{ℓ}{2} + 1 = \binom{ℓ}{2} + \frac{ℓ}{2} + 1. We conclude that R_{ℓ,1} is described by the polynomials stated above.

Finally, we note there is a natural bijection from the set of trails on K_{ℓ}^{∘} to the set of domino snakes by considering an orientation of the trail and mapping each edge (i, j) to a domino [i : j], and this bijection shows that D_{ℓ} = T_{ℓ} for ℓ ≥ 1.

We remark that it is a fun exercise to also generate these domino snakes (and longest trails) recursively, and then to show the recursion satisfies the closed formula in Theorem 29, but we will not include that here.

The rest of this section is dedicated to describing a bijective map

ρ : B_{ℓ,1} → K_{ℓ}^{∘}

that sends each car in the right lane of an arrival sequence in B_{ℓ,1} to an edge in a longest trail in K_{ℓ}^{∘}.

The definition of the map ρ : B_{ℓ,1} → K_{ℓ}^{∘} depends on the parity of ℓ and the parity of the index p where the unique zero in the arrival sequence b in B_{ℓ,1} appears. For instance, the tables in Figure 7 show the image of ρ for each string in B_{ℓ,1} for ℓ = 6 and ℓ = 7. The cars in the right lane of each arrival sequence are highlighted in color (red or blue), with the unique car corresponding to a zero in the arrival sequence highlighted in red. (The blue entries are in fact bounces, which matches our previous notation.) We note that the edges (1, 2), (3, 4), …, (2k − 3, 2k − 2) are not included in the image of ρ when ℓ = 2k, but these edges are included in the image of ρ when ℓ = 2k + 1.

\begin{matrix}b & ρ(b) & r(b) \\ 01\underline{1}1\underline{1}1 & \{(1, 1), (1, 3), (1, 5)\} & 3 \\ \underline{1}011\underline{1}1 & \{[figure: (1, 2)], (2, 2), (2, 4), (2, 6)\} & 3 \\ \underline{1}101\underline{1}1 & \{(2, 3), (3, 3), (3, 5)\} & 3 \\ \underline{1}1\underline{1}011 & \{(1, 4),[figure: (3, 4)], (4, 4), (4, 6)\} & 3 \\ \underline{1}1\underline{1}101 & \{(2, 5), (4, 5), (5, 5)\} & 3 \\ \underline{1}1\underline{1}1\underline{1}0 & \{(1, 6), (3, 6), (5, 6), (6, 6)\} & 4 \end{matrix} \begin{matrix}b & ρ(b) & r(b) \\ 01\underline{1}1\underline{1}1\underline{1} & \{(1, 1), (1, 3), (1, 5), (1, 7)\} & 4 \\ \underline{1}011\underline{1}1\underline{1} & \{(1, 2), (2, 2), (2, 4), (2, 6)\} & 4 \\ \underline{1}101\underline{1}1\underline{1} & \{(2, 3), (3, 3), (3, 5), (3, 7)\} & 4 \\ \underline{1}1\underline{1}011\underline{1} & \{(1, 4), (3, 4), (4, 4), (4, 6)\} & 4 \\ \underline{1}1\underline{1}101\underline{1} & \{(2, 5), (4, 5), (5, 5), (5, 7)\} & 4 \\ \underline{1}1\underline{1}1\underline{1}01 & \{(1, 6), (3, 6), (5, 6), (6, 6)\} & 4 \\ \underline{1}1\underline{1}1\underline{1}10 & \{(2, 7), (4, 7), (6, 7), (7, 7)\} & 4 \end{matrix}

Figure 7: Arrival sequences in B_{ℓ,1} and their images under ρ when ℓ = 6, 7.

If car c is in the right lane of the arrival sequence with a zero in position p, then ρ is defined as follows with the even ℓ on the left and the odd ℓ on the right.

ρ(c, p) = \begin{cases}(c + 1, p), & c < p, p is odd; \\ (c, p), & c ≤ p, c ≠ p − 1, p is even; \\ (p, ℓ), & c = p − 1, p is even; \\ (p, c), & c ≥ p, p is odd; \\ (p, c − 1), & c > p, p is even. \end{cases} ρ(c, p) = \begin{cases}(c + 1, p), & c < p, p is odd; \\ (p, p), & c = p; \\ (p, c), & c > p, p is odd; \\ (c, p), & c < p, p is even; \\ (p, c − 1), & c > p, p is even. \end{cases}

For the inverse map, i ≤ j for each edge (i, j) in K_{ℓ}^{∘}, again with even ℓ on the left and the odd ℓ on the right.

ρ^{−1}(i, j) = \begin{cases}(j, i), & i, j odd, i ≠ j; \\ (i − 1, i), & i, j even, j = ℓ; \\ (j + 1, i), & i, j even, j ≠ i, ℓ; \\ (i − 1, j), & i is even, j is odd; \\ (i, j), & i is odd, j is even; \\ (i, j), & i = j. \end{cases} ρ^{−1}(i, j) = \begin{cases}(j, i), & i, j odd, i ≠ j; \\ (j + 1, i), & i, j even, i ≠ j; \\ (i − 1, j), & i is even, j is odd; \\ (i, j), & i is odd, j is even; \\ (i, j), & i = j. \end{cases}

Proposition 30. The map ρ defines a bijection between the set of cars in the right lane of all the arrival sequences in B_{ℓ,1} to the set of edges in a longest trail in K_{ℓ}^{∘}. Moreover, this bijection implies that R_{ℓ,1} = T_{ℓ} for ℓ ∈ ℕ.

Proof. The map ρ is invertible when restricted to its image, and Theorem 29 proves that its image is the correct size of a longest trail in K_{ℓ}^{∘}. When ℓ is odd, the image of ρ contains all \binom{ℓ}{2} + ℓ edges in K_{ℓ}^{∘}, so it forms an Eulerian circuit in K_{ℓ}^{∘}. When ℓ is even, the image defines a longest trail in K_{ℓ}^{∘} because there are exactly two vertices in the image of ρ that have odd degree, which are the vertices labeled ℓ and ℓ−1, and moreover, vertex ℓ is adjacent to every other vertex. We conclude that the image of ρ is a connected subgraph with exactly two vertices having odd degree, so it forms a longest trail in K_{ℓ}^{∘}.

We complete this section by revisiting Example 28.

Example 31. One can see that edges in ρ(b) correspond to the edges in the longest trail 4 → 1 → 1 → 3 → 2 → 2 → 4 → 4 → 3 → 3 and also the longest domino snake [4 : 1][1 : 1][1 : 3][3 : 2][2 : 2][2 : 4][4 : 4][4 : 3][3 : 3].

\begin{matrix}b & ρ(b) & r(b) \\ 01\underline{1}1 & \{(1, 1), (1, 3)\} & 2 \\ \underline{1}011 & \{[figure: (1, 2)], (2, 2), (2, 4)\} & 2 \\ \underline{1}101 & \{(2, 3), (3, 3)\} & 2 \\ \underline{1}1\underline{1}0 & \{(1, 4), (3, 4), (4, 4)\} & 3 \end{matrix}

6 Color-blind equivalence classes

Consider the two arrival sequences a = 01\underline{1}10 and b = \underline{1}1\underline{1}10. They are equivalent in the sense that the first, third, and fifth car in each arrival sequence end up in the right lane. So, if the sides of the cars were labeled by their starting position in each arrival sequence, as depicted in Figure 8, a color-blind observer would not be able to differentiate their final structures. When we disregard color, the final structure of the cars is completely determined by the right lane vector r⃗ that records the order of the cars in the right lane. For instance, the two arrival sequences listed above have right lane vectors r⃗(01\underline{1}10) = r⃗(\underline{1}1\underline{1}10) = (1, 3, 5).

1 3 5 2 4 1 3 5 2 4 1 3 5 2 4

Direction of traffic

Figure 8: Arrival sequences 01\underline{1}10 and \underline{1}1\underline{1}10 with same r⃗ = (1, 3, 5) and their final color-blind result.

This observation leads us to define the following equivalence relation on the set of all arrival sequences B_{ℓ}: two arrival sequences a and b are color-blind equivalent a ∼ b if r⃗(a) = r⃗(b). Given an arrival sequence b ∈ B_{ℓ}, let

C(b) = {a ∈ B_{ℓ} : r⃗(a) = r⃗(b)}

denote the equivalence class of all arrival sequences who are color-blind equivalent to b.

The final structure of the right lane does not depend on whether the first car is red or green, since it will always stay in the right lane. Hence two binary strings that only differ in their first digit will have the same right lane vector r⃗, which implies the size of each color-blind equivalence class is even.

Proposition 32. Each color-blind equivalence class C(b) has an even number of elements.

In fact, if two arrival sequences only differ in places where their merging paths are touching the diagonal, then they will be in the same color-blind equivalence class. Table 6 shows the color-blind equivalence classes for all arrival sequences in B_{6}, and it highlights where the merging path for each arrival sequence touches the diagonal in orange.

Let t⃗(b) denote the vector recording the steps where the merging path of the arrival sequence b starts off touching the diagonal x = y, and t(b) be the number of times b touches the diagonal. For instance

t⃗(\underline{1}1\underline{1}100) = t⃗(010100) = (1, 3, 5) with t(\underline{1}1\underline{1}100) = t(010100) = 3,

and

t⃗(0011\underline{1}0) = t⃗(\underline{1}011\underline{1}0) = (1, 5) with t(0011\underline{1}0) = t(\underline{1}011\underline{1}0) = 2.

Our main result in this section shows that the size of a color-blind equivalence class C(b) depends only on t(b).

Theorem 33. Let b ∈ B_{ℓ} be an arrival sequence of length ℓ. Let t = t(b) be the number of times b touches the diagonal. Then the color-blind equivalence class C(b) contains 2^{t(b)} arrival sequences, or more succinctly,

|C(b)| = 2^{t}.

Proof. Every time a merging path is resting on the diagonal, the next car in the arrival sequence is forced into the right lane. So if b ∈ B_{ℓ} has t⃗(b) = (1, j_{2}, j_{3}, …, j_{d}) with t(b) = d, then we can switch some of the colors of the d cars in positions t⃗(b) = (1, j_{2}, j_{3}, …, j_{d}) that were forced into the right lane after b touched the diagonal to obtain a new merging sequence with the same right lane vector. Conversely, when a merging path is above the diagonal, changing the color of the next car always results in a different right lane vector, because when the merging path is above the diagonal, green cars always go into the left lane and red cars always go to the right. We conclude that to construct C(b) combinatorially, we simply form all arrival sequences a that agree with b in all positions outside of t⃗(b), and we have 2^{t(b)} distinct choices for parity/color of the cars in positions t⃗(b).

7 Future work

There are many possible variations on this problem, some developed by waiting in real-life traffic (as with the original problem) and some more abstract variations that may only apply

Arrival sequence Right lane Class size Arrival sequence Right lane Class size
b  r⃗(b)  |C(b)|  b  r⃗(b)  |C(b)|
000000  1, 2, 3, 4, 5, 6  2  000001  1, 2, 3, 4, 5  2
\underline{1}00000  \underline{1}00001
000010 1, 2, 3, 4, 6 2 000011 1, 2, 3, 4 2
\underline{1}00010  \underline{1}00011
000100 1, 2, 3, 5, 6 2 000101 1, 2, 3, 5 2
\underline{1}00100  \underline{1}00101
000110 1, 2, 3, 6 2 000111 1, 2, 3 2
\underline{1}00110  \underline{1}00111
001000 1, 2, 4, 5, 6 2 001001 1, 2, 4, 5 2
\underline{1}01000  \underline{1}01001
001010 1, 2, 4, 6 2 001011 1, 2, 4 2
\underline{1}01010  \underline{1}01011
001100 1, 2, 5, 6 4 001101 1, 2, 5 4
0011\underline{1}0  0011\underline{1}1
\underline{1}01100  \underline{1}01101
\underline{1}011\underline{1}0  \underline{1}011\underline{1}1
010000 1, 3, 4, 5, 6 4 010001 1, 3, 4, 5 4
01\underline{1}000  01\underline{1}001
\underline{1}10000  \underline{1}10001
\underline{1}1\underline{1}000  \underline{1}1\underline{1}001
010010 1, 3, 4, 6 4 010011 1, 3, 4 4
01\underline{1}010  01\underline{1}011
\underline{1}10010  \underline{1}10011
\underline{1}1\underline{1}010  \underline{1}1\underline{1}011
010100 1, 3, 5, 6 8 010101 1, 3, 5 8
0101\underline{1}0  0101\underline{1}1
01\underline{1}100  01\underline{1}101
01\underline{1}1\underline{1}0  01\underline{1}1\underline{1}1
\underline{1}10100  \underline{1}10101
\underline{1}101\underline{1}0  \underline{1}101\underline{1}1
\underline{1}1\underline{1}100  \underline{1}1\underline{1}101
\underline{1}1\underline{1}1\underline{1}0  \underline{1}1\underline{1}1\underline{1}1

Table 6: Arrival sequences in B_{6} partitioned into color-blind equivalence classes. Touches are highlighted in orange.

to higher-dimensional traffic jams. We encourage anyone pursuing these problems to make good use of the OEIS, as we were frequently (pleasantly) surprised at the myriad connections to other areas of combinatorics.

Our first open problem considers the possibility that red and green cars are not evenly distributed in the arrival sequence, with green cars more likely to appear earlier in the sequence. This corresponds to the notion that drivers who pick the shortest lane are also the faster drivers.

Open Problem 34. Corollary 8 and Corollary 26 give unsurprising results about what will happen to the expected length of the right lane as the number of cars gets large with the percentage of red cars held constant. How does this expected value change when we weight the arrival sequences so that sequences with more green cars in the front have a larger weight (probability of occurring)?

Our work in this article has focused solely on two lanes merging. In reality, we may encounter three or more lanes, and there are choices for how to represent this mathematically. The next open problem describes one of these possibilities.

Open Problem 35. Consider three lanes merging into a single right lane with three types of drivers:

• Those that pick the right lane only.

• Those that pick the shortest of the two right lanes.

• Those that pick the shortest of all the lanes.

How many of these merging paths reach the point (m_{1}, m_{2}, m_{3})? What is the expected length of the right lane for all arrival sequences with a specific number of drivers of each type? This could also be extended to more lanes.

Once the problem has been generalized to more lanes, it is natural to ask whether any of the connections to other combinatorial objects remains. The next two open questions address a couple of these connections.

Open Problem 36. In Section 5, we mapped a subset of arrival sequences to the longest trail in a complete graph with loops. Can we generalize this to trails in hypergraphs when there are more than two lanes? There are multiple ways to define a trail in a hypergraph [3, 7], but very little is currently known about the length of the longest trail or its connection to other combinatorial objects.

Open Problem 37. In Section 3, we found a connection to the expected maximum number of heads or tails in a set of coin flips. With n lanes, is there a connection to the expected maximum number a face appears in ℓ rolls of an n-sided die?

Another line of inquiry asks whether we are representing drivers appropriately as red or green drivers. More likely, each individual acts as a green driver with some fixed probability. However, representing drivers overall with this dichotomy likely mimics each person’s individual likelihood of choosing the left or right lane. A different situation arises if we imagine drivers only choose the left lane if it is “much” shorter than the right lane. How much shorter? We could fix it at a certain number of cars, where our work so far has consisted of the case where green drivers choose the left when it is at least 1 car shorter. Or we could let it depend on the individual driver, leading to the following open question.

Open Problem 38. Consider the merging problem where green cars only choose the left lane if it is c > 1 cars shorter than the right lane. Alternately, suppose car i is associated with a value c_{i} ∈ ℕ∪{∞} so that car i will only choose the left lane if the difference between the lane lengths is at least c_{i}.

Our final question considers the case where the left lane has a fixed length m, so that once the right lane fills up with m cars, no more cars can enter that lane. How is this real-world condition affecting cars who would like to move into that lane but are unable to?

Open Problem 39. Consider the merging problem where each lane has a capacity of m cars and arrival sequences of length 2m − 1. Once the right lane reaches m cars, then no more cars will be able to enter the left lane. What is the expected number of cars missing from the left lane?

References

[1] L. Addario-Berry and B. A. Reed, Ballot theorems, old and new, in Horizons of Combinatorics, Bolyai Soc. Math. Stud., Vol. 17, Springer, 2008, pp. 9–35.

[2] D. André, Solution directe du probléme résolu par M. Bertrand, Comptes Rendus Acad. Sci. Paris 105 (1887), 436–437.

[3] A. Bahmanian and M. Šajna, Quasi-Eulerian hypergraphs, Electron. J. Combin. 24 (2017), #P3.30.

[4] K. Humphreys, A history and a survey of lattice path enumeration, J. Statist. Plann. Inference 140 (2010), 2237–2254.

[5] C. Krattenthaler and S. G. Mohanty, Lattice path combinatorics–applications to probability and statistics, in Encyclopedia of Statistical Sciences, 2nd edition, Wiley, 2003, pp. 1–14.

[6] G. Kreweras, Sur une classe de problemes de dénombrement liés au treillis des partitions des entiers, Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche 6 (1965), 9–107.

[7] Z. Lonc and P. Naroski, On tours that contain all edges of a hypergraph, Electron. J. Combin. 17 (2010), #R144.

[8] P. A. MacMahon, Memoir on the theory of the compositions of numbers, Philos. Trans. Roy. Soc. A 184 (1893), 835–901.

[9] J. C. Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., I, II, Reprinted by Oxford Univ. Press, 1937, 1892.

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

[11] T. V. Narayana, Lattice Path Combinatorics with Statistical Applications; Mathematical Expositions 23, University of Toronto Press, 1979.

[12] H. Niederhausen and S. Sullivan, Pattern avoiding ballot paths and finite operator calculus, J. Statist. Plann. Inference 140 (2010), 2312–2320.

[13] M. Reinhard, The (n + 1)th proof of Stirling’s formula, Amer. Math. Monthly 115 (2008), 844–845.

[14] M. Renault, Lost (and found) in translation: André’s actual method and its application to the generalized ballot problem, Amer. Math. Monthly 115 (2008), 358–363.

[15] M. Saračević, S. Adamović, and E. Biševac, Application of Catalan numbers and the lattice path combinatorial problem in cryptography, Acta Polytechnica Hungarica 15 (2018), 91–110.

[16] N. J. A. Sloane and The OEIS Foundation Inc., The on-line encyclopedia of integer

    sequences, 2023, https://oeis.org.

[17] R. P. Stanley, Enumerative Combinatorics. Volume 1, 2nd ed., Cambridge Univ. Press, 2012.

[18] W. A. Whitworth, Choice and Chance, 5th ed. G. E. Stechert & Co., 1901.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A19, 05A40, 05C30, 05C38. Keywords: lattice path, ballot number, graph theory, bijection, domino snake, longest trail, traffic.

(Concerned with sequences \underline{A031940} and \underline{A230137}.)

Received May 20 2022; revised version received April 28 2023; May 19 2023; May 31 2023. Published in Journal of Integer Sequences, May 31 2023.

Return to Journal of Integer Sequences home page.