Séminaire Lotharingien de Combinatoire 50 (2004), Article B50h

Irreducible compositions

and the first return to the origin of a random walk

Edward A. Bender ^{1} Gregory F. Lawler ^{2}^{,}^{3} Robin Pemantle ^{4}^{,}^{5} Herbert S. Wilf ^{6}

Abstract. Let n = b_{1} + ⋯ + b_{k} = b′_{1} + ⋯ + b′_{k} be a pair of compositions of n into k positive parts. We say this pair is irreducible if there is no positive j < k for which b_{1} + ⋯ + b_{j} = b′_{1} + ⋯ + b′_{j}. The probability that a random pair of compositions of n is irreducible is shown to be asymptotic to 8/n. This problem leads to a problem in probability theory. Two players move along a game board by rolling a die, and we ask when the two players will first coincide. A natural extension is to show that the probability of a first return to the origin at time n for any mean-zero variance V random walk is asymptotic to \sqrt{V/(2π)}n^{−3/2}. We prove this via two methods, one analytic and one probabilistic.

1University of California at San Diego, La Jolla, CA 92093-0112, <ebender@ucsd.edu>. 2Research supported in part by National Science Foundation grant # DMS 9971220 3Cornell University, Ithaca, NY 14853-4201, <lawler@math.cornell.edu>. 4Research supported in part by National Science Foundation grant # DMS 0103635 5University of Pennsylvania, Philadelphia, PA 19104-6395, <pemantle@math.upenn.edu>. 6University of Pennsylvania, Philadelphia, PA 19104-6395, <wilf@math.upenn.edu>. 2000 Mathematics Subject Classification. Primary: 60C05, 05A16; secondary: 05A15, 05A17,

60G50.

Key words and phrases. generating function, central limit, compositions, renewal, Cauchy integral, diagonal, camembert, dice game.

1. Introduction

Consider a two-person game played on the nonnegative integers, as follows. A probability distribution {p_{i}}_{1}^{∞} is given. Initially both players’ tokens are at the origin. During play, p_{i} will be the probability that the player moves his token i units to the right of its present position. Player 1 then moves to i with probability p_{i}, and player 2 then takes a turn, landing on j with probability p_{j}. Moves continue to alternate until for the first time the two tokens land on the same integer. We are interested in the distribution of n, the number of (pairs of) moves that have been made at that moment of first coincidence.

Our first result concerns a model of a similar situation in which the first coincidence occurs at time n, and all compositions of n are equally probable. By a composition of n into k parts we mean an ordered representation of n as a sum of k positive integers. Let C and C′ denote respectively the compositions n = b_{1} + ⋯ + b_{k} and n = b′_{1} + ⋯ + b′_{k} of n into k parts. We’ll say that C, C′ are an irreducible pair if for every j = 1, 2, …, k − 1 we have b_{1} + ⋯ + b_{j} ≠ b′_{1} + ⋯ + b′_{j}, while, of course, equality holds at j = k. Note that we allow b_{1} + … + b_{i} = b′_{1} + ⋯ + b′_{j} for i ≠ j.

Let f(n) denote the number of irreducible ordered pairs of compositions of n into the same number of parts.

Theorem 1.1. We have

∑_{n≥1} f(n)z^{n} = \frac{z}{\sqrt{1 − 4z} + z} .  (1.1)

(This gives a combinatorial interpretation to sequence A081696 of Sloane’s database.) Furthermore, if we let p_{n} denote the probability that a pair of compositions is irreducible when chosen uniformly at random from among all pairs of n compositions into an equal number of parts, then

f(n) ∼ \frac{2}{\sqrt{π}} n^{−3/2}4^{n};  (1.2)

p_{n} ∼ \frac{8}{n} .  (1.3)

Remark: A somewhat similar problem about integer partitions was studied by Erdős et al [ENS92].

The asymptotics in (1.2) and (1.3) are derived from the exact computation (1.1). We compare this to another well known paradigm for analyzing compositions, namely poissonization. It is well known that a uniform random composition of n may be generated by letting {Y_{j} : j ≥ 1} be independent random variables whose distribution is geometric with mean 2, that is, ℙ(Y_{j} = i) = 2^{−i}. Let W_{k} := ∑_{j=1}^{k} Y_{j} denote the partial sums. If T := min{k : W_{k} ≥ n} is the first time the partial sums exceed n, then Y_{1} + ⋯ + Y_{T −1} + (n − Y_{T −1}) is uniformly distributed over compositions of n. The number of parts of the composition is T, which is asymptotically normal with mean n/2 and standard deviation Θ(\sqrt{n}). Conditioning on T = k gives the uniform distribution on compositions of n into k parts.

From this viewpoint, a pair of compositions with the same number of parts is just a pair of independent random walk sequences {Y_{j}} and {Y′_{j}}, conditioned to have the same stopping time T = T′. Irreducibility of the pair corresponds to W_{j} ≠ W′_{j} for all 1 ≤ j ≤ T − 1. Let S_{k} := W_{k} − W′_{k} = ∑_{j=1}^{k}(Y_{j} − Y′_{j}) := ∑_{j=1}^{k} X_{j} be the partial sums of the difference sequence {X_{j}}. Then irreducibility corresponds to τ = n, where τ is the first return time, that is, τ = min{k ≥ 1 : S_{k} = 0}.

A rigorous proof of (1.3) via analysis of the return time of {S_{n}} to the origin would require, among other things, showing that conditioning on T = T′ does not significantly affect the distribution of the return time. This would be far messier than the compact proof of Theorem 1.1 below. Nevertheless, the poissonization paradigm raises the question of the distribution of the return time of {S_{n}} to the origin. The same question arises in a game (similar to some traditional board games with one token per player in which moves are determined by where a spinner comes to rest) in which two players each roll a die and (simultaneously) advance their tokens the number of positions shown on the die. When the tokens collide, they must both go back to start. The chance of the first collision occurring at time n is just a_{n} := ℙ(τ = n). Our main result is the following asymptotic for a_{n}:

Theorem 1.2. Let {X_{j} : j ≥ 1} be independent with mean zero, finite variance, V, and no periodicity (that is, the GCD of times n at which it is possible to have S_{n} = 1 is 1). Let {S_{n}}, τ and a_{n} be as above. Then the probability a_{n} of the first return to 0 occurring at time n is asymptotically given by

a_{n} ∼ \sqrt{\frac{V}{2π}} n^{−3/2} .

Surprisingly, given the wealth of knowledge about random walks, we were unable to find this theorem in the literature. The formula is not surprising, and is what one obtains in a thumbnail calculation by “differentiating” with respect to n estimates such as (3.9) below, which is an estimate for Q_{n} := ℙ(S_{j} ≠ 0, ∀1 ≤ j ≤ n). There are special cases, such as the simple random walk where S_{n} = ±1 according to a fair coin-flip, in which a_{n} is easy to compute exactly. Asymptotics in the general case are well known for many quantities such as Q_{n} and a′_{n} := ℙ(S_{n} = 0), but we could find no text that included asymptotics for a_{n} and indeed these seem tricky to obtain by probabilistic methods; a probabilistic proof of Theorem 1.2 is the subject of the last section of this note.

In the remainder of this section, we prove Theorem 1.1. In the subsequent section we prove Theorem 1.2 by analytic means. In the final section, we give a probabilistic proof of Theorem 1.2.

Proof of Theorem 1.1: Let f(n, k) be the number of irreducible ordered pairs of compositions of n into k parts. We will show that

∑_{n,k≥1} f(n, k)x^{n}y^{k} = \frac{xy (\sqrt{1 + x^{2}(1 − y)^{2} − 2x(1 + y)} − xy)}{1 − 2x(1 + y) + x^{2}(1 − 2y)} ,  (1.4)

from which (1.1) follows by setting y = 1.

To show (1.4), by considering the number of ordered pairs of compositions of n into k parts such that the partial sums of the parts agree with each other at indices k_{1}, k_{1} + k_{2}, …, k_{1} + ⋯ + k_{r}, we see that

∑_{r≥1}_{∑_{m_{1}+···+m_{r}=n} ; k_{1}+···+k_{r}=k}f(m_{1}, k_{1})f(m_{2}, k_{2}) … f(m_{r}, k_{r}) = \binom{n − 1}{k − 1}^{2} ,

the right side being the total number of pairs of compositions of n into k parts. Hence if F (x, y) = ∑_{n,k≥1} f(n, k)x^{n}y^{k}, we have

\frac{F}{1 − F} = F + F^{2} + F^{3} + … = ∑_{n,k≥1} \binom{n − 1}{k − 1}^{2}x^{n}y^{k}

= xy ∑_{n,k≥0} \binom{n}{k}^{2}x^{n}y^{k}

= xy ∑_{n≥0} x^{n}(1 − y)^{n}P_{n} (\frac{1 + y}{1 − y} )
= \frac{xy}{\sqrt{1 − 2x(1 + y) + x^{2}(1 − y)^{2}}} ,

in which the P_{n}’s are the Legendre polynomials. The claimed result (1.4) now follows by solving for F.

The estimate (1.2) follows from (1.1) via standard Tauberian theorems. The result of Flajolet and Odlyzko, for instance (Theorem 2.1 quoted below) suffices, although (1.2) may also be obtained by the method of Darboux which requires a smaller region of analyticity. Since there are

∑_{k} \binom{n − 1}{k − 1}^{2} = \binom{2n − 2}{n − 1} ∼ \frac{4^{n−1}}{\sqrt{nπ}}

ordered pairs of compositions of n with the same number of parts, it follows that the probability that a random pair of compositions of n with the same number of parts is irreducible is ∼ 8/n. □

2. Analytic proof

Let H(z) := ∑_{n≥1} a_{n}z^{n} be the generating function for the probabilities a_{n} of first return at time n. Let G(z) := ∑_{n≥0} a′_{n}z^{n}, where a′_{n} = ℙ(S_{n} = 0) is the probability of a return to the origin at time n but not necessarily the first return (set a′_{0} = 1 and a_{0} = 0). Then G and H are analytic on the open unit disk and G = 1/(1 − H). We will use this to obtain H from G, while G in turn is obtained from the two-variable generating function

F (z, w) := ∑_{n≥0} ∑_{j∈ℤ}ℙ(S_{n} = j)z^{n}w^{j} .

Finally, we may write F = 1/(1 − zg(w)) where

g(w) := ∑_{n∈ℤ}b_{n}w^{n}

is the generating function for X_{1}.

The following estimates are elementary. From the local central limit theorem [Dur04, Theorem (II.5.2)], as n → ∞,

a′_{n} ∼ \frac{1}{\sqrt{2πV}} n^{−1/2} .  (2.5)

Consequently,

G(z) ∼ \frac{1}{\sqrt{2V}} (1 − z)^{−1/2}  (2.6)

as z ↑ 1. To see this, let ϵ denote 1 − z and compute

G(z) = ∑_{n≥0} \frac{1}{\sqrt{2πV}} n^{−1/2}e^{−nϵ(1+o(1))}
= \frac{1}{\sqrt{2πV}} ϵ^{1/2} ∑_{n≥0}(nϵ)^{−1/2}e^{−nϵ(1+o(1))}
∼ \frac{1}{\sqrt{2πV}} ϵ^{−1/2} ∫_{0}^{∞} x^{−1/2}e^{−x} = \frac{1}{\sqrt{2V}} (1 − z)^{−1/2}

using dominated convergence at the first approximation.

Finally, for H = 1 − 1/G, we have the estimate

1 − H(z) ∼ \sqrt{2V} (1 − z)^{1/2}  (2.7)

as z ↑ 1. The proof of Theorem 1.2 rests on these estimates and on the following Tauberian theorem of [FO90]:

Theorem 2.1 (Flajolet–Odlyzko (1990)). Say that a region R is a Camembert region^{1} if it is of the form R_{ϵ} := {|z| < 1 + ϵ and | arg(z − 1)| > π/2 − ϵ}. If a function H is analytic in a Camembert region and H(z) ∼ C(1 − z)^{−α} near z = 1, then its coefficients a_{n} satisfy

1Named, by French mathematicians, for its shape.

a_{n} ∼ \frac{C}{γ(α)}n^{α−1} .

□

Proof of Theorem 1.2: Let C denote the unit circle. For fixed w ∈ C, the function F (z, w) is analytic as z varies over the open unit disk; this follows from absolute convergence of the power series. It also follows that F (z, w) is continuous in (z, w) on the product Ω := D × C of the open unit disk with the unit circle. For fixed w ∈ C, the Cauchy integral formula gives

z^{n}ℙ(S_{n} = 0) = z_{n} ∫ ∑_{j} ℙ(S_{n} = j)w^{n} \frac{dw}{w} .

We may sum this over n and exchange the sum and integral as long as |z| < 1, leading to

G(z) = \frac{1}{2πi} ∫_{γ} \frac{F (z, w)}{w} dw  (2.8)

where γ goes around the unit circle, counterclockwise^{2}.

Suppose we can show G to be analytic in a Camembert region. It follows that H = 1 − 1/G is meromorphic in a Camembert region, and since a function whose coefficients go to zero may have no poles in the closed unit disk, it follows that H is analytic in a Camembert region. The conclusion of the theorem will then follow from (2.7) and Flajolet–Odlyzko.

Claim: There is a Camembert region R such that z ≠ 1/g(w) for any z ∈ R and w on the unit circle, C. Consequently, F (z, w) has an extension to R × C that is analytic in z and continuous in (z, w). Proof: The facts that X_{1} is a probability distribution, has mean zero, and has variance V translate into three facts about g, namely, g(1) = 1, g′(1) = 0, g′′(1) = V. Immediately, we then have

2This integral formula is used in [HK71] to derive a result (attributed to [Fur67] by [Sta99])

implying in this case that G is algebraic whenever g is rational. In fact, in the case where X_{1} has finite support, one may use this implication at the next step to avoid having to examine the power series expansion of g.

\frac{1}{g(e^{iθ})} = 1 + \frac{V}{2} θ^{2} + o(θ^{2}) .

Hence arg(1/g(w)) → 0 as w → 1 in C and there is an δ > 0 such that for arg(z − 1) > δ and |θ| < δ, z ≠ 1/g(e^{iθ}). For 1 ≠ w ∈ C, aperiodicity of X_{1} implies |g(w)| < 1. Let ϵ be the minimum of δ and the values |g(e^{iθ})|^{−1} − 1 on |θ| ∈ [−π, π] \ (−δ, δ). Then z ≠ 1/g(w) on the Camembert region R(ϵ). □

Finishing the proof of Theorem 1.2, we let R be as in the conclusion of the lemma and observe that for any closed loop β in R, we may exchange the order of integration in the representation of G in (2.8) to get

∫_{β} G(z) dz = ∫_{β} ∫_{γ} \frac{1}{2πi} \frac{F (z, w)}{w} dw dz
= \frac{1}{2πi} ∫_{γ} \frac{dw}{w} ∫_{β} F (z, w) dz
= 0 .

By Morera’s theorem, G is analytic in R, completing the proof of Theorem 1.2. □

3. Probabilistic proof

Let p_{n}(x, y) := ℙ_{x}(S_{n} = y) and q_{n}(x, y) := ℙ_{x}(S_{n} = y, S_{j} ≠ 0 ∀1 ≤ j ≤ n − 1) denote probabilities for {S_{n} = y} respectively with or without killing at the origin. These quantities are symmetric in the two arguments. Previously defined quantities are related to these by a′_{n} = p_{n}(0, 0) and a_{n} = q_{n}(0, 0). We let Q_{n} := ℙ_{0}(S_{j} ≠ 0, ∀1 ≤ j ≤ n) = ∑_{k=n+1}^{∞} a_{k} be the tail sums of {a_{n}}.

The derivations of (2.5), (2.6) and (2.7) in the probability literature are via the generating function analysis in the previous section. At this point, the methods part ways. The probabilistic analysis derives a_{n} from its tail sums, Q_{n}. The reasonably well known estimate on Q_{n} is

Q_{n} ∼ \sqrt{\frac{2V}{π}} n^{−1/2} .  (3.9)

This is proved analytically, not via extending a two-variable generating function to a Camembert region, but just from (2.7). The key here is that the sequence {Q_{n}} is monotone. According to a Tauberian theorem which may be found in [Fel71, Theorem XIII.5], the extra regularity, together with the behavior of its generating function H/(1 − z) for real z ↑ 1, implies (3.9).

Since a_{n+1} = Q_{n} − Q_{n+1}, the conclusion of the theorem now follows if we can establish regularity of a_{n} to the degree that

a_{n+1} − a_{n} = O(n^{−5/2}) .  (3.10)

Note that we have now converted the task from one of finding the correct leading term into one of finding an upper bound to within a constant factor, which is a problem well suited to probabilistic analysis. To complete the regularity argument we need a couple of estimates on how rapidly p_{n}(0, x) := ℙ_{0}(S_{n} = x) can change with n. We will prove these at the end.

Lemma 3.1. Under the assumptions of aperiodicity, zero mean and finite variance, there is a constant C such that

|p_{n}(0, x) − p_{n+1}(0, x)| ≤ \frac{C}{n^{3/2}}  (3.11)
|p_{n}(0, x) − p_{n+1}(0, x)| ≤ \frac{C}{(1 + x^{2})n^{1/2}} .  (3.12)

Upper bounds for q_{n}(0, x) are given by

q_{n}(0, x) ≤ \frac{C(|x| + 1)^{1/2}}{n^{3/2}}  (3.13)
q_{n}(0, x) ≤ \frac{C}{n} .  (3.14)

We now prove (3.10) for n = 3m, the cases of 3m + 1 and 3m + 2 being identical. Breaking down according to location at times m and 2m we get

a_{n} = q_{3m}(0, 0) = ∑_{x≠0} ∑_{y≠0} q_{m}(0, x)q_{m}(x, y)q_{m}(y, 0) .

Write q_{m}(x, y) = p_{m}(x, y) − ℙ_{x}(S_{m} = y, ∃j ∈ [1, m − 1] : S_{j} = 0). Substituting this in the above equation gives

a_{n} = ∑_{x≠0} ∑_{y≠0} q_{m}(0, x)p_{m}(x, y)q_{m}(y, 0) − ∑_{k=1}^{m−1} ∑_{y≠0} a_{m+k}p_{m−k}(0, y)q_{m}(y, 0)

a_{n+1} = ∑_{x≠0} ∑_{y≠0} q_{m}(0, x)p_{m+1}(x, y)q_{m}(y, 0) − ∑_{k=1}^{m} ∑_{y≠0} a_{m+k}p_{m+1−k}(0, y)q_{m}(y, 0)

and hence

|a_{n} − a_{n+1}| ≤ ∑_{x≠0} ∑_{y≠0} q_{m}(0, x)|p_{m}(x, y) − p_{m+1}(x, y)|q_{m}(y, 0)

+ ∑_{y≠0} a_{2m}p_{1}(0, y)q_{m}(0, y)

+ ∑_{k=1}^{m−1} ∑_{y≠0} a_{m+k}|p_{m+1−k}(0, y) − p_{m−k}(0, y)|q_{m}(y, 0) .

We must bound each of the three terms by O(m^{−5/2}). The second term is a_{2m}a_{m} = O(m^{−3}) by (3.13). Using (3.11) we see that the first term is

O(m^{−3/2}) ∑_{x≠0} q_{m}(0, x) ∑_{y≠0} q_{m}(y, 0) = O(m^{−3/2})Q_{m}^{2} = O(m^{−5/2}) .

The third term requires a little more care. We will show that

∑_{y≠0} |p_{k+1}(0, y) − p_{k}(0, y)|q_{m}(0, y) ≤ ck^{−1/2} [1 + log (\frac{m}{k})] m^{−3/2} .  (3.15)

To show this, split into three ranges of values for y, namely |y| ≤ \sqrt{k}, \sqrt{k} < |y| < \sqrt{m} and |y| ≥ \sqrt{m}. In the first range we use (3.11) and (3.13) with |y| bounded above by k^{1/2} to see that the summand is O(k^{−3/2})O(k^{1/2}m^{−3/2}). There are k^{1/2} summands, so the total sum is O(k^{−1/2}m^{−3/2}).

In the middle range, we use (3.12) and (3.13) to see that the summand is bounded by a constant multiple of k^{−1/2}|y|^{−2}|y|m^{−3/2}. Summing over y introduces the factor of (1/2) log(m/k). For the third sum, use (3.12) and (3.14) to see that the summand is O(k^{−1/2}|y|^{−2}m^{−1}), so that summing over y ≥ \sqrt{m} gives O(k^{−1/2}m^{−3/2}). This proves (3.15).

Finally, summing (3.15) over k < m gives O(m^{−5/2}) which establishes (3.10), finishing the proof of Theorem 1.2. □

Proof of Lemma 3.1: The simplest of the inequalities is (3.14), so we handle it first. Let n = 3m. The bound (3.14) follows immediately from

q_{n}(0, x) ≤ ∑_{y} q_{m}(0, y)p_{2m}(y, x) ≤ a_{m} sup_{y,x} p_{2m}(y, x) = O(m^{−1}) .

To prove (3.13), we decompose according to the position at time m and at time 2m, so that

q_{n}(0, x) = ∑_{y,z≠0} q_{m}(0, y)q_{m}(y, z)q_{m}(z, x)
≤ (Q_{m} sup_{y,z} q_{m}(y, z)) ∑_{z≠0} q_{m}(z, x)
= O(m^{−1})Q_{m}(x) ,

where Q_{m}(x) := ℙ_{x}(S_{j} ≠ 0 ∀1 ≤ j ≤ m and we have used q_{m}(z, x) = q_{m}(x, z) to infer ∑_{z} q_{m}(z, x) = Q_{m}(x). Thus it suffices to show that

Q_{m}(x) = O((1 + |x|)m^{−1/2}) .  (3.16)

Observe that there is a constant c depending on the distribution of X_{1} but not on y such that the probability, call it ρ(y), of hitting y in at most y^{2} steps starting from the origin is at least c (use the local central limit theorem to bound the expected number of visits to y within the first t^{2} steps by from below by c_{1}(1 + |y|) and use the Green’s function to bound the expected number of visits to y given at least one visit from above by c_{2}(1 + |y|)). By a last exit decomposition, we then have

c ≤ ρ(y) ≤ ∑_{j≤y^{2}} p_{j}(0, 0)τ(y)

where τ(y) is the probability starting at the origin of hitting y before returning to the origin. Using p_{j}(0, 0) = Θ(j^{−1/2}) and solving for τ(y) gives

τ(y) = Ω (\frac{1}{1 + |y|}) .

But by (3.9), decomposing according to the time y is first hit,

\sqrt{\frac{2V}{π}} n^{−1/2} ∼ Q_{n} ≥ τ(y)Q_{n}(y)

and solving for Q_{n}(y) proves (3.16).

The bounds on δ_{n}(x) := |p_{n}(0, x) − p_{n+1}(0, x)| are classical (though not all that well known) and are obtained by the same means as the local central limit theorem. Let

ϕ(θ) = g(iθ) = 𝔼e^{iθX_{1}}

be the characteristic function of X_{1}, so that as we have seen, mean zero, finite variance and aperiodicity imply that

ϕ(θ) = 1 − \frac{V θ^{2}}{2} + o(θ^{2})  (3.17)

near 1, while

1 − ϕ(θ) ≤ cθ^{2}  (3.18)

for all |θ| ≤ π. The inversion formula gives

p_{n}(0, x) = \frac{1}{2π} ∫_{−π}^{π} ϕ(θ)^{n}e^{−iθx} dθ .  (3.19)

We obtain from (3.19)

δ_{n}(x) ≤ ∫_{−π}^{π} |ϕ(θ)|^{n}|ϕ(θ) − 1|dθ .

Given (3.17) and (3.18), we see this is a saddle point integral with main contribution near θ = 0. In particular, since ϕ(θ) ≤ 1 − cθ^{2}, we know that |ϕ(θ)|^{n} ≤ c exp(bn^{3/4}) for n^{−1/8} ≤ |θ| ≤ π and we may restrict the integrals to a suitable range such as |θ| < n^{−1/8}. Let y = θ\sqrt{n}. From (3.17),

|ϕ (\frac{y}{\sqrt{n}})|^{n} ≤ ce^{−ay^{2}} ,
|ϕ (\frac{y}{\sqrt{n}}) − 1| ≤ c\frac{y^{2}}{n} ,

whence δ_{n}(x) = O(n^{−3/2}).

For (3.12) we integrate (3.19) twice by parts to get

p_{n}(0, x) = −\frac{x^{2}}{2π} ∫_{−π}^{π} [n(n − 1)ϕ′(θ)^{2} + nϕ′′(θ)] ϕ(θ)^{n−2}e^{−ixθ} dθ .  (3.20)

The same truncation and change of variables, together with the estimate

|ϕ′ (\frac{y}{\sqrt{n}})| ≤ c\frac{1 + |y|}{\sqrt{n}}

give δ_{n}(x) = O((1 + x^{2})n^{−1/2}) and completes the proof of the lemma. □

Acknowledgement: The problems we address were suggested by a question posed by Dr. Amy Myers.

References

[Dur04] Durrett, R. (2004). Probability: theory and examples. Thompson Brooks-Cole: Belmont, CA.

[ENS92] Erdős, P., Nicolas, J.-L., and Sárközy, A. (1992). On the number of pairs of partitions of n without common subsums. Colloq. Math. 63, 61–83.

[Fel71] Feller, W. (1971). An introduction to probability theory and its applications, vol. 2, 2^{nd} edition. John Wiley and Sons: New York.

[FO90] Flajolet, P. and Odlyzko, A. (1990). Singularity analysis of generating functions. SIAM J. Disc. Math. 3, 216–240.

[Fur67] Furstenburg, H. (1967). Algebraic functions over finite fields. J. Algebra 7, 271–277.

[HK71] Hautus, M. and Klarner, D. (1971). The diagonal of a double power series. Duke Math. J. 38, 229–235.

[Sta99] Stanley, R. (1999). Enumerative combinatorics, vol. 2. Cambridge Studies in Advanced Mathematics no. 62. Cambridge University Press: Cambridge.