The generalized Frobenius problem via restricted partition functions

DOI10.37236/11161MaRDI QIDQ6199186zbMATH OpenFDO

Authors

Publication date 23 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) The Frobenius problem (11D07) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: Given relatively prime positive integers, $a_1,ldots,a_n$, the Frobenius number is the largest integer with no representations of the form $a_1{x}_1+cdots+a_n{x}_n$ with nonnegative integers $x_i$. This classical value has recently been generalized: given a nonnegative integer $k$, what is the largest integer with at most $k$ such representations? Other classical values can be generalized too: for example, how many nonnegative integers are representable in at most $k$ ways? For sufficiently large $k$, we give formulas for these values by understanding the level sets of the restricted partition function (the function $f(t)$ giving the number of representations of $t$). Furthermore, we give the full asymptotics of all of these values, as well as reprove formulas for some special cases (such as the $n=2$ case and a certain extremal family from the literature). Finally, we obtain the first two leading terms of the restricted partition function as a so-called quasi-polynomial.

Recommendations

• An extreme family of generalized Frobenius numbers
• The polynomial part of a restricted partition function related to the Frobenius problem
• scientific article; zbMATH DE number 5041220
• Frobenius Coin-Exchange Generating Functions
• On a generalization of the Frobenius number

Cites work

• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• An extreme family of generalized Frobenius numbers
• Bounds on generalized Frobenius numbers
• Complexity of the Frobenius problem
• Computing the Continuous Discretely
• Frobenius Coin-Exchange Generating Functions
• Generalized Frobenius numbers: bounds and average behavior
• scientific article; zbMATH DE number 3163859 (Why is no real title available?)
• 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 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 2066386 (Why is no real title available?)
• scientific article; zbMATH DE number 5041220 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Lattice translates of a polytope and the Frobenius problem
• On the number of integer points in translated and expanded polyhedra
• 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
• Unbounded discrepancy in Frobenius numbers

Cited in

(2)

• Generalized Frobenius number of three variables
• Formulas for the generalized Frobenius number of triangular numbers

This page was built for publication: The generalized Frobenius problem via restricted partition functions

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