

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.


14



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
T(n, k) is the number of equivalence classes of ktuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation.  Álvar Ibeas, Sep 21 2021


LINKS



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

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.


KEYWORD



AUTHOR



EXTENSIONS

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


STATUS

approved



