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

Comments

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

Links

Table of n, a(n) for n=0..73.

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

Cf. A000010, A003239, A110710, A283614.

Sequence in context: A029937 A368926 A289772 * A172483 A216396 A273488

Adjacent sequences: A283612 A283613 A283614 * A283616 A283617 A283618

Keyword

nonn,tabf

Author

Stefan Hollos, Apr 11 2017

Status

approved