Analysis of the gift exchange problem

Moa Apagodu Virginia Commonwealth University Richmond, VA 23284, U.S.A.

                                 mapagodu@vcu.edu

David Applegate Google, Inc. 76 Ninth Ave., New York, NY 10011, U.S.A.

                                   david@bcda.us

N. J. A. Sloane^{1} The OEIS Foundation Inc. 11 So. Adelaide Ave., Highland Park, NJ 08904, U.S.A.

                                njasloane@gmail.com

Doron Zeilberger Rutgers University (New Brunswick) Piscataway, NJ 08854, U.S.A.

                             zeilberg@math.rutgers.edu

January 26, 2017

Abstract

In the gift exchange game there are n players and n wrapped gifts. When a player’s number is called, that person can either choose one of the remaining wrapped gifts, or can “steal” a gift from someone who has already unwrapped it, subject to the restriction that no gift can be stolen more than a total of σ times. The problem is to determine the number of ways that the game can be played out, for given values of σ and n. Formulas and asymptotic expansions are given for these numbers. This work was inspired in part by a 2005 remark by Robert A. Proctor in the On-Line Encyclopedia of Integer Sequences.

Keywords: gift swapping, set partitions, restricted Stirling numbers, Bessel polynomials, hypergeometric functions, Almkvist-Zeilberger algorithm, Wilf-Zeilberger summation

This is a sequel to the earlier (electronically published) article [5], differing from it in that there are two additional authors and several new theorems, including the resolution of most of the conjectures, and the extensive tables have been omitted.

Mathematics Subject Classifications: 05A, 11B37, 33F10

1 The problem

The following game is sometimes played at parties. A number σ (typically 1 or 2) is fixed in advance. Each of the n guests brings a wrapped gift, the gifts are placed on a table (this is the “pool” of gifts), and slips of paper containing the numbers 1 to n are distributed randomly among the guests. The host calls out the numbers 1 through n in order.

1Corresponding author

When the number you have been given is called, you can either choose one of the wrapped (and so unknown) gifts remaining in the pool, or you can take (or “steal”) a gift that some earlier person has unwrapped, subject to the restriction that no gift can be “stolen” more than a total of σ times.

If you choose a gift from the pool, you unwrap it and show it to everyone. If a person’s gift is stolen from them, they immediately get another turn, and can either take a gift from the pool, or can steal someone else’s gift, subject always to the limit of σ thefts per gift. The game ends when someone takes the last (nth) gift.

The problem is to determine the number of possible ways the game can be played out, for given values of σ and n.

For example, if σ = 1 and n = 3, with guests A, B, C and gifts numbered 1, 2, 3, there are 42 different scenarios, as follows. We write XN to indicate that guest X took gift N – it is always clear from the context whether the gift was stolen or taken from the pool. Also, provided we multiply the final answer by 6, we can assume that the gifts are taken from the pool in the order 1, 2, 3. There are then seven possibilities:

A1, B2, C3,
A1, B2, C1, A3,
A1, B2, C1, A2, B3,
A1, B2, C2, B3,
A1, B2, C2, B1, A3,
A1, B1, A2, C3,
A1, B1, A2, C2, A3,

(1)

and so the final answer is 6 · 7 = 42.

If we continue to ignore the factor of n! that arises from the order in which the gifts are selected from the pool, the numbers of scenarios for the cases σ = 1 and n = 1, 2, 3, 4, 5 are 1, 2, 7, 37, 266, respectively.

We noticed that these five terms matched the beginning of entry A001515 in [16], although indexed differently. The nth term of A001515 is defined to be y_{n}(1), where y_{n}(x) is a Bessel polynomial [12, 13, 18], and for n = 0, 1, 2, 3, 4 the values are indeed 1, 2, 7, 37, 266. Although there was no suggestion of gift-exchanging in that entry, one of the comments there (contributed by Robert A. Proctor on April 18, 2005) mentioned set partitions and restricted Stirling numbers, and this was enough of a hint to lead us to a solution of the general problem.

Outline of paper. The connection with set partitions is discussed in §2, where Theorem 1 expresses the general solution to the problem—the function G_{σ}(n)—as a sum of restricted Stirling numbers of the second kind. We find it convenient to introduce our own notation, E_{σ}(n, k) (see (3)), for the latter numbers. Theorem 3 gives various properties of the E_{σ}(n, k), and Theorem 4 gives an integral representation for G_{σ}(n) that will enable us to use the methods of [1] and [4] to find recurrences.

We will obtain two different linear recurrences for G_{σ}(n), which we label Type C and Type D. Type C is somewhat simpler, and has leading coefficient 1, while Type D has lower order (order σ +1, in fact, see Theorem 11). To see the difference between the two types of recurrence for G_{2}(n), G_{3}(n), and G_{4}(n), compare (37) with (38), (44) with (46), and (45) with the expression in Table 2 (the first of each pair being the Type C recurrence, the second the Type D recurrence).

Sections 3, 4, and 5 deal with cases σ = 1 (where there are connections with Bessel polynomials and hypergeometric functions, see Theorem 5), σ = 2 (where we introduce the two types of recurrence), and σ ≥ 3, respectively.

Comments on the rules. (i) If σ = 1 then once a gift has been stolen it can never be stolen again. (ii) If σ = 2, and someone steals your gift, then if you wish you may immediately steal it back (provided you hadn’t stolen it to begin with), and then it cannot be stolen again. Retrieving a gift in this way, although permitted by a strict interpretation of the rules, may be prohibited at real parties. (iii) A variation of the game allows the last player to take any gift that has been unwrapped, regardless of how many times it has already been stolen, as an alternative to taking the last gift from the pool. This case only requires minor modifications of the analysis, and we will not consider it here. (iv) We also ignore the complications caused by the fact that you brought (and wrapped) one of the gifts yourself, and so are presumably unlikely to choose it when your number is called.

2 Connection with partitions of labeled sets

Let H_{σ}(n) be the number of scenarios with n gifts and a limit of σ steals, for σ ≥ 0, n ≥ 1. Then H_{σ}(n) is a multiple of n!, and we write H_{σ}(n) = n!G_{σ}(n − 1), where in G_{σ}(n − 1) we assume that the gifts are taken from the pool in the order 1, 2, …, n. We write n − 1 rather than n as the argument of G_{σ} because the nth gift plays a special (and less important) role. This also simplifies the statement of Theorem 1.

In words, G_{σ}(n) is the number of scenarios when there are n + 1 gifts, with a limit of σ steals per gift, and the gifts are taken from the pool in the order 1, 2, …, n + 1.

We recall that the Stirling number of the second kind, S_{2}(i, j), is the number of partitions of the labeled set {1, …, i} into j parts [10, 11], while for h ≥ 1 the h-restricted Stirling number of the second kind, S_{2}^{(h)}(i, j), is the number of partitions of {1, …, i} into j parts of size at most h [7, 8, 9]. It is understood that parts are always nonempty.

Theorem 1. For σ ≥ 0 and n ≥ 0,

G_{σ}(n) = ∑_{k=n}^{(σ+1)n} S_{2}^{(σ+1)}(k, n) .  (2)

Proof. Equation (2) is an assertion about G_{σ}(n), so we are now discussing scenarios where there are n + 1 gifts. For σ = 0, H_{0}(n + 1) = (n + 1)!, so G_{0}(n) = 1, in agreement with S_{2}^{(1)}(n, n) = 1.

We may assume therefore that σ ≥ 1. Let an “action” refer to a player choosing a gift γ, either by taking it from the pool or by stealing it from another player. Since we are now assuming that the gifts are taken from the pool in order, γ determines both the player and whether the action was to take a gift from the pool or to steal it from another player. So the scenario is fully specified simply by the sequence of γ values, recording which gift is chosen at each action. For example, the scenarios in (1) are represented by the sequences 123, 1213, 12123, 1223, 12213, 1123, 11223. Since the game ends as soon as the (n + 1)st gift is selected, the number of actions is at least n + 1 and at most (σ + 1)n + 1.

The sequence of γ values is therefore a sequence of integers from {1, …, n + 1} which begins with 1, ends with n + 1, where each number i ∈ {1, …, n} appears at least once and at most σ + 1 times and n + 1 appears just once, and in which the first i can appear only after i − 1 has appeared. Conversely, any sequence with these properties determines a unique scenario.

Let k denote the length of the sequence with the last entry (the unique n + 1) deleted. We map this shortened sequence to a partition of [1, …, k] into n parts: the first part records the positions of the 1’s, the second part records the positions of the 2’s, …, and the nth part records the positions of the n’s. Continuing the example, for the seven sequences above, the values of k and the corresponding partitions are as shown in Table 1.

Table 1: Values of k and partitions corresponding to the scenarios in (1).

scenario  sequence k partition
A1, B2, C3  123  2 1, 2
A1, B2, C1, A3  1213  3 13, 2
A1, B2, C1, A2, B3 12123  4 13, 24
A1, B2, C2, B3 1223 3 1, 23
A1, B2, C2, B1, A3 12213  4 14, 23
A1, B1, A2, C3 1123 3 12, 3
A1, B1, A2, C2, A3 11223  4 12, 34

The number of such partitions is precisely S_{2}^{(σ+1)}(k, n). Since the mapping from sequences to partitions is completely reversible, the desired result follows.

Corollary 2. G_{σ}(n) is equal to the number of partitions of {1, 2, …, k}, for n ≤ k ≤ (σ + 1)n, into n parts, each of size at most σ + 1.

Remark. The sums B(i) := ∑_{j} S_{2}(i, j) are the classical Bell numbers. The sums ∑_{j} S_{2}^{(h)}(i, j)

also have a long history [14, 15]. However, the sums ∑_{i} S_{2}^{(h)}(i, j) mentioned in (2) (where we sum on the first index rather than the second) do not seem to have studied before. Note that the limits in (2) are the natural limits on the summand k, and could be omitted.

To simplify the notation, and to put the most important variable first, let

E_{σ}(n, k) := S_{2}^{(σ+1)}(k, n) ,  (3)

for σ ≥ 0, n ≥ 0, k ≥ 0. In words, E_{σ}(n, k) is the number of partitions of {1, …, k} into exactly n parts of sizes in the range [1, …, σ + 1].

For n ≥ 0, E_{σ}(n, k) is nonzero only for n ≤ k ≤ (σ + 1)n. To avoid having to worry about negative arguments, we define E_{σ}(n, k) to be zero if either n or k is negative. Then the answer to our problem can be written as

G_{σ}(n) = ∑_{k=n}^{(σ+1)n} E_{σ}(n, k) .  (4)

Stirling numbers of the second kind satisfy many different recurrences and generating functions [10, Chap. V], and to a lesser extent this is also true of E_{σ}(n, k). We begin with four general properties.

Theorem 3. (i) Suppose σ ≥ 1, n ≥ 0, k ≥ 0. Then E_{σ}(n, k) = 0 for k < n or k > (σ + 1)n, E_{σ}(n, k) = 1 if k = n, and otherwise, for n < k ≤ (σ + 1)n,

E_{σ}(n, k) = ∑_{i=0}^{min\{σ,k−n\}} \binom{k − 1}{i}E_{σ}(n − 1, k − 1 − i) .  (5)

(ii) For σ ≥ 0, n ≥ 0, n ≤ k ≤ (σ + 1)n,

E_{σ}(n, k) = ∑_{(ν_{1},...,ν_{σ+1})} \frac{k!}{ν_{1}!ν_{2}! … ν_{σ+1}! 1!^{ν_{1}}2!^{ν_{2}} ⋯ (σ + 1)!^{ν_{σ+1}}} ,  (6)

where the sum is over all (σ + 1)-tuples of nonnegative integers (ν_{1}, …, ν_{σ+1}) satisfying

ν_{1} + ν_{2} + ν_{3} ⋯ + ν_{σ+1} = n ,
ν_{1} + 2ν_{2} + 3ν_{3} ⋯ + (σ + 1)ν_{σ+1} = k .  (7)

(iii) The numbers E_{σ}(n, k) have the exponential generating functions

∑_{k=n}^{(σ+1)n} E_{σ}(n, k)\frac{y^{k}}{k!} = \frac{1}{n!} (y + \frac{y^{2}}{2!} + ⋯ + \frac{y^{σ+1}}{(σ + 1)!})^{n} ,  (8)

∑_{n=0}^{∞} ∑_{k=n}^{(σ+1)n} E_{σ}(n, k)x^{n} \frac{y^{k}}{k!} = exp [x (y + \frac{y^{2}}{2!} + ⋯ + \frac{y^{σ+1}}{(σ + 1)!})] .  (9)

(iv) Suppose σ ≥ 1. Then E_{σ}(n, k) = 0 for k < n or k > (σ + 1)n, E_{σ}(n, k) = 1 if k = n, and otherwise, for n < k ≤ (σ + 1)n,

E_{σ}(n, k) = \frac{k!}{(k − n)} ∑_{i=1}^{min\{σ,k−n\}} \frac{(n + 1)i − k + n}{(i + 1)!(k − i)!}E_{σ}(n, k − i) .  (10)

Proof. (i) This is an analog of the “vertical” recurrence for the Stirling numbers [10, Eq. [3c], p. 209] (note that because (3) involves a transposition, “horizontal” recurrences for E_{σ} correspond to “vertical” recurrences for Stirling numbers). The idea of the proof is to take a partition of [1, …, k] into n parts, remove the part containing k, and renumber the remaining parts. If the part containing k has size i + 1, 0 ≤ i ≤ σ, there are \binom{k−1}{i} possibilities for the other elements in that part. (ii) This follows by standard counting arguments (cf. [10, Th. B, p. 205]), taking ν_{i} to be the number of parts of size i in the partition. (iii) (8) and (9) are analogs of the “vertical” generating functions for the Stirling numbers [10, Eqs. [2a,2b], p. 206], and follow directly from (i). (iv) We let η = k −n (the “excess” of k over n), and rewrite (8) as

∑_{η=0}^{σn} \frac{n!}{(n + η)!}E_{σ}(n, n + η)y^{η} = (1 + \frac{y}{2!} + ⋯ + \frac{y^{σ}}{(σ + 1)!})^{n} .  (11)

We now apply the J. C. P. Miller method for exponentiating a polynomial. In the notation of [22], we take

P (y) = (1 + \frac{y}{2!} + ⋯ + \frac{y^{σ}}{(σ + 1)!}) , a(n, η) = \frac{n!}{(n + η)!}E_{σ}(n, n + η) .  (12)

Then (10) follows at once from (11) and the main theorem of [22].

From (4) and (6) we have:

G_{σ}(n) = ∑_{k=n}^{(σ+1)n} ∑_{(ν_{1},...,ν_{σ+1})} \frac{k!}{ν_{1}!ν_{2}! … ν_{σ+1}! 1!^{ν_{1}}2!^{ν_{2}} ⋯ (σ + 1)!^{ν_{σ+1}}} ,  (13)

where the inner sum is over all (σ + 1)-tuples of nonnegative integers (ν_{1}, …, ν_{σ+1}) satisfying (7). This may be rewritten as a sum of multinomial coefficients:

G_{σ}(n) = \frac{1}{n!} ∑_{i_{1}=1}^{σ+1} ∑_{i_{2}=1}^{σ+1} ⋯ ∑_{i_{n}=1}^{σ+1} \binom{i_{1} + i_{2} + ⋯ + i_{n}}{i_{1}, i_{2}, ⋯, i_{n}} ,  (14)

where i_{r} is the size of the rth part, or, equivalently, the number of times the rth gift is chosen in an action.

Equation (6) also leads to an integral representation and generating function for G_{σ}(n).

Theorem 4. (i) For σ ≥ 1,

G_{σ}(n) = \frac{1}{n!} ∫_{0}^{∞} e^{−y} (∑_{j=1}^{σ+1} \frac{y^{j}}{j!} )^{n} dy .  (15)

(ii) The G_{σ}(n) have ordinary generating function

G_{σ}(x) = ∑_{n=0}^{∞} G_{σ}(n)x^{n}

= ∫_{0}^{∞} exp (−y + x ∑_{j=1}^{σ+1} \frac{y^{j}}{j!} ) dy .  (16)

Proof. (i) Using Euler’s integral representation for the factorial,

k! = ∫_{0}^{∞} e^{−y}y^{k}dy ,  (17)

the right-hand side of (15) is

\frac{1}{n!} ∫_{0}^{∞} e^{−y} ∑_{(ν_{1},...,ν_{σ+1})} \frac{n! y^{ν_{1}+2ν_{2}+3ν_{3}+···+(σ+1)ν_{σ+1}}}{ν_{1}!ν_{2}! … ν_{σ+1}! 2!^{ν_{2}} ⋯ (σ + 1)!^{ν_{σ+1}}}

= ∑_{(ν_{1},...,ν_{σ+1})} \frac{(ν_{1} + 2ν_{2} + ⋯ + (σ + 1)ν_{σ+1})!}{ν_{1}!ν_{2}! … ν_{σ+1}! 2!^{ν_{2}} ⋯ (σ + 1)!^{ν_{σ+1}}} ,  (18)

where the sums are over all (σ + 1)-tuples of nonnegative integers (ν_{1}, …, ν_{σ+1}) satisfying ν_{1} + ν_{2} + ⋯ + ν_{σ+1} = n. This is the same as the expression for G_{σ}(n) in (13). (ii) is an immediate consequence of (i).

The recurrence (5) makes it easy to compute as many values of E_{σ}(n, k) and G_{σ}(n) as one wishes. In the rest of the paper we will derive further formulas and recurrences, and asymptotic estimates for these numbers.

3 The case σ = 1

In the case σ = 1, i.e., when a gift can be stolen at most once, from Theorem 3 we have E_{1}(1, k) = δ_{1,k}, and, for n ≥ 2, E_{1}(n, k) = 0 for k < n and k > 2n, E_{1}(n, n) = 1, and

E_{1}(n, k) = E_{1}(n − 1, k − 1) + (k − 1)E_{1}(n − 1, k − 2) ,  (19)

for n < k ≤ 2n. We also have the explicit formula

E_{1}(n, k) = \frac{k!}{(2n − k)! (k − n)! 2^{k−n}} ,  (20)

for n ≤ k ≤ 2n; and the generating function

∑_{n=0}^{∞} ∑_{k=n}^{2n} E_{1}(n, k) x^{n} \frac{y^{k}}{k!} = e^{x(y+y^{2}/2)} .  (21)

It follows from (4) and (20) that

G_{1}(n) = ∑_{k=n}^{2n} \frac{k!}{(2n − k)! (k − n)! 2^{k−n}}

= ∑_{i=0}^{n} \frac{(n + i)!}{(n − i)! i! 2^{i}} .  (22)

Equation (22) shows that the sequence G_{1}(n) is indeed given by entry A001515 in [16]. That entry states (mostly without proof) several other properties of these numbers, taken from various sources, notably Grosswald [12]. We collect some of these properties in the next theorem. We recall from [12] that the Bessel polynomial y_{n}(z) is given by

y_{n}(z) := ∑_{i=0}^{n} \frac{(n + i)!z^{i}}{(n − i)! i! 2^{i}} .  (23)

Also _{2}F_{0} and (later) _{2}F_{1} denote hypergeometric functions.

Theorem 5. (i)

G_{1}(n) = y_{n}(1) .  (24)

(ii)

G_{1}(n) = _{2}F_{0} [ \begin{matrix}n + 1, −n \\ − \end{matrix} ; −\frac{1}{2} ] .  (25)

(iii)

G_{1}(n) = (2n − 1)G_{1}(n − 1) + G_{1}(n − 2) .  (26)

for n ≥ 2, with G_{1}(0) = 1, G_{1}(1) = 2. (iv) The G_{1}(n) have exponential generating function

EG_{1}(x) := ∑_{n=0}^{∞} G_{1}(n)\frac{x^{n}}{n!} = \frac{e^{1−\sqrt{1−2x}}}{\sqrt{1 − 2x}} .  (27)

(v)

G_{1}(n) ∼ \frac{e(2n)!}{n!2^{n}} as n → ∞ .  (28)

Proof. (i) and (ii) are immediate consequences of (22). (iii) It is easy to verify from (20) that

E_{1}(n, k) = (2n − 1)E_{1}(n − 1, k − 2) + E_{1}(n − 2, k − 2) .  (29)

Our conventions about negative arguments make it unnecessary to put any restrictions on the range over which (29) holds. By summing (29) on k we obtain (26). (Equation (26) also follows from one of the recurrences for Bessel polynomials [12, Eq. (7), p. 18], [13].) (iv) By multiplying (26) by x^{n}/n! and summing on n from 2 to ∞ we obtain the differential equation

EG′′_{1}(x) = 3 EG′_{1}(x) + 2x EG′′_{1}(x) + EG_{1}(x) .  (30)

Then the right-hand side of (27) is the unique solution of (30) which satisfies EG_{1}(0) = 1, EG′_{1}(0) = 2.

(v) This follows from (22), since the terms i = n − 1 and i = n dominate the sum (see also [12, Eq. (1), p. 124]).

4 The case σ = 2

In the case when σ = 1, i.e., when a gift can be stolen at most once, the problem, as we saw in the previous section, turned out to be related to the values of Bessel polynomials, and the principal sequence, G_{1}(n), had been studied before. For σ ≥ 2, we appear to be in new territory—for one thing, the sequences G_{2}(n), G_{3}(n), … were not in [16].^{2}

We naturally tried to find analogs of the various parts of Theorem 5 that would hold for σ ≥ 2. Let us begin with the simplest result, the asymptotic behavior. This is directly analogous to Theorem 5(v).

Theorem 6. For fixed σ ≥ 1,

G_{σ}(n) ∼ \frac{e((σ + 1)n)!}{n!(σ + 1)!^{n}} as n → ∞ .  (31)

Proof. (Sketch) The two terms of (13) corresponding to {k = (σ + 1)n, ν_{σ+1} = n, other ν_{i} = 0} and {k = (σ + 1)n − 1, ν_{σ+1} = n − 1, ν_{σ} = 1, other ν_{i} = 0} dominate the right-hand side of (13), and are both equal to ((σ + 1)n)!/(n!(σ + 1)!^{n}). Dividing the sum by this quantity gives a converging sum, in which a subset of terms approach 1 + 1 + 1/2! + 1/3! + ..., while the others vanish as n → ∞.

Concerning Theorem 5(i), we do not know if there is a generalization of Bessel polynomials whose value gives (13) for σ ≥ 2.

As for Theorem 5(ii), there is a relationship with hypergeometric functions in the case σ = 2. From (6) we have

E_{2}(n, k) = ∑_{c=max\{0,k−2n\}}^{⌊(k−n)/2⌋} \frac{k!}{(2n − k + c)!(k − n − 2c)!c! 2^{k−n−c}3^{c}}

= ∑_{c=max\{0,η−n\}}^{⌊η/2⌋} \frac{k!}{(n − η + c)!(η − 2c)!c! 2^{η−c}3^{c}} ,  (32)

where η = k − n.

2G_{2}(n), G_{3}(n), G_{4}(n) are now entries A144416, A144508, A144509 in [16].

Theorem 7. (i) Let η = k − n. If η ≤ n then

E_{2}(n, k) = \frac{(n + η)!}{η!(n − η)!2^{η}} _{2}F_{1} [ \begin{matrix}−η/2, −η/2 + 1/2 \\ n − η + 1 \end{matrix} ; \frac{8}{3} ] .  (33)

If η ≥ n then

E_{2}(n, k) = \frac{(η + n)!}{(2n − η)!(η − n)!2^{n}3^{η−n}} _{2}F_{1} [ \begin{matrix}−n + η/2, −n + η/2 + 1/2 \\ η − n + 1 \end{matrix} ; \frac{8}{3} ] .  (34)

(ii)

G_{2}(n) = ∑_{η=0}^{n−1} \frac{(n + η)!}{η!(n − η)!2^{η}} _{2}F_{1} [ \begin{matrix}−η/2, −η/2 + 1/2 \\ n − η + 1 \end{matrix} ; \frac{8}{3} ]

+ ∑_{η=n}^{2n} \frac{(n + η)!}{(2n − η)!(η − n)!2^{n}3^{η−n}} _{2}F_{1} [ \begin{matrix}−n + η/2, −n + η/2 + 1/2 \\ η − n + 1 \end{matrix} ; \frac{8}{3} ] . (35)

Proof. (i) follows from (32) using the standard rules for converting sums of products of factorials to hypergeometric functions (cf. [3]), and (ii) follows from (4).

We next give an analog of (29) and our first (Type C) recurrence for G_{2}(n).

Theorem 8. (i)

E_{2}(n, k) = (9n^{2} − 9n + 2)E_{2}(n − 1, k − 3)/2 − 5E_{2}(n − 1, k − 1)/2
+ (9n^{2} − 36n + 35)E_{2}(n − 2, k − 4)/2 + 6(n − 1)E_{2}(n − 2, k − 3)
− 3E_{2}(n − 2, k − 2)/2 + 3(2n − 5)E_{2}(n − 3, k − 4) + 5E_{2}(n − 3, k − 3)/2
+ 5E_{2}(n − 4, k − 4)/2 .  (36)

(ii)

G_{2}(n) = (9n^{2} − 9n − 3)G_{2}(n − 1)/2
+ (9n^{2} − 24n + 20)G_{2}(n − 2)/2
+ (6n − 25/2)G_{2}(n − 3) + 5G_{2}(n − 4)/2 ,  (37)

for n ≥ 4, with G_{2}(0) = 1, G_{2}(1) = 3, G_{2}(2) = 31, G_{2}(3) = 18252.

Proof. (i) Equation (36) follows by applying the Almkvist-Zeilberger technique of “differentiating under the integral sign” from [1], starting with the integral representation for G_{2}(n) given in (15). (ii) Eq. (37) follows by summing (36) on k, just as (26) followed from (29).

Remarks. (i) To apply the technique of “differentiating under the integral sign” from [1], we used the Maple implementation given in [2].

(ii) The recurrence (36) can also be proved using (33), (34), and Gauss’s contiguity relations for hypergeometric functions [6, §2.1.2], [19, §14.7].

(iii) A third proof may be obtained using the method of Sister Mary Celine Fasenmyer, as described in §4.1 of [17].

We discovered (37) by experiment, using Theorem 6 to suggest the leading term. (If r(n) denotes the right-hand side of (31), then r(n)/r(n − 1) = (9n^{2} − 9n + 2)/2.) This is a fourth-order recurrence for G_{2}(n). We also discovered (again by experimenting) a third-order recurrence for G_{2}(n), although the coefficient of G_{2}(n) on the left side is now n − 2 rather than 1.

Theorem 9. For n ≥ 3,

(n − 2)G_{2}(n) = n(9n^{2} − 27n + 17)G_{2}(n − 1)/2
+ (6n^{2} − 15n + 13/2)G_{2}(n − 2)
+ (5n − 5)G_{2}(n − 3)/2 ,  (38)

with G_{2}(0) = 1, G_{2}(1) = 3, G_{2}(2) = 31.

In view of (35), (38) is equivalent to a complicated identity involving hypergeometric functions.

Proof. To prove (38) we apply the Almkvist-Zeilberger technique of “differencing under the integral sign” from [1, §7], again starting from the integral representation for G_{2}(n) given in (15). (We again used the Maple implementation of the technique from [2].)

Since (36) uses the continuous version of the algorithm in [1], and (38) the discrete version, we refer to these recurrences as Types C and D respectively. When σ = 1, both Types C and D produce (26).

Finally, if we need more terms of the asymptotic expansion than are given in Theorem 6 (or a computer-certified proof of it!), we can apply the Poincaré–Birkhoff–Trjitzinsky method as presented in [21] to the Type C recurrence (37). This works for any σ; for σ = 2, we find that

G_{2}(n) ∼ \frac{e (3n)!}{n! 6^{n}} (1 + \frac{1}{3 n} + \frac{1}{54 n^{2}} − \frac{8}{81 n^{3}} − ⋯) .  (39)

5 The cases σ ≥ 3

In this final section we discuss the cases σ ≥ 3, mostly concentrating on G_{σ}(n) rather than E_{σ}(n, k). We have not found any connections between these G_{σ}(n) and generalized Bessel polynomials or hypergeometric functions.

Let us first prove that recurrences for G_{σ}(n) and E_{σ}(n, k) always exist. This follows from the Wilf–Zeilberger “Fundamental Theorem for multivariate sums” ([17, Theorem 4.5.1], [20]).

Theorem 10. (i) For σ ≥ 1, there is a number δ ≥ 0 such that E_{σ}(n, k) satisfies a recurrence of the form

∑_{i=0}^{δ} ∑_{j=0}^{δ} C_{i,j}^{(E)}(n)E_{σ}(n − i, k − j) = 0 for all n ≥ δ ,  (40)

where the coefficients C_{i,j}^{(E)}(n) are polynomials in n with coefficients depending on i and j. (ii) For σ ≥ 1, there is a number δ ≥ 0 such that G_{σ}(n) satisfies a recurrence of the form

∑_{i=0}^{δ} C_{i}^{(G)}(n)G_{σ}(n − i) = 0 for all n ≥ δ ,  (41)

where the coefficients C_{i}^{(G)}(n) are polynomials in n with coefficients depending on i.

Proof. (ii) As usual, Eq. (41) follows by summing (40) on k. (i) We will use the case σ = 3 to illustrate the proof, the general case being similar. We know from (6) that

E_{3}(n, k) = ∑_{a,b,c,d} \frac{k!}{a! b! c! d! 2^{b} 6^{c} 24^{d}} ,  (42)

where the sum is over all 4-tuples of nonnegative integers (a, b, c, d) satisfying

a + b + c + d = n ,
a + 2b + 3c + 4d = k .

In other words,

\frac{E_{3}(n, k)}{2^{n}} = ∑_{c,d} \frac{k!}{(2n − k + c + 2d)! (k − n − 2c − 3d)! c! d! 2^{k−c} 3^{c+d}} ,  (43)

where now the sum is over all values of c and d for which the summand is defined. This summand is a “holonomic proper-hypergeometric term”, in the sense of [20], and it follows from the Fundamental Theorem in that paper that E_{3}(n, k)/2^{n} and hence E_{3}(n, k) satisfies a recurrence of the desired form. Similarly, in the general case, we write the summand in E_{σ}(n, k) as a function of n, k, a_{3}, …, a_{σ+1}, again obtaining a holonomic proper-hypergeometric term.

The Type C recurrences for G_{3}(n) and G_{4}(n) (obtained as in §4) are:^{3}

G_{3}(n) = (32n^{3}/3 − 16n^{2} + 10n/3 − 49/6)G_{3}(n − 1)
+ (48n^{3} − 236n^{2} + 1157n/3 − 650/3)G_{3}(n − 2)
+ (80n^{3} − 382n^{2} + 641n − 511)G_{3}(n − 3)/3
+ (64n^{3}/3 − 218n^{2} + 2696n/3 − 7915/6)G_{3}(n − 4)
+ (56n^{2} − 490n + 6853/6)G_{3}(n − 5)
+ (56n − 1703/6)G_{3}(n − 6)
+ 58G_{3}(n − 7)/3 ,  (44)

G_{4}(n) = (625 n^{4} − 1250 n^{3} + 625 n^{2} − 300 n − 543)G_{4}(n − 1)/24
+ (27500 n^{4} − 184000 n^{3} + 447500 n^{2} − 473075 n + 180003)G_{4}(n − 2)/72
+ (336875 n^{4} − 2546500 n^{3} + 7679675 n^{2} − 12016800 n + 8048577)G_{4}(n − 3)/864
+ (4833125 n^{4} − 77581625 n^{3} + 476892700 n^{2} − 1304291160 n + 1325759504)G_{4}(n − 4)/2592
+ (1700625 n^{4} + 28316750 n^{3} − 605973450 n^{2} + 3123850885 n − 5033477363)G_{4}(n − 5)/7776
+ (2670000 n^{4} − 64380500 n^{3} + 704577200 n^{2} − 3610058445 n + 6818722190)G_{4}(n − 6)/7776
+ (2002500 n^{4} − 51976000 n^{3} + 517392050 n^{2} − 2252744530 n + 3561765885)G_{4}(n − 7)/7776
+ (9078000 n^{3} − 209915400 n^{2} + 1640828980 n − 4301927039)G_{4}(n − 8)/7776
+ (5393400 n^{2} − 91413680 n + 390747263)G_{4}(n − 9)/2592
+ (1593990 n − 14522219)G_{4}(n − 11)/972
+ 310343G_{4}(n − 11)/648 .  (45)

3The Types C and D recurrences for G_{1}(n) through G_{15}(n) can be found in http://www.math.rutgers.edu/~zeilberg/tokhniot/oGifts2.txt and http://www.math.rutgers.edu/~zeilberg/tokhniot/oGifts1.txt respectively.

We also found analogous recurrences for the E_{σ}(n, k), which we omit. The Type D recurrence for G_{3}(n) is given in (46), and that for G_{4}(n) can be seen in Table 2.

3 (64 n^{3} − 360 n^{2} + 762 n − 547) G_{3} (n) = (2048 n^{6} − 14592 n^{5} + 42304 n^{4} − 58384 n^{3} + 36972 n^{2} − 10888 n + 2381) G_{3} (n − 1) + (5376 n^{5} − 35616 n^{4} + 92200 n^{3} − 110788 n^{2} + 54186 n − 5365) G_{3} (n − 2) + (5376 n^{4} − 27552 n^{3} + 52616 n^{2} − 45620 n + 10514) G_{3} (n − 3)

+ (1856 n^{3} − 4872 n^{2} + 6786 n − 2349) G_{3} (n − 4)  (46)

Table 2: The Type D recurrence for G_{4}(n)..

72 (16687500 n^{6} − 209150000 n^{5} + 1070031875 n^{4} − 3019737375 n^{3} + 4945130775 n^{2} − 4329975510 n + 1513065336) G_{4} (n) =

(31289062500 n^{10} − 454734375000 n^{9} + 2821911328125 n^{8} − 10081802109375 n^{7} + 22781118187500 n^{6} − 33185759803125 n^{5} + 30632133843750 n^{4} − 17235043672875 n^{3} + 5483042423925 n^{2} − 700627863570 n − 57348303408) G_{4} (n − 1)

+ (141843750000 n^{9} − 1990540625000 n^{8} + 11724386562500 n^{7} − 39078979093750 n^{6} + 81505745228125 n^{5} − 107513140175625 n^{4} + 84513872351000 n^{3} − 33225357802500 n^{2} + 2737777538500 n + 1197797898465) G_{4} (n − 2)

+ (252815625000 n^{8} − 3168622500000 n^{7} + 16127100406250 n^{6} − 45548278450000 n^{5} + 80090937641250 n^{4} − 86115353337125 n^{3} + 47445915625400 n^{2} − 6693899844450 n − 2609871946015) G_{4} (n − 3)

+ (199248750000 n^{7} − 1999129125000 n^{6} + 7757225837500 n^{5} − 16990061751250 n^{4} + 23960112482875 n^{3} − 17664322875275 n^{2} + 4396729093865 n + 802753105180) G_{4} (n − 4)

+ (58189312500 n^{6} − 380170175000 n^{5} + 957510585625 n^{4} − 1734293884125 n^{3} + 1621184408800 n^{2} − 573345040895 n − 48634580313) G_{4} (n − 5) .

Equation (46) and the expression in Table 2 are linear recurrences of orders 4 and 5, respectively, and the Type D recurrences for G_{5}(n) and G_{6}(n) are similarly of orders 6 and 7. An analogous property holds for all σ.

Theorem 11. For σ ≥ 1, the Type D recurrence for G_{σ}(n) has order at most σ + 1.

Proof. This follows from Theorem AZ of [4]. To see this we apply that theorem to the quantity

Ĝ_{σ}(n) := n! G_{σ}(n) = ∫_{0}^{∞} e^{−x} (∑_{j=1}^{σ+1} \frac{x^{j}}{j!} )^{n} dx .

That is, for the expression F (n, x) in the statement of Theorem AZ we take P OL(n, x) = 1, a(x) = −x, b(x) = 1, S_{p}(x) = 1, s(x) = ∑_{j=1}^{σ+1} x^{j}/j!, and t(x) = 1. The conclusion of the theorem is that Ĝ_{σ}(n) (and hence G_{σ}(n)) satisfies a linear recurrence of order at most L = σ + 1.

References

[1] G, Almkvist and D. Zeilberger. The method of differentiating under the integral sign. J. Symbolic Computation, 10:571–591, 1990.

[2] G, Almkvist and D. Zeilberger. A MAPLE program that finds, and proves, recurrences and differential equations satisfied by hyperexponential definite integrals. ACM SIGSAM Bulletin, 25.3:14–17, 1991.

[3] G. E. Andrews. Applications of basic hypergeometric series. SIAM Rev., 16:441–484, 1974.

[4] M. Apagodu and D. Zeilberger. Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory. Adv. Appl. Math., 37:139–152, 2006.

[5] D. Applegate and N. J. A. Sloane. The gift exchange problem. arXiv preprint arXiv:0907.0513, July 2, 2009.

[6] H. Bateman et al. Higher transcendental functions. McGraw-Hill, NY, Vol. 1, 1953.

[7] J. Y. Choi, L. Long and J. D. H. Smith. Reciprocity for multirestricted Stirling numbers. J. Combin. Theory, Ser. A, 113:1050–1060, 2006.

[8] J. Y. Choi and J. D. H. Smith. On the combinatorics of multi-restricted numbers. Ars Combin., 75:45–63, 2005.

[9] J. Y. Choi and J. D. H. Smith. Recurrences for tri-restricted numbers. J. Combin. Math. Combin. Comput., 58:3–11, 2006.

[10] L. Comtet. Advanced combinatorics. Reidel, Dordrecht, 1974.

[11] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994.

[12] E. Grosswald. Bessel polynomials. Lecture Notes in Math., Vol. 698, Springer, 1978.

[13] H. L. Krall and O. Frink. A new class of orthogonal polynomials: the Bessel polynomials. Trans. Amer. Math. Soc., 65:100–115, 1949.

[14] F. L. Miksa, L. Moser and M. Wyman. Restricted partitions of finite sets. Canad. Math. Bull., 1:87–96, 1958.

[15] L. Moser and M. Wyman. On solutions of x^{d} = 1 in symmetric groups. Canad. J. Math., 7:159–168, 1955.

[16] The OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published elec-

tronically at https://oeis.org.

[17] M. Petkovšek, H. S. Wilf and D. Zeilberger. A = B. Peters, Wellesley, MA, 1996.

[18] J. Riordan. Combinatorial identities. Wiley, NY, 1968.

[19] E. T. Whittaker and G. N. Watson. A course of modern analysis. Cambridge Univ. Press, 4th ed., 1963.

[20] H. S. Wilf and D. Zeilberger. An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities. Invent. Math., 108:575–633, 1992.

[21] J. Wimp and D. Zeilberger. Resurrecting the asymptotics of linear recurrences. J. Math. Anal. Appl., 111:162–176, 1985.

[22] D. Zeilberger. The J. C. P. Miller recurrence for exponentiating a polynomial, and its q-analog. J. Differ. Equations Appl., 1:57–60, 1995.