Geodesic
A bijection between necklaces and multisets with divisible subset sum
Swee Hong Chan1
1Cornell University
The electronic journal of combinatorics, Tome 26 (2019) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 Richard Stanley (Enumerative Combinatorics Vol. 1 Chapter 1, Problem 105(b)).
DOI : 10.37236/7804
Classification : 05A19

Swee Hong Chan  1

1 Cornell University 
@article{10_37236_7804,
     author = {Swee Hong Chan},
     title = {A bijection between necklaces and multisets with divisible subset sum},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {1},
     doi = {10.37236/7804},
     zbl = {1409.05030},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7804/}
}
TY  - JOUR
AU  - Swee Hong Chan
TI  - A bijection between necklaces and multisets with divisible subset sum
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7804/
DO  - 10.37236/7804
ID  - 10_37236_7804
ER  - 
%0 Journal Article
%A Swee Hong Chan
%T A bijection between necklaces and multisets with divisible subset sum
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7804/
%R 10.37236/7804
%F 10_37236_7804
Swee Hong Chan. A bijection between necklaces and multisets with divisible subset sum. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7804

Cité par Sources :