A208777 T(n,k) is the number of n-bead necklaces labeled with numbers 1..k not allowing reversal, with no adjacent beads differing by more than 1.

1, 2, 1, 3, 3, 1, 4, 5, 4, 1, 5, 7, 7, 6, 1, 6, 9, 10, 12, 8, 1, 7, 11, 13, 18, 19, 14, 1, 8, 13, 16, 24, 30, 39, 20, 1, 9, 15, 19, 30, 41, 65, 71, 36, 1, 10, 17, 22, 36, 52, 91, 128, 152, 60, 1, 11, 19, 25, 42, 63, 117, 185, 293, 315, 108, 1, 12, 21, 28, 48, 74, 143, 242, 435, 658, 685

Offset

1,2

Comments

Table starts

.1..2...3...4...5...6...7...8....9...10...11...12...13...14...15...16...17...18

.1..3...5...7...9..11..13..15...17...19...21...23...25...27...29...31...33...35

.1..4...7..10..13..16..19..22...25...28...31...34...37...40...43...46...49...52

.1..6..12..18..24..30..36..42...48...54...60...66...72...78...84...90...96..102

.1..8..19..30..41..52..63..74...85...96..107..118..129..140..151..162..173..184

.1.14..39..65..91.117.143.169..195..221..247..273..299..325..351..377..403..429

.1.20..71.128.185.242.299.356..413..470..527..584..641..698..755..812..869..926

.1.36.152.293.435.577.719.861.1003.1145.1287.1429.1571.1713.1855.1997.2139.2281

The transposed array (starting with index 0) appears as Table 2 in the Knopfmacher et al. reference. [Joerg Arndt, Aug 08 2012]

Links

R. H. Hardin, Table of n, a(n) for n = 1..456

Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Example

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

Mathematica

T[n_, k_] := 1/n*Sum[DivisorSum[n, EulerPhi[#]*(1+2*Cos[i*Pi/(k+1)])^(n/#)&], {i, 1, k}] // FullSimplify; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Dec 05 2015, adapted from PARI *)

Prog

(PARI)
/* from the Knopfmacher et al. reference */
default(realprecision, 99); /* using floats */
sn(n, k)=1/n*sum(i=1, k, sumdiv(n, j, eulerphi(j)*(1+2*cos(i*Pi/(k+1)))^(n/j)));
T(n, k)=sn(n, k);
matrix(22, 22, n, k, round(T(n, k)) ) /* as matrix shown in comments */
/* Joerg Arndt, Aug 09 2012 */

Crossrefs

Column 2 is A000031, col. 3 is A208772, col. 4 is A208773, col. 5 is A208774, col. 6 is A208775, col. 7 is A208776.

Sequence in context: A278492 A128139 A208721 * A104732 A132108 A377000

Adjacent sequences: A208774 A208775 A208776 * A208778 A208779 A208780

Keyword

nonn,tabl

Author

R. H. Hardin, Mar 01 2012

Status

approved