|
|
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 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
|
|
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[n-k+1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-Franç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
|
|
|
|