Two Game-Set Inequalities

Walter Shur 11 Middle Road Port Washington, NY 11050 USA

                      shur@optonline.net

Abstract

Two players compete in a contest where the first player to win a specified number of points wins the game, and the first player to win a specified number of games wins the set. This paper proves two generalized inequalities, each independent of the probability of winning a point, concerning the better player’s chances of winning. Counterexamples are given for two additional conjectured inequalities. A sequence of integers which plays a significant role in this paper can be found in A033820 of the On-line Encyclopedia of Integer Sequences.

1 Introduction

A and B play a set of games. The winner of each game is the first player to win k points, and the winner of the set is the first player to win n games. The probabilities that A and B win each point are p and q, respectively, with p + q = 1. Let P (n, k, p) and Q(n, k, p) be the probabilities that A wins and loses the set, respectively . Let P (n, p) = P (n, 1, p) = P (1, n, p) and Q(n, p) = Q(n, 1, p) = Q(1, n, p) be the probabilities that A wins and loses an n point game, respectively. (Note that P (n, k, p) = P (n, P (k, p)) and Q(n, k, p) = Q(n, P (k, p)). This paper proves the following two theorems:

Theorem 1. If n ≥ 2, k ≥ 2, and .5 < p < 1, then P (n, k, p) > P (nk, p).

Theorem 2. If 2 ≤ k < n and .5 < p < 1, then P (n, k, p) > P (k, n, p).

2 Proofs

Lemma 1. P (k, p) = \frac{1}{2} + \frac{1}{2}(p − q) ∑_{i=0}^{k−1} \binom{2i}{i}(pq)^{i}.

Proof. We show first that

P (k + 1, p) − P (k, p) = \frac{1}{2}(p − q)\binom{2k}{k}(pq)^{k}, k ≥ 1.  (1)

The only (k + 1)-point games in which the winner might be different than the winner of the k-point game are those which are tied at k points each.

The increase in A’s chance of winning a k + 1-point game over his chance of winning a k-point game is the excess of (a) the probability that there is a k-point tie, B having won the k-point game, and A wins the next point, over (b) the probability that there is a k-point tie, A having won the k-point game, and B wins the next point. Note that in half of those tied games, B won the k-point game, and in the other half, A won the k-point game. Since \binom{2k}{k}(pq)^{k} is the probability of a k-point tie, (1) holds.

Lemma 1 is true since it is true for k = 1, and its right hand side simply sums the differences in (1).

Lemma 2. Let a_{k,i} := \frac{1}{2}\binom{2k}{k}\binom{2i}{i}\frac{k}{k + i}. Then P (k, p)Q(k, p) = (pq)^{k} ∑_{i=0}^{k−1} a_{k,i}(pq)^{i},

(Note that a_{k,i} is equal to a_{k+i−1,k−1} in A033820 of the On-line Encyclopedia of Integer Sequences.)

Proof. We see from Lemma 1, noting that −(p − q)^{2} = 4pq − 1, that

P (k, p)Q(k, p) = \frac{1}{4} + \frac{1}{4}(4pq − 1) (∑_{i=0}^{k−1} \binom{2i}{i}(pq)^{i})^{2} .  (2)

Since

(∑_{i=0}^{∞} \binom{2i}{i}(pq)^{i})^{2} = (\frac{1}{\sqrt{1 − 4pq}} )^{2} = ∑_{i=0}^{∞} 4^{i}(pq)^{i},

we see that if 1 ≤ t ≤ k − 1, the coefficient of (pq)^{t} in (2) equals \frac{1}{4} · 4 · 4^{t−1} − \frac{1}{4} · 4^{t} = 0, and equals 0 for t = 0 as well.

Hence, we can define a_{k,i} such that

P (k, p)Q(k, p) = (pq)^{k} ∑_{i=0}^{k−1} a_{k,i}(pq)^{i}.  (3)

Thus, a_{k,t−k} is the coefficient of (pq)^{t} in (2).

We have, then

a_{k,t−k} = ∑_{j=t−k}^{k−1} \binom{2j}{j}\binom{2t − 2j − 2}{t − j − 1} − \frac{1}{4} ∑_{j=t−k+1}^{k−1} \binom{2j}{j}\binom{2t − 2j}{t − j}

= \binom{2t − 2k}{t − k}\binom{2k − 2}{k − 1} + ∑_{j=t−k+1}^{k−1} \binom{2j}{j} (\binom{2t − 2j − 2}{t − j − 1} − \frac{1}{4}\binom{2t − 2j}{t − j})

= \binom{2t − 2k}{t − k}\binom{2k − 2}{k − 1} + \frac{1}{2} ∑_{j=t−k+1}^{k−1} \binom{2j}{j}\binom{2t − 2j − 2}{t − j − 1}\frac{1}{t − j} . (4)

Let g(t, j) = \frac{j(2t − 2j − 1)\binom{2j}{j}\binom{2t−2j−2}{t−j−1}}{(t − j)t}.

We show that

\binom{2j}{j}\binom{2t − 2j − 2}{t − j − 1}\frac{1}{t − j} = g(t, j + 1) − g(t, j)  (5)

by dividing both sides of the equation by \binom{2j}{j}\binom{2t−2j−2}{t−j−1} to obtain

\frac{1}{t − j} = \frac{1 + 2j}{t} − \frac{j(2t − 2j − 1)}{(t − j)t} = \frac{1}{t − j} .

Let S(t, k) equal the sum in (4). By summing both sides of (5) from j = t − k + 1 to k − 1, we see that S(t, k) is equal to g(t, k) − g(t, t − k + 1), and we have

S(t, k) = \frac{k(2t − 2k − 1)\binom{2k}{k}\binom{2t−2k−2}{t−k−1}}{(t − k)t} − \frac{(t − k + 1)(2k − 3)\binom{2t−2k+2}{t−k+1}\binom{2k−4}{k−2}}{(k − 1)t}.

We see from (4) that

a_{k,t−k} = \binom{2t − 2k}{t − k}\binom{2k − 2}{k − 1} + \frac{1}{2}S(t, k).

Dividing both sides by \binom{2k}{k}\binom{2t−2k}{t−k}, we have

\frac{a_{k,t−k}}{\binom{2k}{k}\binom{2t−2k}{t−k}} = \frac{k}{4k − 2} + \frac{1}{2} (\frac{k}{2t} − \frac{k(2t − 2k + 1)}{2(2k − 1)t}) = \frac{k}{2t}.

Replacing t by k + i gives

a_{k,i} = \frac{1}{2}\binom{2k}{k}\binom{2i}{i}\frac{k}{k + i}.

Lemma 3.

P′(k, p) = \frac{1}{2}k\binom{2k}{k}(pq)^{k−1}, where the derivative is taken with respect to p. Proof. The probability that A wins a k-point game on the (k + i)^{th} point played is

p^{k}\binom{k − 1 + i}{i}(1 − p)^{i}.

Hence,

P (k, p) = p^{k} ∑_{i=0}^{k−1} \binom{k − 1 + i}{i}(1 − p)^{i} = p^{k} ∑_{j=0}^{k−1}(−1)^{j} (∑_{i=j}^{k−1} \binom{i}{j}\binom{k − 1 + i}{i}) p^{j}.

We have

∑_{i=j}^{k−1} \binom{i}{j}\binom{k − 1 + i}{i} = ∑_{i=j}^{k−1} \binom{k − 1 + i}{i − j}\binom{k − 1 + j}{j} = \binom{k − 1 + j}{j}\binom{2k − 1}{k + j}

= \frac{k}{k + j} \binom{k + j}{j}\binom{2k − 1}{k + j} = \frac{1}{2}\binom{2k}{k}\binom{k − 1}{j}\frac{k}{k + j} .

Hence,

P (k, p) = \frac{1}{2}k\binom{2k}{k} ∑_{j=0}^{k−1}(−1)^{j}\binom{k − 1}{j}\frac{1}{k + j} p^{k+j}.

Taking the derivative with respect to p, we have

P′(k, p) = \frac{1}{2}k\binom{2k}{k} ∑_{j=0}^{k−1}(−1)^{j}\binom{k − 1}{j}p^{k+j−1} = \frac{1}{2}k\binom{2k}{k}(pq)^{k−1}.

Lemma 4. The function

r_{n,k}(p) = \frac{P′(n, k, p)}{P′(nk, p)}

is a decreasing function of p, for .5 ≤ p < 1.

Proof.

r_{n,k}(p) = \frac{P′(n, k, p)}{P′(nk, p)} = \frac{P′(n, P (k, p))}{P′(nk, p)}

= \frac{\frac{1}{2}n\binom{2n}{n} (P (k, p)Q(k, p))^{n−1} \frac{1}{2}k\binom{2k}{k}(pq)^{k−1}}{\frac{1}{2}nk\binom{2nk}{nk}(pq)^{nk−1}}

= \frac{1}{2} \frac{\binom{2n}{n}\binom{2k}{k} (P (k, p)Q(k, p))^{n−1}}{\binom{2nk}{nk}(pq)^{k(n−1)}} ,  .5 ≤ p < 1.  (6)

Substituting from Lemma 2, we have

r_{n,k}(p) = \frac{1}{2} \begin{matrix}\binom{2n}{n} & \binom{2k}{k} \\ ( & {2nk \atop nk} & ) \end{matrix} (∑_{i=0}^{k−1} a_{k,i}(pq)^{i})^{n−1} ,

where a_{k,i} = \frac{1}{2}\binom{2k}{k}\binom{2i}{i}\frac{k}{k + i}.

Since a_{k,i} > 0, and pq is a decreasing function of p, it follows that r_{n,k}(p) is a decreasing function of p.

Lemma 5. If 2 ≤ t ≤ m, then

4^{t} \begin{matrix}( & {2m−2t \atop m−t} & ) \\ ( & {2m \atop m} & ) \end{matrix} \frac{2m − t}{m} > 2 .

Proof. For t = 2, the left hand side of Lemma 5 reduces to

\frac{8(m − 1)^{2}}{(2m − 1)(2m − 3)} = 2 + \frac{2}{(2m − 1)(2m − 3)}

which is clearly greater than 2 when m ≥ 2. We show by induction that Lemma 5 holds for all t. Suppose it is true for some t, and consider the left hand side of Lemma 5 with t replaced by t + 1. We have,

4^{t+1} \begin{matrix}( & {2m−2t−2 \atop m−t−1} & ) \\ ( & {2m \atop m} & ) \end{matrix} \frac{2m − t − 1}{m} = 4 (4^{t} \begin{matrix}( & {2m−2t \atop m−t} & ) \\ ( & {2m \atop m} & ) \end{matrix} \frac{2m − t}{m}) \frac{(m − t)^{2}}{(2m − 2t − 1)(2m − 2t)} \frac{2m − t − 1}{2m − t}

> \frac{4(m − t)(2m − t − 1)}{(2m − 2t − 1)(2m − t)}.

The right hand side of the inequality is greater than 2 when m > t since

\frac{4(m − t)(2m − t − 1)}{(2m − 2t − 1)(2m − t)} = 2 + \frac{2t}{(2m − 2t − 1)(2m − t)}.

When m = t, and t ≥ 2, it is shown easily by induction that \frac{4^{t}}{\binom{2t}{t}} > 2.

Lemma 6. If n ≥ 2 and k ≥ 2, then r_{n,k}(.5) > 1. Proof. Noting that P (k, .5) = Q(k, .5) = .5, we have from (6),

r_{n,k}(.5) = \frac{1}{2} \begin{matrix}\binom{2n}{n} & \binom{2k}{k} \\ ( & {2nk \atop nk} & ) \end{matrix}4^{(k−1)(n−1)}.

Lemma 6 is true for k = 2, since we have

r_{n,2}(.5) = 3 4^{n−1} \begin{matrix}( & {2n \atop n} & ) \\ ( & {4n \atop 2n} & ) \end{matrix} > 1,

and we apply Lemma 5 with m = 2n and t = n.

We show by induction that Lemma 6 holds for all k. Suppose it is true for some k, and consider Lemma 6 with k replaced by k + 1.

r_{n,k+1}(.5) = \frac{1}{2} \begin{matrix}\binom{2n}{n} & \binom{2k+2}{k+1} \\ ( & {2nk+2n \atop nk+n} & ) \end{matrix}4^{k(n−1)}

= 4^{n−1} (\frac{1}{2} \begin{matrix}\binom{2n}{n} & \binom{2k}{k} \\ ( & {2nk \atop nk} & ) \end{matrix}4^{(k−1)(n−1)}) \frac{(2k + 2)(2k + 1)}{(k + 1)^{2}} \begin{matrix}( & {2nk \atop nk} & ) \\ ( & {2nk+2n \atop nk+n} & ) \end{matrix}

> \frac{1}{2}4^{n} \begin{matrix}( & {2nk \atop nk} & ) \\ ( & {2nk+2n \atop nk+n} & ) \end{matrix} \frac{2k + 1}{k + 1} > 1.

The final inequality is obtained by applying Lemma 5 with m = nk + n and t = n.

Theorem 1. If n ≥ 2, k ≥ 2, and .5 < p < 1, then P (n, k, p) > P (nk, p). Proof. We have P (n, k, .5) = P (nk, .5) = .5, and P (n, k, 1) = P (nk, 1) = 1.

If there existed a point p_{1}, .5 < p_{1} < 1, such that P (n, k, p_{1}) = P (nk, p_{1}), then r_{n,k}(p) = \frac{P′(n, k, p)}{P′(nk, p)} would need to be 1 at least twice, once on the interval .5 < p < p_{1} and once on the interval p_{1} < p < 1 (since r_{n,k}(p) cannot be greater than 1 (or less than 1) over the full extent of either interval). But r_{n,k}(p) cannot be 1 at least twice because we know from Lemma 4 that r_{n,k}(p) is a decreasing function of p. Hence, either P (n, k, p) > P (nk, p), or P (nk, p) > P (n, k, p), on the interval .5 < p < 1. Since we know from Lemma 6 that r_{n,k}(.5) > 1, we must have P (n, k, p) > P (nk, p) over that same range.

Lemma 7. Let

f(n, x) = ∑_{i=0}^{n−1} a_{n,i}x^{i}.

If the function

h(n, k, x) = (n − 1)f(n, x)f′(k, x) − (k − 1)f(k, x)f′(n, x)

has at most one positive zero, then the functions P (n, k, p) and P (k, n, p) cannot intersect on the interval .5 < p < 1.

Proof. Let

R_{n,k}(p) = \frac{P′(n, k, p)}{P′(k, n, p)}.

Looking at the proof of Lemma 4 we see that

R_{n,k}(p) = \frac{\frac{1}{2}n\binom{2n}{n} (P (k, p)Q(k, p))^{n−1} \frac{1}{2}k\binom{2k}{k}(pq)^{k−1}}{\frac{1}{2}k\binom{2k}{k} (P (n, p)Q(n, p))^{k−1} \frac{1}{2}n\binom{2n}{n}(pq)^{n−1}} .

Substituting from Lemma 2, and simplifying, we have

R_{n,k}(p) = \frac{f(k, pq)^{n−1}}{f(n, pq)^{k−1}} , .5 ≤ p < 1.

Following the simple argument made in the the proof of Theorem 1, if P (n, k, p) and P (k, n, p) intersected on .5 < p < 1, R_{n,k}(p) would equal 1 at least twice on that interval. Furthermore, since f(n, .25) = 4^{n−1} and f(k, .25) = 4^{k−1} (see Lemma 2 with p = .5 and pq = .25), R_{n,k}(.25) = 1. Hence, there would be at least three different values of pq for which R_{n,k}(p) = 1.

Therefore, the logarithm of R_{n,k}(p) would equal 0 at least three times, and the derivative of that logarithm with respect to pq would equal 0 at least twice. The derivative of the logarithm of R_{n,k}(p) with respect to pq is equal to

\frac{h(n, k, pq)}{f(n, pq)f(k, pq)},

proving the Lemma.

Lemma 8. Let {a_{i}}_{1}^{n} be a sequence such that a_{1} < 0, ∑_{i=1}^{n} a_{i} ≤ 0 and such that either Case 1: a_{i} ≤ 0 if 2 ≤ i ≤ n, or Case 2: there exists a t ≤ n such that a_{i} ≤ 0 if 2 ≤ i < t, and a_{i} > 0 if i ≥ t. holds.

Let {r_{i}}_{1}^{n} be a sequence such that for all i, r_{i} > 0 and r_{i+1} < r_{i}.

Then ∑_{i=1}^{n} r_{i}a_{i} < 0.

Proof. The Lemma is obvious for Case 1.

For Case 2, ∑_{i=1}^{n} r_{i}a_{i} − ∑_{i=1}^{n} r_{t}a_{i} < 0, since (r_{1} − r_{t})a_{1} is negative, and if i > 1, r_{i} − r_{t} is

positive when a_{i} is negative or zero, and zero or negative when a_{i} is positive. Hence,

∑_{i=1}^{n} r_{i}a_{i} < ∑_{i=1}^{n} r_{t}a_{i} ≤ 0.

Lemma 9. Each of the ratios \frac{a_{n,t}}{a_{n,t−1}} and \frac{a_{n+1,t}}{a_{n,t−1}} decreases as t decreases.

Proof.

\frac{a_{n,t}}{a_{n,t−1}} − \frac{a_{n,t−1}}{a_{n,t−2}} = \frac{2 (1 + n^{2} + 2n(t − 1) + t(3t − 5))}{t(t − 1)(n + t − 1)(n + t)},

which is positive for t ≥ 2 and n ≥ 3.

\frac{a_{n+1,t}}{a_{n,t−1}} − \frac{a_{n+1,t−1}}{a_{n,t−2}} = \frac{4(2n + 1) (n(n − 1) + 2nt + t(5t − 7))}{(t − 1)tn(n + t)(n + 1 + t)},

which is positive for t ≥ 2 and n ≥ 3.

We note that, as defined, the quantity R_{n,k}(1) is indeterminate. We take R_{n,k}(1) to mean

lim_{p→1} R_{n,k}(p).

Lemma 10. If 1 < k < n then R_{n,k}(1) < 1.

Proof. Noting that pq = 0 when p = 1,

R_{n,k}(1) = \frac{f(k, 0)^{n−1}}{f(n, 0)^{k−1}} = \frac{a_{k,0}^{n−1}}{a_{n,0}^{k−1}} = \begin{matrix}(\frac{1}{2} \binom{2k}{k}) & n−1 \\ (\frac{1}{2} \binom{2n}{n}) & k−1 \end{matrix} ,

Let u_{n,k} = \frac{R_{n+1,k}(1)}{R_{n,k}(1)} = (\frac{n + 1}{4n + 2})^{k−1} \frac{1}{2}\binom{2k}{k}, and

Let v_{n,k} = \frac{u_{n,k+1}}{u_{n,k}} = \frac{n + 1}{4n + 2} /\frac{k + 1}{4k + 2}

It is assumed in the following that 1 < k < n.

v_{n,k} < 1, since n > k, and the function \frac{r+1}{4r+2} is a decreasing function of r ;

Since v_{n,k} < 1, u_{n,k} is a decreasing function of k, and since u_{n,1} = 1, u_{n,k} < 1; Since u_{n,k} < 1 , R_{n,k}(1) is a decreasing function of n, and since R_{k,k}(1) = 1, R_{n,k}(1) < 1.

Theorem 2. If 2 ≤ k ≤ n and .5 < p < 1, then P (n, k, p) > P (k, n, p).

Proof. The h(n, k, x) of Lemma 7 can be written as

h(n, k, x) = (n − 1) ∑_{i=0}^{n−1} a_{n,i}x^{i} ∑_{i=0}^{k−1} ia_{k,i}x^{i−1} − (k − 1) ∑_{i=0}^{k−1} a_{k,i}x^{i} ∑_{i=0}^{n−1} ia_{n,i}x^{i−1} = ∑_{r=0}^{n+k−3} c_{n,k,r}x^{r}.

We show that h(n, k, x) has at most one positive zero by showing that the sequence {c_{n,k,r}}_{r=0}^{n+k−3} has exactly one change in sign, and applying Descartes’ Rule of Signs.

We do this by considering four cases,

Case 1: 0 ≤ r ≤ k − 2. We show that c_{n,k,r} > 0. Case 2: k − 1 ≤ r ≤ n − 2. We show that if c_{n,k,r} ≤ 0, then c_{n,k,r+1} < 0. Case 3: n − 1 ≤ r ≤ n + k − 4. We show that c_{n,k,r} < 0. Case 4: r = n + k − 3. We show that c_{n,k,r} = 0.

Case 1: 0 ≤ r ≤ k − 2.

c_{n,k,r} = ∑_{j=0}^{r+1} ((n − 1)j − (k − 1)(r + 1 − j)) a_{k,j}a_{n,r+1−j}.

We see that c_{n,k,r} is an increasing function of n, since the bracketed term in c_{n,k,r} is an increasing funtion of n, and

\frac{a_{n+1,t}}{a_{n,t}} = 1 + \frac{3n^{2} + n + 2t + 3nt}{n(n + t + 1)} > 1.

Since c_{k,k,r} = 0, c_{n,k,r} > 0.

Case 2: k − 1 ≤ r ≤ n − 2.

c_{n,k,r} = ∑_{j=0}^{k−1} ((n − 1)j − (k − 1)(r + 1 − j)) a_{k,j}a_{n,r+1−j}

Let

b(n, k, r, j) = ((n − 1)j − (k − 1)(r + 2 − j)) a_{k,j}a_{n,r+1−j},

so that

c_{n,k,r+1} = ∑_{j=0}^{k−1} b(n, k, r, j)\frac{a_{n,r+2−j}}{a_{n,r+1−j}} .

We see that b(n, k, r, 0) < 0, the bracketed term in b(n, k, r, j) increases as j increases, and if c_{n,k,r} ≤ 0, then ∑_{j=0}^{k−1} b(n, k, r, j) < 0(since the bracketed term in b(n, k, r, j) is less than the bracketed term in c_{n,k,r}). Furthermore, we know from Lemma 9 that the sequence \{\frac{a_{n,r+2−j}}{a_{n,r+1−j}} \} is decreasing as j increases.

Hence the conditions set forth in Lemma 8 are met, and we have c_{n,k,r+1} < 0.

Case 3: n − 1 ≤ r ≤ n + k − 4.

Let r = n − 1 + t, 0 ≤ t ≤ k − 3.

c_{n,k,n−1+t} = ∑_{j=t+1}^{k−1} ((n − 1)j − (k − 1)(n + t − j)) a_{k,j}a_{n,n+t−j}.

Let b(n, k, t, j) = (nj − (k − 1)(n + 1 + t − j)) a_{k,j}a_{n,n+t−j}, so that

c_{n+1,k,n+t} = ∑_{j=t+1}^{k−1} b(n, k, t, j)\frac{a_{n+1,n+1+t−j}}{a_{n,n+t−j}} .

We see that b(n, k, t, t + 1) = (n(t − (k − 2))) a_{k,j}a_{n,n−1} < 0, the bracketed term in b(n, k, t, j) increases as j increases, and if c_{n,k,n−1+t} < 0, then ∑_{j=t+1}^{k−1} b(n, k, t, j) < 0 (since the bracketed term in b(n, k, t, j) is less than or equal to the bracketed term in c_{n,k,n−1+t}). Furthermore, from Lemma 9 we know that the sequence \{\frac{a_{n+1,n+1+t−j}}{a_{n,n+t−j}} \} is decreasing as j increases.

Hence the conditions set forth in Lemma 8 are met, and we have c_{n+1,k,n+t} < 0. Since c_{k,k,k−1+t} = 0, we have for all n > k, c_{n,k,n−1+t} < 0.

Case 4: r = n + k − 3.

c_{n,k,r} = ((n − 1)(k − 1) − (k − 1)(n − 1)) a_{n,n−1}a_{k,k−1} = 0.

We have proved that h(n, k, x) has at most one positive zero. Hence we know from Lemma 7 that on the interval .5 < p < 1, P (n, k, p) and P (k, n, p) cannot intersect. From Lemma 10, we know that lim_{p→1} \frac{P′(n, k, p)}{P′(k, n, p)} < 1. Hence, we must have

P (n, k, p) > P (k, n, p) on .5 < p < 1.

3 Counterexamples for two conjectured inequalities

Define Maxpoints(m, n) := (2m − 1)(2n − 1), the maximum number of points possible where the winner is the first player to win m n-point games.

Initial examination of numerical values of P (n, k, p) for a wide range of values of n, k and p suggested that the following conjectured inequalities might be universally true and provable (.5 < p < 1):

Conjecture 1. If Maxpoints(a, b) > Maxpoints(c, d), then P (a, b, p) > P (c, d, p).

Conjecture 2. If ab = cd and min(a, b) > min(c, d), then P (a, b) > P (c, d).

The following computations show that neither of these conjectures is universally true:

Maxpoints(3, 2) = 15 P (3, 2, .6) = .7617 ⋯
Maxpoints(1, 7) = 13 P (7, .6) = .7711 ⋯

\begin{matrix}min (4, 3) = 3 & P (4, 3, .99) = .999999999999999999670 ⋯ \\ min (6, 2) = 2 & P (6, 2, .99) = .999999999999999999676 ⋯ \end{matrix}

4 Remark

The integers a_{k,i}, which play a significant role in this paper, are the same as the integers a_{k+i−1,k−1} in A033820 of the On-line Encyclopedia of Integer Sequences. They appear in quite different contexts in [1, 2].

References

[1] A. Burstein, Enumeration of words with forbidden patterns, Ph. D. Thesis, U. of Pennsylvania, 1998.

[2] I. Gessel, Super ballot numbers, J. Symbolic Computation 14 (1992), 179–194.

2000 Mathematics Subject Classification: 60C05. Keywords: games, inequalities, probability, sets.

(Concerned with sequence \underline{A033820}.) Received July 29 2003; revised version received November 24 2003. Published in Journal of Integer Sequences, December 6 2003. Return to Journal of Integer Sequences home page.