1,5

Turning over the necklace is not allowed (the group is cyclic not dihedral). T(n,k) = T(k,n) follows immediately from the formula. - N. J. A. Sloane, May 03 2014

T(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021

Define F(n,k,t) as the set of multisets of natural numbers less than n with cardinality k and sum t modulo n. When n is a positive odd integer |F(n,k,0)|=T(n,k). Chan asks for a bijective proof of this, and Oh & Park construct a bijection for the case where n or k is prime. - Elijah Beregovsky, Oct 18 2025

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Swee Hong Chan, A bijection between necklaces and multisets with divisible subset sum, arXiv:1802.03507 [math.CO], 2018-2019.

Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.

A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233--238. MR1691428 (2000c:13006)

A. Elashvili, M. Jibladze and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - N. J. A. Sloane, Aug 06 2014

Suho Oh and Jina Park, Necklaces and slimes, Discrete Mathematics, Vol. 343, Issue 8, Aug. 2020.

N. J. A. Sloane, A Note on Modular Partitions and Necklaces

T(n,k) = (Sum_{d | gcd(n,k)} phi(d)*binomial((n+k)/d, n/d))/(n+k). [Corrected by N. J. A. Sloane, May 03 2014]

The table starts:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, ...

1, 2, 4, 5, 7, 10, 12, 15, 19, 22, 26, 31, ...

1, 3, 5, 10, 14, 22, 30, 43, 55, 73, 91, 116, ...

1, 3, 7, 14, 26, 42, 66, 99, 143, 201, 273, 364, ...

1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038, ...

...

# Maple program for the table - N. J. A. Sloane, May 03 2014:

with(numtheory);

T:=proc(n, k) local d, s, g, t0;

t0:=0; s:=n+k; g:=gcd(n, k);

for d from 1 to s do

if (g mod d) = 0 then t0:=t0+phi(d)*binomial(s/d, k/d); fi;

od: t0/s; end;

r:=n->[seq(T(n, k), k=1..12)];

[seq(r(n), n=1..12)];

T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#] Binomial[(n+k)/#, n/#]& ]/ (n+k); Table[T[n-k+1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 02 2015 *)

(PARI) T(n, k) = sumdiv(gcd(n, k), d, eulerphi(d)*binomial((n+k)\d, n\d))/(n+k)

Same as A047996 with first row and main diagonal removed.

A037306 is yet another version.

Cf. A003239 (main diagonal).

See A245558, A245559 for a closely related array.

Sequence in context: A275298 A048570 A090806 * A174446 A071201 A318045

Adjacent sequences: A241923 A241924 A241925 * A241927 A241928 A241929

nonn,tabl

Franklin T. Adams-Watters, May 02 2014

Edited by N. J. A. Sloane, May 03 2014

Elashvili et al. references supplied by Vladimir Popov, May 17 2014

approved