

A241926


Table read by antidiagonals: T(n,k) (n >= 1, k >= 1) is the number of necklaces with n black beads and k white beads.


3



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, 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, 66, 80, 66, 43, 19, 6, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

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


LINKS

Table of n, a(n) for n=1..78.
Paul Drube and Puttipong Pongtanapaisan, Annular NonCrossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Elashvili, M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze, D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173188. MR1719140 (2000j:05009). See p. 174.  N. J. A. Sloane, Aug 06 2014
N. J. A. Sloane, A Note on Modular Partitions and Necklaces


FORMULA

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]


EXAMPLE

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

# 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)];


MATHEMATICA

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


PROG

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


CROSSREFS

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 A240656
Adjacent sequences: A241923 A241924 A241925 * A241927 A241928 A241929


KEYWORD

nonn,tabl


AUTHOR

Franklin T. AdamsWatters, May 02 2014


EXTENSIONS

Edited by N. J. A. Sloane, May 03 2014
Elashvili et al. references supplied by Vladimir Popov, May 17 2014


STATUS

approved



