Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #51 Nov 09 2024 02:36:29
%S 1,1,1,1,2,1,1,2,2,1,1,3,4,3,1,1,3,5,5,3,1,1,4,7,10,7,4,1,1,4,10,14,
%T 14,10,4,1,1,5,12,22,26,22,12,5,1,1,5,15,30,42,42,30,15,5,1,1,6,19,43,
%U 66,80,66,43,19,6,1,1,6,22,55,99,132,132,99,55,22,6,1
%N Table read by antidiagonals: T(n,k) (n >= 1, k >= 1) is the number of necklaces with n black beads and k white beads.
%C 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
%C 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
%H G. C. Greubel, <a href="/A241926/b241926.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%H Paul Drube and Puttipong Pongtanapaisan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Drube/drube3.html">Annular Non-Crossing Matchings</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
%H A. Elashvili and M. Jibladze, <a href="http://dx.doi.org/10.1016/S0019-3577(98)80021-9">Hermite reciprocity for the regular representations of cyclic groups</a>, Indag. Math. (N.S.) 9 (1998), no. 2, 233--238. MR1691428 (2000c:13006)
%H A. Elashvili, M. Jibladze and D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
%H N. J. A. Sloane, <a href="/A047996/a047996.pdf">A Note on Modular Partitions and Necklaces</a>
%F 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]
%e The table starts:
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, ...
%e 1, 2, 4, 5, 7, 10, 12, 15, 19, 22, 26, 31, ...
%e 1, 3, 5, 10, 14, 22, 30, 43, 55, 73, 91, 116, ...
%e 1, 3, 7, 14, 26, 42, 66, 99, 143, 201, 273, 364, ...
%e 1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038, ...
%e ...
%p # Maple program for the table - _N. J. A. Sloane_, May 03 2014:
%p with(numtheory);
%p T:=proc(n,k) local d, s, g, t0;
%p t0:=0; s:=n+k; g:=gcd(n,k);
%p for d from 1 to s do
%p if (g mod d) = 0 then t0:=t0+phi(d)*binomial(s/d,k/d); fi;
%p od: t0/s; end;
%p r:=n->[seq(T(n,k),k=1..12)];
%p [seq(r(n),n=1..12)];
%t 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 *)
%o (PARI) T(n,k) = sumdiv(gcd(n,k),d,eulerphi(d)*binomial((n+k)\d,n\d))/(n+k)
%Y Same as A047996 with first row and main diagonal removed.
%Y A037306 is yet another version.
%Y Cf. A003239 (main diagonal).
%Y See A245558, A245559 for a closely related array.
%K nonn,tabl
%O 1,5
%A _Franklin T. Adams-Watters_, May 02 2014
%E Edited by _N. J. A. Sloane_, May 03 2014
%E Elashvili et al. references supplied by Vladimir Popov, May 17 2014