login
A283615
Irregular triangle read by rows: T(n,k) is the number of necklaces of n 1's, n -1's, and k 0's such that no two adjacent elements are equal.
1
1, 1, 2, 1, 1, 2, 5, 4, 2, 1, 2, 7, 16, 18, 12, 4, 1, 2, 11, 32, 70, 92, 82, 40, 10, 1, 2, 13, 56, 166, 348, 510, 520, 350, 140, 26, 1, 2, 17, 88, 336, 932, 1948, 2992, 3404, 2756, 1518, 504, 80, 1, 2, 19, 124, 584, 2056, 5524, 11444, 18298, 22428, 20706, 13944, 6468, 1848, 246, 1, 2, 23, 168, 944, 3976, 13120, 34064, 70380, 115516
OFFSET
0,3
COMMENTS
T(n,k) is the number of unique circular arrays (A283614) given equivalence under rotation.
FORMULA
T(n,k) = Sum_{d|gcd(n,k)} phi(d) * A283614(n/d,k/d) / (2*n+k) where phi is Euler's totient function (A000010).
T(n,2*n) = A003239(n).
T(n,2*n-1) = 2*binomial(2*(n-1), n-1).
T(n,n) = A110710(n).
EXAMPLE
Table for n=[0..6], k=[0..12]
0 1 2 3 4 5 6 7 8 9 10 11 12
-----------------------------------------------------------------------------
0 | 1
1 | 1 2 1
2 | 1 2 5 4 2
3 | 1 2 7 16 18 12 4
4 | 1 2 11 32 70 92 82 40 10
5 | 1 2 13 56 166 348 510 520 350 140 26
6 | 1 2 17 88 336 932 1948 2992 3404 2756 1518 504 80
The 13 necklaces for n=5, k=2 are:
[+-+-+-+-0+0-],[+-+-+-+0+-0-],[+-+-+-+0-+0-],[+-+-+-0+-+0-]
[+-+-+0+-+-0-],[+-+-+0-+-+0-],[+-+-+-+-+0-0],[+-+-+-+-0+-0]
[+-+-+-+-0-+0],[+-+-+-+0-+-0],[+-+-+-0+-+-0],[+-+-+-0-+-+0]
[+-+-+0-+-+-0].
PROG
(Maxima)
g(x, y):=2*(x*y+1)/sqrt((1-y)*(1-(2*x+1)^2*y))-1;
A283614(n, k):=coeff(limit(diff(g(x, y), y, n)/n!, y, 0), x, k);
A283615(n, k):=block([s, d],
s:0,
for d in divisors(gcd(n, k)) do
s:s+totient(d)*A283614(n/d, k/d),
return(s/(2*n+k)));
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Stefan Hollos, Apr 11 2017
STATUS
approved