A208544 -id:A208544 - cp's OEIS frontend

A330341 Triangle read by rows: T(n,k) is the number of n-bead bracelets using exactly k colors with no adjacent beads having the same color.

0, 0, 1, 0, 0, 1, 0, 1, 3, 3, 0, 0, 3, 12, 12, 0, 1, 10, 46, 90, 60, 0, 0, 9, 120, 480, 720, 360, 0, 1, 27, 384, 2235, 5670, 6300, 2520, 0, 0, 29, 980, 9380, 36960, 68880, 60480, 20160, 0, 1, 75, 2904, 38484, 217152, 604800, 876960, 635040, 181440

Offset: 1

Andrew Howroyd, Dec 20 2019

In the case of n = 1, the single bead is considered to be cyclically adjacent to itself giving T(1,1) = 0. If compatibility with A208544 is wanted then T(1,1) should be 1.

			Triangle begins:
  0;
  0, 1;
  0, 0,  1;
  0, 1,  3,   3;
  0, 0,  3,  12,   12;
  0, 1, 10,  46,   90,    60;
  0, 0,  9, 120,  480,   720,   360;
  0, 1, 27, 384, 2235,  5670,  6300,  2520;
  0, 0, 29, 980, 9380, 36960, 68880, 60480, 20160;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Column 3 is A330632.
Row sums are A330621.
Cf. A208544, A273891, A330618.

\\ here U(n, k) is A208544(n, k) for n > 1.
U(n, k) = (sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n + if(n%2, 1-k, k*(k-1)^(n/2)/2))/2;
T(n, k)={sum(j=1, k, (-1)^(k-j)*binomial(k, j)*U(n, j))}

T(n,k) = Sum_{j=1..k} (-1)^(k-j)*binomial(k,j)*A208544(n,j) for n > 1.

A208539 Number of n-bead necklaces of 3 colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

3, 3, 1, 6, 3, 13, 9, 30, 29, 78, 93, 224, 315, 687, 1095, 2250, 3855, 7685, 13797, 27012, 49939, 96909, 182361, 352698, 671091, 1296858, 2485533, 4806078, 9256395, 17920860, 34636833, 67159050, 130150587, 252745368

Offset: 1

R. H. Hardin, Feb 27 2012

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 1..100
Marko Riedel et al., math.stackexchange, Proper colorings of necklaces
Marko Riedel et al., math.stackexchange, Proper colorings of bracelets

Column 3 of A208544.

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]; a[n_] = T[n, 3]; Array[a, 34] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

a(2*n+1) = A106365(2*n+1)/2 for n > 0, a(2*n) = (A106365(2*n) + 3*2^(n-1))/2. - Andrew Howroyd, Mar 12 2017

A208538 Number of n-bead necklaces of n colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

1, 1, 1, 21, 102, 1505, 19995, 365260, 7456596, 174489813, 4545454545, 130773238871, 4115123283810, 140620807064413, 5185603185296625, 205262771447683860, 8680820740569200760, 390641235316599920745, 18637772246193096746253, 939749336469457562916217

Offset: 1

R. H. Hardin, Feb 27 2012

nonn

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

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

Diagonal of A208544.

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]; a[n_] = T[n, n]; Array[a, 20] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

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

a(12)-a(20) from Andrew Howroyd, Mar 12 2017

A208540 Number of n-bead necklaces of 4 colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

4, 6, 4, 21, 24, 92, 156, 498, 1096, 3210, 8052, 22913, 61320, 173088, 478316, 1351983, 3798240, 10781954, 30585828, 87230157, 249056136, 713387076, 2046590844, 5884491500, 16945772208, 48883660146, 141214768972

Offset: 1

R. H. Hardin, Feb 27 2012

nonn

			All solutions for n=3
..1....1....2....1
..2....2....3....3
..3....4....4....4

Andrew Howroyd, Table of n, a(n) for n = 1..100
Marko Riedel et al., math.stackexchange, Proper colorings of necklaces
Marko Riedel et al., math.stackexchange, Proper colorings of bracelets

Column 4 of A208544.

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]; a[n_] = T[n, 4]; Array[a, 27] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

a(2*n+1) = A106366(2*n+1)/2 for n > 0, a(2*n) = (A106366(2*n) + 2*3^n)/2. - Andrew Howroyd, Mar 12 2017

A208541 Number of n-bead necklaces of 5 colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

5, 10, 10, 55, 102, 430, 1170, 4435, 14570, 53764, 190650, 704370, 2581110, 9608050, 35791470, 134301715, 505290270, 1909209550, 7233629130, 27489127708, 104715393910, 399827748310, 1529755308210, 5864083338770, 22517998136934, 86607770318380

Offset: 1

R. H. Hardin, Feb 27 2012

nonn

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

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

Column 5 of A208544.

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]; a[n_] = T[n, 5]; Array[a, 26] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

a(2n+1) = A106367(2n+1)/2 for n > 0, a(2n) = (A106367(2n) + 5*4^n/2)/2. - Andrew Howroyd, Mar 12 2017

a(21)-a(26) from Andrew Howroyd, Mar 12 2017

A208542 Number of n-bead necklaces of 6 colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

6, 15, 20, 120, 312, 1505, 5580, 25395, 108520, 493131, 2219460, 10196680, 46950120, 218102685, 1017252828, 4768969770, 22439395680, 105966797755, 501933850740, 2384200683816, 11353265675240, 54186115056825, 259150629458220, 1241763804134805

Offset: 1

R. H. Hardin, Feb 27 2012

nonn

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

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

Column 6 of A208544.

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]; a[n_] = T[n, 6]; Array[a, 24] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

a(2n+1) = A106368(2n+1)/2 for n > 0, a(2n) = (A106368(2n) + 3*5^n)/2. - Andrew Howroyd, Mar 12 2017

a(19)-a(24) from Andrew Howroyd, Mar 12 2017

A208543 Number of n-bead necklaces of 7 colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

7, 21, 35, 231, 777, 4291, 19995, 107331, 559895, 3037314, 16490775, 90782986, 502334385, 2799220041, 15672833365, 88162676511, 497842924845, 2821127825971, 16035782631855, 91404068329560, 522308348593785, 2991403003191771, 17168048327252235, 98716281736491076

Offset: 1

R. H. Hardin, Feb 27 2012

nonn

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

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

Column 7 of A208544.

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]; a[n_] = T[n, 7]; Array[a, 24] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

a(18)-a(24) from Andrew Howroyd, Mar 12 2017

A330621 Number of length n bracelets with entries covering an initial interval of positive integers and no adjacent entries equal.

Original entry on oeis.org

0, 1, 1, 7, 27, 207, 1689, 17137, 196869, 2556856, 36878013, 585247590, 10131891315, 190024056601, 3838053182983, 83057105368627, 1917217162193175, 47021314781221603, 1221073517359584357, 33471097453271690668, 965771726172667547339, 29259595679585441629303

Offset: 1

Andrew Howroyd, Dec 20 2019

nonn

			Case n=4: there are the following 7 bracelets:
  1212,
  1213, 1232, 1323,
  1234, 1243, 1324.

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

Row sums of A330341.

Cf. A208544.

\\ here U(n, k) is A208544(n, k) for n > 1.
U(n, k) = (sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n + if(n%2, 1-k, k*(k-1)^(n/2)/2))/2;
a(n)={if(n<1, n==0, sum(j=1, n, U(n,j)*sum(k=j, n, (-1)^(k-j)*binomial(k, j))))}

A208545 Number of 7-bead necklaces of n colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 9, 156, 1170, 5580, 19995, 58824, 149796, 341640, 714285, 1391940, 2559414, 4482036, 7529535, 12204240, 19173960, 29309904, 43730001, 63847980, 91428570, 128649180, 178168419, 243201816, 327605100, 435965400, 573700725, 747168084

Offset: 1

R. H. Hardin, Feb 27 2012

Row 7 of A208544.

			All solutions for n=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

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1).

Cf. A208537.

Vec(3*x^3*(3 + 28*x + 58*x^2 + 28*x^3 + 3*x^4) / (1 - x)^8 + O(x^40)) \\ Colin Barker, Nov 11 2017

Empirical: a(n) = (1/14)*n^7 - (1/2)*n^6 + (3/2)*n^5 - (5/2)*n^4 + (5/2)*n^3 - (3/2)*n^2 + (3/7)*n.
From Colin Barker, Nov 11 2017: (Start)
G.f.: 3*x^3*(3 + 28*x + 58*x^2 + 28*x^3 + 3*x^4) / (1 - x)^8.
a(n) = 8*a(n-1) - 28*a(n-2) + 56*a(n-3) - 70*a(n-4) + 56*a(n-5) - 28*a(n-6) + 8*a(n-7) - a(n-8) for n>8.
(End)

cp's OEIS Frontend

A330341 Triangle read by rows: T(n,k) is the number of n-bead bracelets using exactly k colors with no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A208539 Number of n-bead necklaces of 3 colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A208538 Number of n-bead necklaces of n colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A208540 Number of n-bead necklaces of 4 colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A208541 Number of n-bead necklaces of 5 colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A208542 Number of n-bead necklaces of 6 colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A208543 Number of n-bead necklaces of 7 colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A330621 Number of length n bracelets with entries covering an initial interval of positive integers and no adjacent entries equal.

Views

Author

Keywords

Examples