Analysis of the gift exchange problem

MaRDI QIDQ2363700zbMATH OpenFDO

Authors Moa Apagodu, N. J. A. Sloane, Doron Zeilberger, David Applegate

Publication date 26 July 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.08394, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p9

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

hypergeometric functionsrestricted Stirling numbersset partitionsBessel polynomialsAlmkvist-Zeilberger algorithmgift swappingWilf-Zeilberger summation

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of partitions of integers (05A17) Recurrences (11B37) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Probabilistic games; gambling (91A60)

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 sigma times. The problem is to determine the number of ways that the game can be played out, for given values of sigma 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.

Recommendations

• Optimal incentives under gift exchange
• The swapping problem
• The Secret Santa Problem
• On the generalized shuffle-exchange problem
• scientific article; zbMATH DE number 1353830
• scientific article; zbMATH DE number 1816801
• Gift equilibria and Pareto optimality reconsidered
• On the complexity of exchanging

Cites work

• scientific article; zbMATH DE number 5127202 (Why is no real title available?)
• scientific article; zbMATH DE number 3176961 (Why is no real title available?)
• scientific article; zbMATH DE number 1231230 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• scientific article; zbMATH DE number 2192195 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• scientific article; zbMATH DE number 3081880 (Why is no real title available?)
• A New Class of Orthogonal Polynomials: The Bessel Polynomials
• An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
• Analysis of the gift exchange problem
• Applications of Basic Hypergeometric Functions
• Bessel polynomials
• Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory
• On Solutions of x^d = 1 In Symmetric Groups
• Reciprocity for multirestricted Stirling numbers
• Restricted Partitions of Finite Sets
• Resurrecting the asymptotics of linear recurrences
• The J.C.P. miller recurrence for exponentiating a polynomial, and its q- analog
• The method of differentiating under the integral sign

Cited in

(5)

• The secret Santa problem continues
• Christmas gift exchange games
• On the Stirling numbers associated with the meromorphic Weyl algebra
• Analysis of the gift exchange problem
• The Secret Santa Problem

Describes a project that uses

Uses Software

• DEtools
• MultiZeilberger
• OEIS

This page was built for publication: Analysis of the gift exchange problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363700)