# Ballot Problem with Fixed Number of Ties:

Problem Statement: In an election, candidate A receives $m$ votes and candidate B receives $n$ notes. Let $m \ge n$. In how many ways can the ballots be counted so that ties occur exactly $r$ times ($r \le n$)?

Example: $m = 3, n = 2, r = 1$. There are 4 such scenarios: for order ABAAB, BAAAB the tie occurs at the 2nd vote; for order AABBA, BBAAA the tie occurs at the 4th vote.

Call this number $Z( m,n, r)$. My practical goal is to answer the following: Given the total number of votes $N$, how many ways can we order the ballots to have exactly $r$ ties? It is $$Z(N,r) = \sum_{n = r}^{N/ 2} Z( N-n, n ,r ) + \sum_{n = r}^{N/ 2} Z( n, N-n ,r )$$ once we figure out $Z(m,n,r)$.

It would be nice if one can get $Z(N,r)$ or its generating function directly, but I think the "$r$-tie" ballot problem is interesting on its own.

## Mapping to lattice path enumeration

Here is an equivalent form of the problem:

Consider lattice path from $(0,0)$ to point $(m,n)$ with only up $(0,1)$ or right $(1,0)$ movement in $m +n$ steps. Excluding the starting point $(0,0)$, how many lattice paths hit the (lattice point on the) diagonal line $y = x$ exactly $r$ times?

The following figure shows a lattice path that reaches (4,3) and its image under Andre's reflection. It hits the diagonal 3 times.

## $r = 0$ is the strictly monotonic path

The $r = 0$ problem can be solved by Andre's reflection principle. (method used here is similar to this ME post)

First of all $m > n$, otherwise the end point $(n,n)$ will be one touching point. Since no touching of the diagonal is allowed, the first step must go right. There are ${ m + n - 1 \choose m-1}$ such paths but we need to exclude the ones that touches the diagonal.

Suppose there is one such path (first step going right) that touches the diagonal, we can do reflection about the $y= x$ line for the path between the origin and the first intersection (see Figure). The reflected path is one that starts with up movement. Since such paths will definite cross the diagonal line to reach $(m,n)$, it is easy to see that the map is one-to-one. There are ${m+n -1 \choose n - 1}$ such paths.

In sum, the result is $$Z( m, n, 0) = { m + n - 1 \choose m - 1 } - {m+n -1 \choose n - 1} = { m + n - 1 \choose n } - {m+n -1 \choose n - 1} \quad m > n$$ which is very similar to the ballot theorem.

Any idea of approaching the general $r$?

Thanks!

## Update 1: $m = n, r = 1$ is the strictly monotonic Dyck path

The only intersection is at the end point $(n,n)$, so this is basically a Dyck path that hits the diagonal once. This ME post gives the general result for a Dyck path to hit the diagonal $k$ times. Setting $k$ = 1, the result is $\frac{1}{n}{2n - 2 \choose n-1 }$. Here the path can be either above or below the diagonal line, hence a factor of $2$, $$Z( n, n, 1 ) = \frac{2}{n}{2n - 2 \choose n-1 }$$

## Update 2: number of lattice paths that crosses the diagonal $k$ times

Call this number $C( m, n, r )$.

Kern, Malcolm; Walter, Stanley, Ballot theorem and lattice path crossings, Can. J. Stat. 6, 87-90 (1978). ZBL0387.60018. gives the result C( m,n, r ) = \left\lbrace \begin{aligned} &\frac{2(r+1)}{n} {2n \choose n - r -1 } & m = n \\ &\frac{m - n + 2r + 1}{m + n + 1} { m + n +1 \choose n - r } & m > n \\ \end{aligned} \right.

This is a relevant but different problem. Notice the difference between "touch" and "cross". Only going from one side of $y=x$ to the other is considered as a "cross". In the ballot problem, this is a change of the leading candidate, not a tie. One can check that $C( n, n, 0 )$ is twice the Catalan number.

• I posted a comment earlier but deleted due to a mistake. However this is possible using an ogf approach. Simply create an ogf that enumerates a sequence of $r$ upper and lower dyck paths followed by a single path that doesn't touch the diagonal. There are a few details to work out but say $g(x,y)=\sum 2C(n-1)(xy)^n$ where $C(m)$ is the $m^{\text{th}}$ Catalan number and $h(x,y)=\sum Z(m,n,0)x^my^n$ then I believe the generating function $f(x,y,t)=h(x,y)(1-tg(x,y))^{-1}$ is what you want and hence the coefficient of $t^rx^my^n$. I doubt there is a clean way to do this in the general case. – N. Shales Sep 1 '17 at 1:35
• @N.Shales, $g(x,y) = \sum_{n=1}^{\infty} Z(n,n,1) (xy)^n = 2 \sum_{n=1}^{\infty} C(n-1) (xy)^n = 1- \sqrt( 1 - 4xy)$ is easy to work out. But $h(x,y)$ contains hypergeometric function when first summing over $n$. I'm not sure whether $h(x,y)$ has a simple expression. – anecdote Sep 1 '17 at 1:40
• Honestly I'm not sure the general case is going to give you a simple expression. This was just my first thought though. A "pointer" if you will. I haven't even checked it for small values so there may still be mistakes (hence the comment as opposed to an answer). Just a side note: the dyke triangle does have a straightforward ogf (not in the link) but the indeterminates are different enumerators from the horizontal step $x$ and vertical step $y$ enumerators of $h(x,y)$. – N. Shales Sep 1 '17 at 2:05

I got it! It can be solved by using generating function.

## solution(updated)

$$Z( m,n, r ) = 2^r \frac{m - n + r}{m + n -r} {m + n - r \choose n - r} \quad m \ge n$$

check:

$m = 3, n = 2, r = 1$, $$Z( 3, 2, 1 ) = 2^1 \frac{3 - 2 +1}{3+2-1} {3 + 2 -1 \choose 2 - 1} = 2 \frac{2}{4} { 4 \choose 1 } = 4 \rightarrow \text{correct}$$

$m = 5, n = 3, r = 2$, this has been enumerated by @MarkusScheuer (thanks!) $$Z( 5, 3, 2 ) = 2^2 \frac{5 - 3 + 2}{5 + 3 - 2} { 5 + 3 - 2 \choose 3 - 2} = 4 \frac{4}{6} { 6 \choose 1 } = 16 \rightarrow \text{correct}$$

## diagonal case

Consider $Z(n,n,2 )$. Now we have two hits on the diagonal. Let the first hit be $(k,k)$, there are $Z( k, k, 1 ) Z( n-k, n-k, 1)$ possibilities. By enumerating the first hit, we have $$Z( n,n, 2 ) = \sum_{k=1}^{n-1} Z( k, k ,1 ) Z( n -k, n-k ,1 )$$ By using the generating function $$f(x) = \sum_{k=0}^{\infty} Z( k, k, 1 ) x^k = \sum_{k=0}^{\infty} 2 \frac{1}{k} {2k -2 \choose k - 1} = 1 - \sqrt{ 1- 4x}$$ we have $$Z( n, n, 2 ) = \text{coefficient of }x^n \text{ in } [f(x)]^2$$

Similarly, $Z( n,n, r )$ is the coefficient of $x^n$ in $[f(x)]^r$.

This result is a special case of the more general result in Spivey, Michael Z., Enumerating lattice paths touching or crossing the diagonal at a given number of lattice points, Electron. J. Comb. 19, No. 3, Research Paper P24, 6 p. (2012). ZBL1253.05020., $$Z( n, n, r ) = 2^r \left[{ 2n - r - 1 \choose n - r } - { 2n - r - 1 \choose n - r -1 }\right] = \frac{r 2^r}{2n - r }{ 2n - r \choose n - r }$$

Let me check it against my result. The generating function for $Z(n ,n, r )$ is \begin{aligned} f_r(x) &= \sum_{k =0}^{\infty} 2^r \left[{ 2k - r - 1 \choose k - r } - { 2k - r - 1 \choose k - r - 1 }\right] x^k \\ &= 2^r x^r \sum_{k=0}^{\infty} { 2k + r - 1 \choose k } - 2^r x^{r+1} \sum_{k=0}^{\infty} { 2k + r +1 \choose k }\\ &= 2^r x^r [ {}_2 F_1( \frac{r}{2}, \frac{r+1}{2}; r; 4x ) - x {}_2 F_1( \frac{r}{2}+1, \frac{r+3}{2}; r+2; 4x )]\\ &= \left[\frac{4x}{1 + \sqrt{1-4x}} \right]^r \text{ by Mathematica}\\ &= [ 1 - \sqrt{ 1- 4x} ]^r = [f(x)]^r \rightarrow \text{ correct! } \end{aligned} where I used the relation $$\sum_{k=0}^{\infty} { 2k + a \choose k } x^k = {}_2 F_1( \frac{a+1}{2}, \frac{a+2}{2}; a+1; 4x )$$

## non-diagonal case

For $m >n$, we just need to enumerate the last hitting point $$Z( m, n, r ) = \sum_{k= r}^{n} Z( k, k, r ) Z( m -k, n-k , 0 )$$

The suitable choice of generating function for the last segment (without hitting the diagonal) is $$g(x, a) = \sum_{k=0}^{\infty} Z( k, k-a, 0 ) x^k$$ so that $Z( m,n, r)$ is the coefficient of $x^m$ in $[f(x)]^r g(x, m -n )$.

The $g(x, a )$ function can be calculated similarly to the diagonal case, $$g(x, a ) = \sum_{k = 0}^{\infty} { 2k - a -1 \choose k-a} x^k - \sum_{k = 0}^{\infty} { 2k - a -1 \choose k -a - 1 }x^k = \frac{(1 - \sqrt{ 1- 4x })^a}{2^a }$$ hence $Z( m,n, r )$ is the coefficient of $x^m$ in $$\frac{( 1 -\sqrt{ 1- 4x })^{r + m - n} }{2^{m-n}}$$ which can be constructed from the diagonal case \begin{aligned} Z( m,n, r ) &= \frac{1}{2^{m-n} }Z( m, m, r+ m-n ) \\ &= 2^r \left[{m + n - r -1 \choose n - r} - {m + n - r -1 \choose n - r - 1}\right]\\ &= 2^r \frac{m - n + r }{m + n -r} {m + n - r \choose n - r} \end{aligned}

This also works for the diagonal case.

## elementary check

For fixed point $(m, n)$, the number of lattice path without restriction is \begin{aligned} \sum_{r=0}^{n} Z( m,n,r ) &= \sum_{r=0}^n 2^r \left[{m + n - r -1 \choose n - r} - {m + n - r -1 \choose n - r - 1}\right] \\ &= {m + n -1 \choose n } - {m + n -1 \choose n - 1} + 2 \left[{m + n -2 \choose n-1 } - {m + n -2 \choose n - 2} \right] + \cdots \\ &= {m + n -1 \choose n } + {m + n -2 \choose n-1 } \\ & \quad - 3 {m + n -2 \choose n - 2} + 4 \left[{m + n -3 \choose n-2 } - {m + n -3 \choose n - 4} \right]\\ &= \sum_{r=0}^{n} {m + n -r -1 \choose n - r } = \sum_{k=0}^{n}{ m-1 +k \choose m-1 } = { m \choose n } \rightarrow \text{correct} \end{aligned}

## fixed length problem

For simplicity, let the total length $n + m$ to be an odd integer $2k+1$. Since the $m < n$ case is the reflection of $m > n$, we can just count the later case and multiply by $2$. The number of all such lattice paths that hits the diagonal $r$ times is \begin{aligned} Z( 2k+1, r ) &= 2\sum_{n = r}^{k} Z( 2k +1 -n, n, r ) = 2^{r+1} \sum_{n=r}^k\left[ { 2k - r \choose n - r } - { 2k -r \choose n - r -1 } \right] \\ &= 2^{r+1} { 2k -r \choose k - r } \end{aligned}

• Very nice approach, especially with respect to the $r$-fold convolution of Catalan-numbers, which was not known to me (+1). – Markus Scheuer Sep 3 '17 at 8:57
• The answers still differ slightly. But now it should be easier to check and compare the answers. I will go through both answers soon again. Maybe you also want to go through them. – Markus Scheuer Sep 3 '17 at 8:59
• I think in case $m=n$ the binomial coefficient should be $\binom{2n-r}{n-r}=\binom{2n-r}{n}$. – Markus Scheuer Sep 3 '17 at 9:05
• Your example $Z(m,n,r)=Z(3,2,1)=4$ doesn't match the result you're stating right at the beginning. – Markus Scheuer Sep 3 '17 at 9:23
• @MarkusScheuer, thanks. If my result is correct, your equation (3) should corresponds to the product of two generating functions. It uses the same trick as the convolution of Catalan numbers. My approach uses the bridge through the Gauss hypergeometric function. You may come up with your own. I would like to be notified when we land on the same result. – anecdote Sep 3 '17 at 16:22

Note: [2017-09-17] Essential simplification due to usage of change of variable formula.

We consider the problem in terms of lattice paths with up-steps $(1,1)$ and down-steps $(1,-1)$. We use as basic building blocks Dyck paths which are paths of length $2t (t\geq 0)$ from $(0,0)$ to $(2t,0)$ which do not go beyond the $x$-axis.

The number of Dyck paths of length $2t$ is the Catalan-number $C_t=\frac{1}{t+1}\binom{2t}{t}$ with generating function \begin{align*} c(z)&=\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\\ &=\sum_{j=0}^\infty C_j z^j=\sum_{j=0}^\infty \frac{1}{j+1}\binom{2j}{j}z^j\\ &=1+z+2z^2+5z^3+14z^4+42z^5+132z^6+429z^7+\cdots \end{align*} For example the coefficient $[z^5]c(z)=42$ tells us there are $42$ paths from $(0,0)$ to $(10,0)$ which do not go beyond the $x$-axis.

We want to count the number $N(r,m,n)$ of paths starting from $(0,0)$ with $m$ up-steps, $n$ down-steps which touch (besides $(0,0)$) the $x$-axis $r\geq 1$ times with \begin{align*} 1\leq r\leq n\leq m \end{align*}

Special case: $r=1$ and $n=m$

Since $m=n$ the number of up-steps is equal the number of down-steps. We consider paths of length $2n$ starting at $(0,0)$ and ending at $(2n,0)$ which do not touch the $x$-axis in between.

We find a generating function based upon Dyck-paths:

• then we take all Dyck-paths of length $2n-2$ and

• finish with a down-step,

• or we start with a down-step, take all Dyck-paths of length $2n-2$ and finish with an up-step.

This way it is guaranteed that we never touch or cross the $x$-axis between start and end point.

The corresponding generating function is $2zc(z)$, with $z$ representing the starting up-, resp. starting down-step. The factor $2$ respects two possibilities up, resp. down. The number $N(1,n,n)$ is therefore \begin{align*} \color{blue}{N(1,n,n)}&=[z^n](2zc(z))=2[z^{n-1}]c(z)=2C_{n-1}\\ &=\frac{2}{n}\binom{2n-2}{n-1}\\ &\color{blue}{=\frac{2}{2n-1}\binom{2n-1}{n}} \end{align*}

Special case: $1\leq r\leq n=m$

Concatenation of $r$ paths as described in the step before gives paths from $(0,0)$ to $(2n,0)$ which touch the $x$-axis $r$ times, the last time at $(2n,0)$. Concatenation means multiplication of the corresponding generating functions and we so obtain

\begin{align*} \color{blue}{N(r,n,n)}&=[z^n](2zc(z))^r=[z^n](1-\sqrt{1-4z})^r\tag{1}\\ \end{align*}

In order to derive the coefficients of the generating function in (1) we use the following

Change of variable formula: Let $f(z)$ be a Laurent series and $g(w)$ be a power series, $g(w)=g_1w+g_2w^2+\cdots$, where $g_1\ne 0$. Then \begin{align*} \color{blue}{[z^{-1}]f(z)=[w^{-1}]f(g(w))g^\prime(w)}\tag{2} \end{align*}

See e.g. p.12 of this presentation by Ira Gessel.

We use the transformation \begin{align*} z=\frac{w}{(1+w)^2}\qquad\qquad\frac{dz}{dw}=\frac{1-w}{(1+w)^3} \end{align*} and get \begin{align*} 1-\sqrt{1-4z}=\frac{2w}{1+w} \end{align*}

We obtain from (2) \begin{align*} \color{blue}{[z^p]\left(1-\sqrt{1-4z}\right)^q} &=[z^{-1}]z^{-p-1}\left(1-\sqrt{1-4z}\right)^q\\ &=[w^{-1}]\left(\frac{w}{(1+w)^2}\right)^{-p-1}\left(\frac{2w}{1+w}\right)^q\frac{1-w}{(1+w)^3}\\ &=2^q[w^{p-q}](1+w)^{2p-q-1}(1-w)\\ &=2^q\left[\binom{2p-q-1}{p-q}-\binom{2p-q-1}{p-q-1}\right]\\ &=2^q\left[\binom{2p-q}{p-q}-2\binom{2p-q-1}{p-q-1}\right]\\ &=2^q\left[\binom{2p-q}{p-q}-2\cdot\frac{p-q}{2p-q}\binom{2p-q}{p-q}\right]\\ &=\color{blue}{\frac{2^qq}{2p-q}\binom{2p-q}{p-q}}\tag{3} \end{align*}

In case $N(r,n,n)$ we set in (3) $p=n$ and $q=r$ and obtain

We obtain with (2) \begin{align*} \color{blue}{N(r,n,n)}&=[z^n]\left(1-\sqrt{1-4z}\right)^r\\ &=\color{blue}{\frac{2^rr}{2n-r}\binom{2n-r}{n-r}}\tag{4} \end{align*}

One additional aspect is to consider for the general case.

General case: $1\leq r\leq n\leq m$

The general case $1\leq r \leq n< m$ means we have $r$ blocks as above which uses at least $r$ up-steps, one for each block and at most $n$ up-steps within the $r$ blocks, i.e. before we touch the $x$-axis the last time.

In general we use $r\leq t\leq n$ up-steps within the $r$ blocks, leaving $m-t$ up-steps and $n-t$ down-steps. Since $m\geq n$ the number $m-t$ of up-steps is greater or equal than the number of $n-t$ down-steps.

The $m-t$ up-steps and $n-t$ down steps are used to build paths from $(0,0)$ to \begin{align*} (m-t)(1,1)+(n-t)(1,-1)=(m+n-2t,m-n) \end{align*} which start with an up-step and stay above the $x$-axis. According to Andre's reflection lemma is the number of paths from $(0,0)$ to $(m+n-2t,m-n)$ which do not cross the $x$-axis given as \begin{align*} \frac{m-n}{m+n-2t}\binom{m+n-2t}{m-t}\tag{5} \end{align*}

In (4) we do not have a factor $2^{m-n}$ since we consider only paths which are beyond the $x$-axis.

Note:

• Observe the structure of the binomial coefficient in (5) is the same as in (2) with $p=m-t$ and $q=m-n$.

• Combinatorially this means the number of paths of length $m+n$ which start in $(0,0)$ with an up-step and end in $(m,m-n)$ at height $m-n=r$ and never touch the $x$-axis is the same as the number of paths of length $2m$ from $(0,0)$ to $(2n,0)$ which start with an up-step go never beyond the $x$-axis and touch the $x$ axis $r$ times, the last time at $(2n,0)$.

• Alebraically this implies \begin{align*} [z^{m-t}]\left(\frac{1-\sqrt{1-4z}}{2}\right)^{m-n} =\frac{m-n}{m+n-2t}\binom{m+n-2t}{m-t}\tag{6} \end{align*}

We finally conclude from (4) and (6):

The number $N(r,m,n)$ of valid paths is \begin{align*} \color{blue}{N(r,m,n)}&=\sum_{t=r}^n[z^t]\left(2zc(z)\right)^r [z^{m-t}](zc(z))^{m-n}\\ &=\frac{1}{2^{m-n}}\sum_{t=r}^n[z^t]\left(2zc(z)\right)^r [z^{m-t}](2zc(z))^{m-n}\\ &=\frac{1}{2^{m-n}}[z^m](2zc(z))^{m-n+r}\\ &=\frac{1}{2^{m-n}}[z^m](1-\sqrt{1-4z})^{m-n+r}\\ &\color{blue}{=2^r\frac{m-n+r}{m+n-r}\binom{m+n-r}{n-r}}\\ \end{align*}

Example: $N(1,3,2)$

Let's calculate OPs example $N(1,3,2)$ counting the number of paths which touch the $x$-axis $r=1$ time consisting of $m=3$ up-steps and $n=2$ down-steps. We obtain from (3) \begin{align*} \color{blue}{N(1,3,2)}&=2\cdot\frac{2}{4}\binom{4}{1} \color{blue}{= 4} \end{align*} Encoding up-steps with $U$ and down-steps with $D$ the valid paths are

\begin{align*} D\ D\ U\ \color{blue}{U}\ U\\ D\ \color{blue}{U}\ U\ U\ D\\ U\ \color{blue}{D}\ U\ U\ D\\ U\ U\ D\ \color{blue}{D}\ U\\ \end{align*}

Blue characters mark touching the $x$-axis.

Example: $N(2,5,3)$

One more example with paths consisting of $5$ up-steps and $3$ down-steps touching the $x$-axis twice. We obtain from (3) \begin{align*} \color{blue}{N(2,5,3)}&=2^2\cdot\frac{4}{6}\binom{6}{1} \color{blue}{= 16} \end{align*}

The $16$ valid paths

Blue characters mark touching the $x$-axis.

• I think we essentially use the same method of multiplying the generating functions. But here the product of the Catalan numbers is not spelled out. Can you show, presumably using Catalan number identities, that your result is identical to mine? (or perhaps point out my mistake) Thanks. – anecdote Sep 3 '17 at 1:00
• @anecdote: I've updated my answer with considerable simplifications inspired by this answer. It clearly shows the strong relationship between our approaches. – Markus Scheuer Sep 17 '17 at 13:57
• OK, the change of variable technique (residue theorem) avoids the use the Catalan number or hypergeometric identities. Thanks for teaching me this! – anecdote Sep 17 '17 at 18:11
• @anecdote: You're welcome. Now it's also a satisfying answer for me compared with my former approach. :-) – Markus Scheuer Sep 17 '17 at 18:16

I came up with a visual proof of $$Z(m,n, r ) = 2^r \frac{m - n + r}{m + n - r} { m + n - r \choose n- r }$$ that is mush easier than my generating function approach. I think it deserves a separate answer.

## The $2^r$ factor

Divide a lattice path of $r$ intersections with the diagonal into $r$ segments where the $i$-th segment is between the $i$-th intersection point and the $i+1$-th.

Each segment is a lattice path that intersects the diagonal only at the end point and there are two possibilities: going above or blow the $y = x$ line. Hence we can consider only the lattice path below $y = x$ (shown in left figure below). Call the corresponding number of lattice paths to be $Z_{-}( m,n, r )$, we have $$Z( m, n, r ) = 2^r Z_{-} ( m, n, r )$$

## Reduction to $r = 0$

Take a lattice path below the line $y= x$. At all the intersection points, the preceding step must be going up (labeled blue in the left figure).

If we remove those blue steps, we end up with a path on the right figure that starts from $(0,0)$ and ends at $(m, n - r)$. This path will not hit the diagonal $y = x$. On the other hand, we can also reconstruct the original path by drawing backwards and complementing a blue step when hitting diagonal. For the example in the right figure, we first move the last red step "going right" to the place between $(m-1,n)$ and $(m,n)$. If it hits the diagonal(it does), we complement a blue step; otherwise we pick up the previous red step.

This procedure establish a one-to-one correspondence between the path from $(0,0)$ to $(m,n)$ below $y= x$ that hits the diagonal $r$ times, with the path from $(0,0)$ to $( m, n-r)$ that does not hit the diagonal at all.

Equivalently, $$Z_{-} ( m, n, r ) = Z( m, n -r, 0)$$

## Conclusion

We therefore conclude that $$Z(m,n, r ) = 2^r Z(m,n-r, 0) = 2^r \left[ { m + n - r - 1\choose n- r }-{m + n -r -1 \choose n- r - 1 }\right] = 2^r \frac{m - n + r}{m + n - r} { m + n - r \choose n- r }$$

• @MarkusScheuer, this visual proof convinces me that my solution is correct. – anecdote Sep 3 '17 at 19:37
• (+1) And I thought that there wasn't a nice solution! This post and it's answers from yourself and @MarkusScheuer are very valuable. I especially like the bijection here, good work everyone and thanks for the interesting question! – N. Shales Sep 3 '17 at 23:59