Frobenius Coin-Exchange Generating Functions

DOI10.1080/00029890.2020.1707625MaRDI QIDQ4960436zbMATH OpenOpenAlexFDO

Authors Leonardo Bardomero, Matthias Beck

Publication date 16 April 2020

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.00554

zbMATH Keywords

generating functionlinear Diophantine problem of FrobeniusFrobenius coin-exchange problem

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of partitions of integers (05A17) The Frobenius problem (11D07)

Abstract: We study variants of the emph{Frobenius coin-exchange problem}: given $n$ positive relatively prime parameters, what is the largest integer that cannot be represented as a nonnegative integral linear combination of the given integers? This problem and its siblings can be understood through generating functions with 0/1 coefficients according to whether or not an integer is representable. In the 2-parameter case, this generating function has an elegant closed form, from which many corollaries follow, including a formula for the Frobenius problem. We establish a similar closed form for the generating function indicating all integers with exactly $k$ representations, with similar wide-ranging corollaries.

Recommendations

• Generating functions associated to Frobenius algebras
• Generalization of a Result of Sylvester Regarding the Frobenius Coin Problem and an Elementary Proof of Eisenstein's Lemma for Jacobi Symbols
• scientific article; zbMATH DE number 3230287
• Generating functions
• scientific article; zbMATH DE number 4063514
• scientific article; zbMATH DE number 4008820
• scientific article; zbMATH DE number 3627192

Cites work

• scientific article; zbMATH DE number 4089553 (Why is no real title available?)
• scientific article; zbMATH DE number 166132 (Why is no real title available?)
• scientific article; zbMATH DE number 579489 (Why is no real title available?)
• scientific article; zbMATH DE number 2066386 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• A Circle-Of-Lights Algorithm for the "Money-Changing Problem"
• A Minimal-Path Algorithm for the "Money Changing Problem"
• An algorithm for a linear Diophantine equation and a problem of Frobenius
• An extreme family of generalized Frobenius numbers
• Complexity of the Frobenius problem
• Computing the Continuous Discretely
• Generators and relations of abelian semigroups and semigroup rings
• Lattice translates of a polytope and the Frobenius problem
• Numerical semigroups, cyclotomic polynomials, and Bernoulli numbers
• On the linear diophantine problem of Frobenius
• Parametric polyhedra with at least \(k\) lattice points: their semigroup structure and the \(k\)-Frobenius problem
• Short generating functions for some semigroup algebras
• Short rational generating functions for lattice point problems
• Symmetric semigroups of integers generated by 4 elements
• The Number of Terms in the Cyclotomic Polynomial F pq (x)
• Unbounded discrepancy in Frobenius numbers

Cited in

(5)

• On the solutions of three-variable Frobenius-related problems using order reduction approach
• The generalized Frobenius problem via restricted partition functions
• The Frobenius number for sequences of triangular numbers associated with number of solutions
• On the determination of p-Frobenius and related numbers using the p-Apéry set
• The Frobenius coin problem -- a cylindrical approach

This page was built for publication: Frobenius Coin-Exchange Generating Functions

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