A208544 T(n,k) = Number of n-bead necklaces of k colors allowing reversal, with no adjacent beads having the same color.

1, 2, 0, 3, 1, 0, 4, 3, 0, 0, 5, 6, 1, 1, 0, 6, 10, 4, 6, 0, 0, 7, 15, 10, 21, 3, 1, 0, 8, 21, 20, 55, 24, 13, 0, 0, 9, 28, 35, 120, 102, 92, 9, 1, 0, 10, 36, 56, 231, 312, 430, 156, 30, 0, 0, 11, 45, 84, 406, 777, 1505, 1170, 498, 29, 1, 0, 12, 55, 120, 666, 1680, 4291, 5580, 4435

Offset

1,2

Comments

Table starts

.1.2..3...4....5.....6......7......8.......9......10......11.......12.......13

.0.1..3...6...10....15.....21.....28......36......45......55.......66.......78

.0.0..1...4...10....20.....35.....56......84.....120.....165......220......286

.0.1..6..21...55...120....231....406.....666....1035....1540.....2211.....3081

.0.0..3..24..102...312....777...1680....3276....5904....9999....16104....24882

.0.1.13..92..430..1505...4291..10528...23052...46185...86185...151756...254618

.0.0..9.156.1170..5580..19995..58824..149796..341640..714285..1391940..2559414

.0.1.30.498.4435.25395.107331.365260.1058058.2707245.6278140.13442286.26942565

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 264 terms from R. H. Hardin)

Formula

T(2n+1,k) = A208535(2n+1,k)/2 for n > 0, T(2n,k) = (A208535(2n,k) + (k*(k-1)^n)/2)/2. - Andrew Howroyd, Mar 12 2017

Empirical for row n:

n=1: a(k) = k

n=2: a(k) = (1/2)*k^2 - (1/2)*k

n=3: a(k) = (1/6)*k^3 - (1/2)*k^2 + (1/3)*k

n=4: a(k) = (1/8)*k^4 - (1/4)*k^3 + (3/8)*k^2 - (1/4)*k

n=5: a(k) = (1/10)*k^5 - (1/2)*k^4 + k^3 - k^2 + (2/5)*k

n=6: a(k) = (1/12)*k^6 - (1/2)*k^5 + (3/2)*k^4 - (7/3)*k^3 + (23/12)*k^2 - (2/3)*k

n=7: a(k) = (1/14)*k^7 - (1/2)*k^6 + (3/2)*k^5 - (5/2)*k^4 + (5/2)*k^3 - (3/2)*k^2 + (3/7)*k

Example

All solutions for n=7, k=3:
..1....1....1....1....1....1....1....1....1
..2....2....2....2....2....2....2....2....2
..3....3....1....1....3....1....3....1....3
..1....1....2....2....1....2....2....3....2
..2....3....3....3....3....1....3....1....3
..3....1....1....2....2....2....2....2....1
..2....3....3....3....3....3....3....3....3

Mathematica

T[n_, k_] := If[n == 1, k, (DivisorSum[n, EulerPhi[n/#]*(k-1)^#&]/n + If[ OddQ[n], 1-k, k*(k-1)^(n/2)/2])/2]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 30 2017, after Andrew Howroyd *)

Prog

(PARI)
T(n, k) = if(n==1, k, (sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n + if(n%2, 1-k, k*(k-1)^(n/2)/2))/2);
for(n=1, 10, for(k=1, 10, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 14 2017

Crossrefs

Cf. A081720, A208535, A106512.

Main diagonal is A208538.

Columns 3..7 are A208539, A208540, A208541, A208542, A208543.

Row 2 is A000217(n-1).

Row 3 is A000292(n-2).

Row 4 is A002817(n-1).

Row 5 is A164938(n-1).

Row 6 is A027670(n-1).

Sequence in context: A144257 A257232 A321980 * A208535 A284856 A276550

Adjacent sequences: A208541 A208542 A208543 * A208545 A208546 A208547

Keyword

nonn,tabl

Author

R. H. Hardin, Feb 27 2012

Status

approved