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

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/n6 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