Analysis of the gift exchange problem

Analysis of the gift exchange problem
By Moa Apagodu, David Applegate, Neil J. A. Sloane, and Doron Zeilberger
.pdf LaTex

[Appeared in Electronic J. of Combinatorics, Volume 24(3), paper P3.9]

First Written: Jan. 26, 2017. This version: Feb. 5, 2017.
David Applegate and Neil Sloane, inspired, in large part, by an insightful comment made by Bob Proctor regarding OEIS sequence A1515, wrote a nice earlier version. In the current version, Moa Apagodu and myself (DZ), joined in, and got Shalosh B. Ekhad to do some work.

On Line Appendices

On-Line Appendix I

On-Line Appendix II

Accompanying Maple Programs
Important: This article is accompanied by a the Maple program

DavidNeil.txt that computes the minimal-order recurrences using the (discrete) Almkvist-Zeilberger and minimal-order differential equations for the generating functions.

EKAHD.txt A new vesrion of EKHAD.txt that contains procedure Matana(n,K) used below.

Sample Input and Output for DavidNeil

To get the minimal recurrences satisfied by G_σ(n), and asymptotics to order 1/n⁶ for σ from 1 to 6, the input yields the output

To get the minimal-order differential equations satisfied by the generating functions for G_σ(n), g_σ(x), for σ from 1 to 15, the input yields the output

Sample Input and Output for EKHAD.txt

To get the minimal recurrences satisfied by G_σ(n) or σ from 1 to 15, the input yields the input.
Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page