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, 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

Author

Stefan Hollos, Apr 11 2017

Keywords

• nonn
• tabf

Comments

T(n,k) is the number of unique circular arrays (A283614) given equivalence under rotation.

Examples

			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].
		

Crossrefs

Cf. A000010, A003239, A110710, A283614.

Programs

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

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).