Frobenius Coin-Exchange Generating Functions

DOI10.1080/00029890.2020.1707625zbMATH Open1444.11045arXiv1901.00554OpenAlexW3014547306MaRDI QIDQ4960436FDOQ4960436

Authors: Leonardo Bardomero, Matthias Beck 

Publication date: 16 April 2020

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

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.

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

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

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)

Cites Work

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

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)