A208776 -id:A208776 - cp's OEIS frontend

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

R. H. Hardin, Mar 01 2012

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]

			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

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.

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

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

/* 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 */

A215338 Cyclically smooth Lyndon words with 7 colors.

Original entry on oeis.org

7, 6, 12, 23, 56, 118, 292, 683, 1692, 4180, 10604, 26978, 69720, 181162, 475072, 1252756, 3324096, 8861054, 23729740, 63786792, 172066648, 465566598, 1263208676, 3435891568, 9366558088, 25585826404, 70019830220, 191943097314, 526978629656, 1448862393216, 3988658225028, 10993822451304, 30335737458872, 83793421017568

Offset: 1

Joerg Arndt, Aug 13 2012

nonn

We call a Lyndon word (x[1],x[2],...,x[n]) smooth if abs(x[k]-x[k-1]) <= 1 for 2<=k<=n, and cyclically smooth if abs(x[1]-x[n]) <= 1.

			The cyclically smooth necklaces (N) and Lyndon words (L) of length 4 with 7 colors (using symbols ".", "1", "2", "3", "4", "5", and "6") are:
    ....   1       .  N
    ...1   4    ...1  N L
    ..11   4    ..11  N L
    .1.1   2      .1  N
    .111   4    .111  N L
    .121   4    .121  N L
    1111   1       1  N
    1112   4    1112  N L
    1122   4    1122  N L
    1212   2      12  N
    1222   4    1222  N L
    1232   4    1232  N L
    2222   1       2  N
    2223   4    2223  N L
    2233   4    2233  N L
    2323   2      23  N
    2333   4    2333  N L
    2343   4    2343  N L
    3333   1       3  N
    3334   4    3334  N L
    3344   4    3344  N L
    3434   2      34  N
    3444   4    3444  N L
    3454   4    3454  N L
    4444   1       4  N
    4445   4    4445  N L
    4455   4    4455  N L
    4545   2      45  N
    4555   4    4555  N L
    4565   4    4565  N L
    5555   1       5  N
    5556   4    5556  N L
    5566   4    5566  N L
    5656   2      56  N
    5666   4    5666  N L
    6666   1       6  N
There are 36 necklaces (so A208776(4)=36) and a(4)=23 Lyndon words.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Cf. A208776 (cyclically smooth necklaces, 7 colors).

Cf. A215333 (smooth necklaces, 7 colors), A215334 (smooth Lyndon words, 7 colors).

terms = 40;
sn[n_, k_] := 1/n Sum[EulerPhi[j] (1+2Cos[i Pi/(k+1)])^(n/j), {i, 1, k}, {j, Divisors[n]}];
vn = Table[Round[sn[n, 7]], {n, terms}];
vl = Table[Sum[MoebiusMu[n/d] vn[[d]], {d, Divisors[n]}], {n, terms}] (* Jean-François Alcover, Jul 22 2018, after Joerg Arndt *)

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)));
vn=vector(66,n, round(sn(n,7)) ); /* necklaces */
/* Lyndon words, via Moebius inversion: */
vl=vector(#vn,n, sumdiv(n,d, moebius(n/d)*vn[d]))

a(n) = sum_{ d divides n } moebius(n/d) * A208776(d).

A208720 Number of n-bead necklaces labeled with numbers 1..7 allowing reversal, with no adjacent beads differing by more than 1.

Original entry on oeis.org

7, 13, 19, 36, 58, 122, 224, 502, 1066, 2528, 5902, 14717, 36557, 93987, 242387, 635990, 1675743, 4457771, 11903835, 31970464, 86144382, 233001926, 631920076, 1718567054, 4684178054, 12794677456, 35012475762, 95976563897, 263496604025, 724445459431

Offset: 1

R. H. Hardin, Mar 01 2012

nonn

			All solutions for n=3:
..1....1....6....3....6....5....2....4....4....3....5....4....5....7....6....2
..2....1....6....4....7....5....3....4....5....3....6....4....5....7....6....2
..2....1....7....4....7....5....3....5....5....3....6....4....6....7....6....3
..
..1....2....3
..1....2....3
..2....2....4

Andrew Howroyd, Table of n, a(n) for n = 1..100

Column 7 of A208721.

Cf. A208776, A002714.

a(2n+1) = (1/2) * (A208776(2n+1) + A002714(n+1)). - Andrew Howroyd, Mar 03 2017

a(2n) = (1/2) * A208776(2n) + (1/4) * (A002714(n) + A002714(n+1)). - Andrew Howroyd, Mar 03 2017

a(22)-a(30) from Andrew Howroyd, Mar 03 2017

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A215338 Cyclically smooth Lyndon words with 7 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A208720 Number of n-bead necklaces labeled with numbers 1..7 allowing reversal, with no adjacent beads differing by more than 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions