A bijection between necklaces and multisets with divisible subset sum

MaRDI QIDQ1732032zbMATH OpenFDO

Authors Swee Hong Chan

Publication date 15 March 2019

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

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

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

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19)

Abstract: Consider these two distinct combinatorial objects: (1) the necklaces of length $n$ with at most $q$ colors, and (2) the multisets of integers modulo $n$ with subset sum divisible by $n$ and with the multiplicity of each element being strictly less than $q$. We show that these two objects have the same cardinality when $q$ and $n$ are mutually coprime. Additionally, when $q$ is a prime power, we construct a bijection between these two objects by viewing necklaces as cyclic polynomials over the finite field of size $q$. Specializing to $q=2$ answers a bijective problem posed by Richard Stanley.

Review text

Summary: Consider these two distinct combinatorial objects: (1) the necklaces of length \(n\) with at most \(q\) colors, and (2) the multisets of integers modulo \(n\) with subset sum divisible by \(n\) and with the multiplicity of each element being strictly less than \(q\). We show that these two objects have the same cardinality if \(q\) and \(n\) are mutually coprime. Additionally, when \(q\) is a prime power, we construct a bijection between these two objects by viewing necklaces as cyclic polynomials over the finite field of size \(q\). Specializing to \(q=2\) answers a bijective problem posed by \textit{R. P. Stanley} [Enumerative combinatorics. Vol. 1. Cambridge: Cambridge University Press (2012; Zbl 1247.05003), Chapter 1, Problem 105(b)].

Recommendations

• On the number of necklaces whose co-periods divide a given integer
• Necklaces and slimes
• Difference necklaces
• Necklaces, self-reciprocal polynomials, and \(q\)-cycles
• Combinatorics of necklaces and ``Hermite reciprocity

Cites work

• Elementary Number Theory
• Enumeration of power sums modulo a prime
• Finite fields and Galois rings
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3689291 (Why is no real title available?)
• The arithmetic Tutte polynomials of the classical root systems
• Toric arrangements associated to graphs

Cited in

(4)

• A new sieve for restricted multiset counting
• Necklaces and slimes
• On the number of necklaces whose co-periods divide a given integer
• A bijection between necklaces and restricted multisets

This page was built for publication: A bijection between necklaces and multisets with divisible subset sum

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