Asymptotics for Lacunary Sums of Binomial Coefficients and a Card Problem with Ranks

Tamás Lengyel Mathematics Department Occidental College 1600 Campus Road Los Angeles, CA 90041 USA

                        lengyel@oxy.edu

Abstract We find asymptotics for lacunary sums of binomial coefficients. As an application we determine the exact and approximate probability that the first card has the uniquely highest rank among the top l cards of a standard card deck.

1 Introduction

In card games, we often pick the first i cards from the top of a standard deck and check the ranks of these cards as they show up. The kings have the highest rank, 13, while the aces have the lowest, 1. What are the chances, p_{i}, that the first card has the uniquely highest rank among these i cards? One expects this number to be slightly less than 1/i for small values of i. We will obtain some asymptotics for this probability in the generalized case in which there are m denominations (of face values 1, 2, …, m) in each of k suits, i.e., m = 13 and k = 4 for the standard deck. We prove

Theorem 1. Let i, k and m be positive integers and p_{i} as defined above. Then

p_{i} ≈ \frac{1}{i} − \frac{1}{2m} (1 − \frac{1}{k}) ,  (1)

for 2 ≤ i ≤ m^{1/4} as m → ∞.

We can rephrase Theorem 1 and obtain Theorem 2 which is of general interest since it concerns the k-sected version of the so-called upper summation [3, p. 174] (sometimes also referred to as the hockey stick pattern, though apparently, there is some confusion regarding this naming convention).

Theorem 2. Let i, k and m be positive integers. We have that

∑_{l=1}^{m} \binom{k(l − 1)}{i − 1} ∼ \binom{km}{i}\frac{1}{k} (1 − \frac{i}{2m} (1 − \frac{1}{k}))  (2)

for 2 ≤ i ≤ m^{1/4} as m → ∞.

Some particular lacunary sums of this type have combinatorial interpretations (cf. Table 1), and they appear in Sloane’s On-Line Encyclopedia of Integer Sequences [5].

k i A-number Comments
2 3 \underline{A002412} hexagonal pyramidal numbers, or greengrocer’s numbers
2 4 \underline{A112742} second derivative of the n-th Chebyshev polynomial

(of the first kind) evaluated at x = 1

3 4 \underline{A116689} partial sums of dodecahedral numbers

Table 1: Lacunary sums of binomial coefficients

We can extend Theorem 2 for other k-sections using simple identities for binomial coefficients.

Theorem 3. Let i, k and m be positive integers and j be an integer so that 0 ≤ j < min{i, k}. We have that

∑_{l=1}^{m} \binom{k(l − 1) + j}{i − 1} ∼ \binom{km + j}{i}\frac{1}{k} (1 − \frac{i}{2(m + \frac{j}{k})} (1 − \frac{1}{k}))  (3)

for 2 ≤ i ≤ m^{1/4} as m → ∞.

The approximation (2) (and subsequently, (3)) can be improved by involving more terms in the last factor as it is indicated immediately after (14) for approximating p_{i}. Note that the sum in (2) has a closed form by standard binomial summation if k = 1, and it corresponds to the upper summation identity. In this case, equality holds in (2) for all positive integers i and m. The same applies to (3).

2 Preliminaries

The simplest version of the card selection problem is proposed in [4, Example 2.3.3] with the standard deck and i = 2: “Two cards are drawn from a poker deck without replacement.

What is the probability that the second is higher in rank than the first?” We use the notation

A_{i} = the rank of first card exceeds that of the other i − 1 cards, so
A_{2} = the rank of first card exceeds that of the second card,
B = the rank of second card exceeds that of the first card,
C = the first and second cards have the same rank.

Clearly, P (A_{2}) = P (B), by symmetry, and P (C) = \frac{3}{51} which yields P (A_{2}) = \frac{24}{51} = \frac{1}{2} − \frac{3}{102} ≈ 0.4706, while the approximation (1) yields p_{2} ≈ \frac{1}{2} − \frac{1}{26} (1 − \frac{1}{4}) ≈ 0.4712.

By using conditional probabilities, we get that in general,

\begin{aligned}p_{i} = P (A_{i}) & = ∑_{l=1}^{m} P (A_{i} | D_{l})P (D_{l}) = ∑_{l=1}^{m} \begin{matrix}( & {k(l−1) \atop i−1} & ) \\ ( & {km−1 \atop i−1} & ) \end{matrix} \frac{k}{km} \\ & = \frac{k}{i} \frac{1}{\binom{km}{i}} ∑_{l=1}^{m} \binom{k(l−1)}{i−1}, \end{aligned}  (4)

with D_{l} being the event that the first card is of face value l = 1, 2, …, m. Clearly, p_{1} = 1 and p_{k(m−1)+1} = 1/\binom{km}{k}, since in the latter case, the first card and the last k − 1 cards in the full deck of km cards are of the highest rank. Easy calculation shows that p_{2} = \frac{k(m−1)}{2(km−1)} but p_{i} looks less and less manageable as i gets large. Also, it is obvious that p_{i} = 1/i for k = 1.

We applied symbolic summation techniques to rewrite (2), (3) and (4) but did not succeed in obtaining useful closed forms. Note, however, that we can derive the generating function of the last sum in (4) in the form of

g(x) = ∑_{i=1}^{k(m−1)+1} p_{i} \frac{i}{k} \binom{km}{i}x^{i} = ∑_{i=1}^{k(m−1)+1} ∑_{l=1}^{m} \binom{k(l − 1)}{i − 1}x^{i}

through the generating function in two variables

\begin{aligned}f(x, y) & = ∑_{i=1}^{k(m−1)+1} ∑_{l=1}^{m} \binom{k(l−1)}{i−1}x^{i}y^{l} = ∑_{l=1}^{m} y^{l} ∑_{i=1}^{k(l−1)+1} \binom{k(l−1)}{i−1}x^{i} \\ & = ∑_{l=1}^{m} y^{l}x(1 + x)^{k(l−1)} = xy^{\frac{1−(y(1+x)^{k})^{m}}{1−y(1+x)^{k}}} . \end{aligned}

In fact, it follows that g(x) = f(x, 1) = x\frac{1−(1+x)^{km}}{1−(1+x)^{k}}. However, this does not seem to help with the asymptotics.

3 Proof of Theorem 1

Clearly, p_{1} = 1, and it is easy to see that p_{i} = \frac{1}{i} − \frac{1}{2m}(1 − \frac{1}{k}) + \frac{(i−1)(k^{2}−6 k+5)}{12 k^{2}m^{2}} + O(\frac{1}{m^{3}} ) for 2 ≤ i ≤ 8 as m → ∞, in agreement with (1).

By standard asymptotical expansion of the binomial coefficients, we have that

\binom{n}{k} = \frac{n^{k}}{k!} (1 − \frac{\binom{k}{2}}{n} + \frac{(3k − 1)\binom{k}{3}}{4n^{2}} + O (\frac{k^{6}}{n^{3}} )) ,  (5)

which is useful when k = O (n^{1/2−ϵ}) with any small positive ϵ. We will use the inequality

\binom{n}{k} ≤ \frac{n^{k}}{k!} ,  (6)

which holds for every k, 0 ≤ k ≤ n, in the second part of the estimation (13). On the other hand,

\begin{aligned}∑_{l=1}^{m}(l − 1)^{i} & = \frac{1}{i+1} ∑_{l=0}^{i} \binom{i+1}{l}B_{l}m^{i+1−l} \\ & = \frac{1}{i+1}m^{i+1} − \frac{1}{2}m^{i} + \frac{i}{12}m^{i−1} + O (i^{2}m^{i−2}) \end{aligned}  (7)

with i = o (m) by using the Bernoulli numbers, B_{l} [3, Section 6.5]; for example, B_{0} = 1, B_{1} = −\frac{1}{2}, B_{2} = \frac{1}{6}, B_{3} = 0, B_{4} = −\frac{1}{30}, B_{5} = 0, and B_{6} = \frac{1}{42}. We note that an alternative approach for approximating sums of powers is outlined in [1] based on an observation of Bernoulli which is related to the Faulhaber polynomials [2]

∑_{l=1}^{m}(l − 1)^{i} = \frac{m_{1}^{i+1}}{i + 1} (1 − \frac{\binom{i+1}{2}}{12m_{1}^{2}} + \frac{7\binom{i+1}{4}}{240m_{1}^{4}} − …) with m_{1} = m − \frac{1}{2}.  (8)

For an application of this technique see [6]. Note that while in the expansion (7) the fourth term vanishes since B_{3} = 0, in the alternative approach the second term vanishes already. This fact might help in getting the asymptotic evaluations below a little faster, although by somewhat more complicated expansions. This approach can be easily tested by some software with symbolic calculation capabilities. We achieved this by using the Mathematica function FullSimplify with the assumption that the exponents in the terms of the form (m − \frac{1}{2})^{i} are positive integers. In fact, to get the approximation (1), we need only

\frac{1}{m^{i}} (1 + \frac{\binom{i}{2}}{km}) (\frac{(m − \frac{1}{2})^{i}}{i} − \frac{\binom{i−1}{2}}{k} \frac{(m − \frac{1}{2})^{i−1}}{i − 1} ) ,

while our main approach requires an extra term from the expansion (7) (cf. (11))

\frac{1}{m^{i}} (1 + \frac{\binom{i}{2}}{km}) (m^{i} (\frac{1}{i} − \frac{1}{2m}) − \frac{\binom{i−1}{2}}{k}m^{i−1} \frac{1}{i − 1})

to obtain (14). In order to determine the next term (15) of the approximation, we need 4 and 6 terms of the expansions (8) and (7), respectively. We note, however, that in both approaches, every other term vanishes after the initial terms.

The good news is that the dominant terms in the sum (4) have large values of l in the binomial coefficients for which we can use the asymptotics given in (5). This fact will make the approximation surprisingly effective even for fairly large values of i.

Let i be any integer between 9 and the sufficiently large m^{1/4}, and a(i) = ⌈\frac{i^{8/3}}{k} ⌉ + 1. This choice guarantees

(\frac{a(i)}{m})^{i} = O ((\frac{1}{km^{1/3}} )^{i}) = O (\frac{1}{m^{3}} ) .  (9)

Note that as m → ∞, formulas (7) and (9) yield the asymptotics

∑_{l=1}^{a(i)−1}(l − 1)^{i−1} = a(i)^{i} (\frac{1}{i} − \frac{1}{2a(i)} + \frac{i − 1}{12a(i)^{2}} + O (\frac{i^{2}}{a(i)^{3}} ))  (10)

and

\begin{aligned}∑_{l=a(i)}^{m}(l − 1)^{i−1} & = ∑_{l=1}^{m}(l − 1)^{i−1} − ∑_{l=1}^{a(i)−1}(l − 1)^{i−1} \\ & = m^{i} (\frac{1}{i} − \frac{1}{2m} + \frac{i−1}{12m^{2}} + O (\frac{i^{2}}{m^{3}} )) + m^{i} (\frac{a(i)}{m})^{i} O (\frac{1}{i}) \\ & = m^{i} (\frac{1}{i} − \frac{1}{2m} + \frac{i−1}{12m^{2}} + O (\frac{i^{2}}{m^{3}} )) + m^{i}O (\frac{1}{im^{3}} ) . \end{aligned}  (11)

The identity (5) implies that

\begin{aligned}\binom{km}{i} & = \frac{(km)^{i}}{i!} (1 − \frac{\binom{i}{2}}{km} + \frac{(3i−1)\binom{i}{3}}{4(km)^{2}} + O (\frac{i^{6}}{(km)^{3}} )), \\ \frac{1}{\binom{km}{i}} & = \frac{i!}{(km)^{i}} (1 + \frac{\binom{i}{2}}{km} + \frac{(3i−2)\binom{i+1}{3}}{4(km)^{2}} + O (\frac{i^{6}}{(km)^{3}} )). \end{aligned}  (12)

According to (4), (5), (6), (9), (10) and (12), and with A = \frac{k}{i} \frac{1}{\binom{km}{i}}, we get that

\begin{aligned}p_{i} & = A ∑_{l=1}^{m} \binom{k(l−1)}{i−1} \\ & = A (∑_{l=a(i)}^{m} \binom{k(l−1)}{i−1} + \frac{k^{i−1}}{i!} O(a(i)^{i})) \\ & = \frac{k}{i} \frac{i!}{(km)^{i}} (1 + \frac{\binom{i}{2}}{km} + \frac{(3i−2)\binom{i+1}{3}}{4(km)^{2}} + O (\frac{i^{6}}{(km)^{3}} )) \\ & × ∑_{l=a(i)}^{m} \frac{k^{i−1}(l−1)^{i−1}}{(i−1)!} (1 − \frac{\binom{i−1}{2}}{k(l−1)} + \frac{(3i−4)\binom{i−1}{3}}{4(k(l−1))^{2}} + O (\frac{i^{6}}{(l−1)^{3}} ) ) + O (\frac{1}{im^{3}} ) , \end{aligned}  (13)

for a(i) ≤ l implies that i ≤ (k(l − 1))^{3/8}, and thus, we can use (5) in the last part of (13). Now by (11), we derive that

p_{i} = \frac{k}{i} \frac{i!}{(km)^{i}} (1 + \frac{\binom{i}{2}}{km} + \frac{(3i−2)\binom{i+1}{3}}{4(km)^{2}} + O (\frac{i^{6}}{(km)^{3}} ))\frac{k^{i−1}}{(i−1)!}

×( (\frac{1}{i}m^{i} − \frac{1}{2}m^{i−1} + \frac{i−1}{12}m^{i−2}) − \frac{\binom{i−1}{2}}{k} (\frac{1}{i−1}m^{i−1} − \frac{1}{2}m^{i−2} + \frac{i−2}{12}m^{i−3})

+\frac{(3i−4)\binom{i−1}{3}}{4k^{2}} (\frac{1}{i−2}m^{i−2} − \frac{1}{2}m^{i−3} + \frac{i−3}{12}m^{i−4}) ) + O (\frac{i^{5}}{m^{3}} ) + O (\frac{1}{im^{3}} )

which can be rewritten as

\begin{matrix}(1 + \frac{\binom{i}{2}}{km} + \frac{(3i−2)\binom{i+1}{3}}{4(km)^{2}})( (\frac{1}{i} − \frac{1}{2m} + \frac{i−1}{12m^{2}} ) − \frac{\binom{i−1}{2}}{k} (\frac{1}{(i−1)m} − \frac{1}{2m^{2}} ) \\ +\frac{(3i−4)\binom{i−1}{3}}{4k^{2}} (\frac{1}{(i−2)m^{2}} − \frac{1}{2m^{3}} ) ) + O (\frac{i^{5}}{m^{3}} ) \\ = \frac{1}{i} − \frac{1}{2m} (1 − \frac{1}{k}) + O (\frac{i}{m^{2}} ) . \end{matrix}  (14)

The error term in (14) can be further determined to yield

\frac{(i − 1) (k^{2} − 6 k + 5)}{12 k^{2}m^{2}} + O(\frac{1}{m^{3}} )  (15)

as m → ∞ and i is kept fixed. With more involved calculations we find that the next error term is \frac{(i−1) (k−1)(3(k−3) i−4 k+8)}{24 k^{3}m^{3}} + O(\frac{1}{m^{4}} ) which explains why the previous approximation becomes even better if k = 3 and m is sufficiently large. Note that if k = 1 then the second term of (1) and the above mentioned two terms vanish as one might expect since p_{i} = 1/i in this case.

Numerical calculation and plotting p_{i} against i confirms that the approximation (1) is valid for a much larger set of values i. (Of course, this observation is of no surprise as in the above proof we dealt with the bounds on i quite generously. We extend the range of values of i in the next section.) For example, in the case of the standard deck, we get that p_{i} ≈ \frac{1}{i} − 0.029, in agreement with the fact that second term in (1) does not depend on i, and it seems to be a fairly precise over-estimation for any 2 ≤ i ≤ 22. In general, however, numerical experimentation also suggests that the approximation (1) needs correcting terms when i grows.

4 Extending the range

The proof presented in the previous section can be improved to work for a larger set of values of i; thus, we can extend the validity of Theorems 1-3. In fact, let i be any integer between 9/(1 − ϵ) and the sufficiently large m^{1/3}, and a(i) = ⌈\frac{i^{2+ϵ}}{k} ⌉ + 1 with any small positive ϵ. We note that a(i) ≤ l implies that i ≤ (k(l − 1))^{\frac{1}{2+ϵ}}; thus, we can use the approximation (5) for binomial coefficients. We also need 9/(1 − ϵ) ≤ k to guarantee (9). After streamlining the steps outlined in (10)-(14), we obtain a complete proof. First, we observe that

\begin{aligned}\binom{km}{i} & = \frac{(km)^{i}}{i!} (1 − \frac{\binom{i}{2}}{km} + O (\frac{i^{4}}{(km)^{2}} )), \\ \frac{1}{\binom{km}{i}} & = \frac{i!}{(km)^{i}} (1 + \frac{\binom{i}{2}}{km} + O (\frac{i^{4}}{m^{2}} )). \end{aligned}

It follows that

p_{i} = A ∑_{l=1}^{m} \binom{k(l−1)}{i−1}

= A (∑_{l=a(i)}^{m} \binom{k(l−1)}{i−1} + \frac{k^{i−1}}{i!} O(a(i)^{i}))

= \frac{k}{i} \frac{i!}{(km)^{i}} (1 + \frac{\binom{i}{2}}{km} + O (\frac{i^{4}}{m^{2}} ))

× ∑_{l=a(i)}^{m} \frac{k^{i−1}(l−1)^{i−1}}{(i−1)!} (1 − \frac{\binom{i−1}{2}}{k(l−1)} + O (\frac{i^{4}}{(l−1)^{2}} ) ) + O (\frac{1}{im^{3}} ) ,

therefore,

p_{i} = \frac{k}{i} \frac{i!}{(km)^{i}} (1 + \frac{\binom{i}{2}}{km} + O (\frac{i^{4}}{m^{2}} ))\frac{k^{i−1}}{(i−1)!}

×( (\frac{1}{i}m^{i} − \frac{1}{2}m^{i−1} + \frac{i−1}{12}m^{i−2}) − \frac{\binom{i−1}{2}}{k} (\frac{1}{i−1}m^{i−1} − \frac{1}{2}m^{i−2})

+O(i^{4}) \frac{1}{i−2}m^{i−2}) + O (\frac{i^{5}}{m^{3}} ) + O (\frac{1}{im^{3}} ) .

This can be rewritten as

\begin{matrix}(1 + \frac{\binom{i}{2}}{km})( (\frac{1}{i} − \frac{1}{2m}) − \frac{\binom{i−1}{2}}{k} \frac{1}{(i−1)m}) + O (\frac{i^{3}}{m^{2}} ) \\ = \frac{1}{i} − \frac{1}{2m} (1 − \frac{1}{k}) + O (\frac{i^{3}}{m^{2}} ) . \end{matrix}

By including more correcting terms, one might be able to extend the range for i to m^{1/2−ϵ} with any positive ϵ.

Acknowledgments

The author wishes to thank the referee and Gregory Tollisen for making helpful suggestions and comments that improved the presentation of this paper.

References

[1] B. L. Burrows and R. F. Talbot, Sums of powers of integers, Amer. Math. Monthly 91 (1984), 394–403.

[2] A. W. F. Edwards, A quick route to sums of powers, Amer. Math. Monthly 93 (1986), 451–455.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, A foundation for computer science, Addison-Wesley, Reading, MA, 1994, 2nd edition.

[4] M. Larsen and M. Marx, An Introduction to Mathematical Statistics and Its Applications, Prentice Hall, Upper Saddle River, NJ, 2006, 4th edition.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

   at http://www.research.att.com/∼njas/sequences.

[6] B. Tsaban, Bernoulli numbers and the probability of a birthday surprise, Discrete Appl. Math. 127 (2003), 657–663.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 05A16, 11B68. Keywords: lacunary sum, asymptotic enumeration, Bernoulli numbers.

(Concerned with sequences \underline{A002412}, \underline{A112742}, and \underline{A116689}.)

Received April 14 2007; revised version received July 2 2007. Published in Journal of Integer Sequences, July 4 2007.

Return to Journal of Integer Sequences home page.