A027670 -id:A027670 - cp's OEIS frontend

A081720 Triangle T(n,k) read by rows, giving number of bracelets (turnover necklaces) with n beads of k colors (n >= 1, 1 <= k <= n).

1, 1, 3, 1, 4, 10, 1, 6, 21, 55, 1, 8, 39, 136, 377, 1, 13, 92, 430, 1505, 4291, 1, 18, 198, 1300, 5895, 20646, 60028, 1, 30, 498, 4435, 25395, 107331, 365260, 1058058, 1, 46, 1219, 15084, 110085, 563786, 2250311, 7472984, 21552969, 1, 78, 3210, 53764, 493131, 3037314

Offset: 1

N. J. A. Sloane, based on information supplied by Gary W. Adamson, Apr 05 2003

From Petros Hadjicostas, Nov 29 2017: (Start)
The formula given below is clear from the programs given in the Maple and Mathematica sections, while the g.f. for column k can be obtained using standard techniques.
If we differentiate the column k g.f. m times, then we can get a formula for row m. (For this sequence, we only need to use this row m formula for 1 <= k <= m, but it is valid even for k>m.) For example, to get the formula for row 8, we have T(n=8,k) = d^8/dx^8 (column k g.f.)/8! evaluated at x=0. Here, "d^8/dx^8" means "8th derivative w.r.t. x" of the column k g.f. Doing so, we get T(n=8, k) = (k^6 - k^5 + k^4 + 3*k^3 + 2*k^2 - 2*k + 4)*(k + 1)*k/16, which is the formula given for sequence A060560. (Here, we use this formula only for 1 <= k <= 8.)
(End)

			1;                                                (A000027)
1,  3;                                            (A000217)
1,  4,  10;                                       (A000292)
1,  6,  21,   55;                                 (A002817)
1,  8,  39,  136,   377;                          (A060446)
1, 13,  92,  430,  1505,   4291;                  (A027670)
1, 18, 198, 1300,  5895,  20646,  60028;          (A060532)
1, 30, 498, 4435, 25395, 107331, 365260, 1058058; (A060560)
...
For example, when n=k=3, we have the following T(3,3)=10 bracelets of 3 beads using up to 3 colors: 000, 001, 002, 011, 012, 022, 111, 112, 122, and 222. (Note that 012 = 120 = 201 = 210 = 102 = 021.) _Petros Hadjicostas_, Nov 29 2017

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Yi Hu, Numerical Transfer Matrix Method of Next-nearest-neighbor Ising Models, Master's Thesis, Duke Univ. (2021).
Yi Hu and Patrick Charbonneau, Numerical transfer matrix study of frustrated next-nearest-neighbor Ising models on square lattices, arXiv:2106.08442 [cond-mat.stat-mech], 2021, cites the 4th column.

Cf. A321791 (extension to n >= 0, k >= 0).

Cf. A081721 (diagonal), A081722 (row sums), column sequences k=2..6: A000029, A027671, A032275, A032276, A056341.

A081720 := proc(n, k)
    local d, t1;
    t1 := 0;
    if n mod 2 = 0 then
        for d from 1 to n do
            if n mod d = 0 then
                t1 := t1+numtheory[phi](d)*k^(n/d);
            end if;
        end do:
        (t1+(n/2)*(1+k)*k^(n/2)) /(2*n) ;
    else
        for d from 1 to n do
            if n mod d = 0 then
                t1 := t1+numtheory[phi](d)*k^(n/d);
            end if;
        end do;
        (t1+n*k^((n+1)/2)) /(2*n) ;
    end if;
end proc:
seq(seq(A081720(n,k),k=1..n),n=1..10) ;

t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n + 1)/2))/(2*n)]); Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 13 2012, after Maple, updated Nov 02 2017 *)
Needs["Combinatorica`"]; Table[Table[NumberOfNecklaces[n,k,Dihedral],{k,1,n}],{n,1,8}]//Grid  (* Geoffrey Critzer, Oct 07 2012, after code by T. D. Noe in A027671 *)

See Maple code.
From Petros Hadjicostas, Nov 29 2017: (Start)
T(n,k) = ((1+k)*k^{n/2}/2 + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is even, and = (k^{(n+1)/2} + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is odd.
G.f. for column k: (1/2)*((k*x+k*(k+1)*x^2/2)/(1-k*x^2) - Sum_{n>=1} (phi(n)/n)*log(1-k*x^n)) provided we chop off the Taylor expansion starting at x^k (and ignore all the terms x^n with n(End)
2*n*T(n,k) = A054618(n,k)+n*(1+k)^(n/2)/2 if n even, = A054618(n,k)+n*k^((n+1)/2) if n odd. - R. J. Mathar, Jan 23 2022

Name edited by Petros Hadjicostas, Nov 29 2017

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

Original entry on oeis.org

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

R. H. Hardin, Feb 27 2012

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

			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

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

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

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

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

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

A006565 Number of ways to color vertices of a hexagon using <= n colors, allowing only rotations.

Original entry on oeis.org

0, 1, 14, 130, 700, 2635, 7826, 19684, 43800, 88725, 166870, 295526, 498004, 804895, 1255450, 1899080, 2796976, 4023849, 5669790, 7842250, 10668140, 14296051, 18898594, 24674860, 31853000, 40692925, 51489126, 64573614

Offset: 0

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Victor Meally, Letter to N. J. A. Sloane, no date.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A027670, A075195.

A006565 := n-> (n^6+n^3+2*n^2+2*n)/6.
A006565:=-(1+7*z+53*z**2+49*z**3+10*z**4)/(z-1)**7; [Conjectured by Simon Plouffe in his 1992 dissertation.]

n*(n+1)*(n^2+n+1)*(n^2-2*n+2)/6.

A051137 Table T(n,k) read by antidiagonals: number of necklaces allowing turnovers (bracelets) with n beads of k colors.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 6, 10, 10, 5, 1, 1, 8, 21, 20, 15, 6, 1, 1, 13, 39, 55, 35, 21, 7, 1, 1, 18, 92, 136, 120, 56, 28, 8, 1, 1, 30, 198, 430, 377, 231, 84, 36, 9, 1, 1, 46, 498, 1300, 1505, 888, 406, 120, 45, 10, 1

Offset: 0

Alford Arnold

Unlike A075195 and A284855, antidiagonals go from bottom-left to top-right.

			Table begins with T[0,1]:
1  1    1     1      1       1        1        1         1         1
1  2    3     4      5       6        7        8         9        10
1  3    6    10     15      21       28       36        45        55
1  4   10    20     35      56       84      120       165       220
1  6   21    55    120     231      406      666      1035      1540
1  8   39   136    377     888     1855     3536      6273     10504
1 13   92   430   1505    4291    10528    23052     46185     86185
1 18  198  1300   5895   20646    60028   151848    344925    719290
1 30  498  4435  25395  107331   365260  1058058   2707245   6278140
1 46 1219 15084 110085  563786  2250311  7472984  21552969  55605670
1 78 3210 53764 493131 3037314 14158228 53762472 174489813 500280022

C. G. Bower, Transforms (2)

Columns 2-6 are A000029, A027671, A032275, A032276, and A056341.
Rows 2-7 are A000217, A000292, A002817, A060446, A027670, and A060532.
Cf. A000031.
Cf. A081720, A081721.
T(n,k) = (A075195(n,k) + A284855(n,k)) / 2.

b[n_, k_] := DivisorSum[n, EulerPhi[#]*k^(n/#) &] / n;
c[n_, k_] := If[EvenQ[n], (k^(n/2) + k^(n/2+1))/2, k^((n+1)/2)];
T[0, ] = 1; T[n, k_] := (b[n, k] + c[n, k])/2;
Table[T[n, k-n], {k, 1, 11}, {n, k-1, 0, -1}] // Flatten
(* Robert A. Russell, Sep 21 2018 after Jean-François Alcover *)

T(n, k) = (k^floor((n+1)/2) + k^ceiling((n+1)/2)) / 4 + (1/(2*n)) * Sum_{d divides n} phi(d) * k^(n/d). - Robert A. Russell, Sep 21 2018
G.f. for column k: (kx/4)*(kx+x+2)/(1-kx^2) - Sum_{d>0} phi(d)*log(1-kx^d)/2d. - Robert A. Russell, Sep 28 2018
T(n, k) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i). (See A075195 formulas.) - Richard L. Ollerton, May 04 2021

A321791 Table read by descending antidiagonals: T(n,k) is the number of unoriented cycles (bracelets) of length n using up to k available colors.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 6, 1, 0, 1, 6, 15, 20, 21, 8, 1, 0, 1, 7, 21, 35, 55, 39, 13, 1, 0, 1, 8, 28, 56, 120, 136, 92, 18, 1, 0, 1, 9, 36, 84, 231, 377, 430, 198, 30, 1, 0

Offset: 0

Robert A. Russell, Dec 18 2018

			Table begins with T(0,0):
  1 1  1    1     1      1       1        1        1         1         1 ...
  0 1  2    3     4      5       6        7        8         9        10 ...
  0 1  3    6    10     15      21       28       36        45        55 ...
  0 1  4   10    20     35      56       84      120       165       220 ...
  0 1  6   21    55    120     231      406      666      1035      1540 ...
  0 1  8   39   136    377     888     1855     3536      6273     10504 ...
  0 1 13   92   430   1505    4291    10528    23052     46185     86185 ...
  0 1 18  198  1300   5895   20646    60028   151848    344925    719290 ...
  0 1 30  498  4435  25395  107331   365260  1058058   2707245   6278140 ...
  0 1 46 1219 15084 110085  563786  2250311  7472984  21552969  55605670 ...
  0 1 78 3210 53764 493131 3037314 14158228 53762472 174489813 500280022 ...
For T(3,3)=10, the unoriented cycles are 9 achiral (AAA, AAB, AAC, ABB, ACC, BBB, BBC, BCC, CCC) and 1 chiral pair (ABC-ACB).

Index entries for sequences related to bracelets

Cf. A075195 (oriented), A293496(chiral), A284855 (achiral).
Cf. A051137 (ascending antidiagonals).
Columns 0-6 are A000007, A000012, A000029, A027671, A032275, A032276, and A056341.
Rows 0-7 are A000012, A001477, A000217, A000292, A002817, A060446, A027670, and A060532.
Main diagonal gives A081721.

Table[If[k>0, DivisorSum[k, EulerPhi[#](n-k)^(k/#)&]/(2k) + ((n-k)^Floor[(k+1)/2]+(n-k)^Ceiling[(k+1)/2])/4, 1], {n, 0, 12}, {k, 0, n}] // Flatten

T(n,k) = [n==0] + [n>0] * (k^floor((n+1)/2) + k^ceiling((n+1)/2)) / 4 + (1/(2*n)) * Sum_{d|n} phi(d) * k^(n/d).
T(n,k) = (A075195(n,k) + A284855(n,k)) / 2.
T(n,k) = A075195(n,k) - A293496(n,k) = A293496(n,k) + A284855(n,k).
Linear recurrence for row n: T(n,k) = Sum_{j=0..n} -binomial(j-n-1,j+1) * T(n,k-1-j) for k >= n + 1.
O.g.f. for column k >= 0: Sum_{n>=0} T(n,k)*x^n = 3/4 + (1 + k*x)^2/(4*(1 - k*x^2)) - (1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - k*x^d). - Petros Hadjicostas, Feb 07 2021

Showing 1-5 of 5 results.

cp's OEIS Frontend

A081720 Triangle T(n,k) read by rows, giving number of bracelets (turnover necklaces) with n beads of k colors (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A006565 Number of ways to color vertices of a hexagon using <= n colors, allowing only rotations.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Formula

A051137 Table T(n,k) read by antidiagonals: number of necklaces allowing turnovers (bracelets) with n beads of k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A321791 Table read by descending antidiagonals: T(n,k) is the number of unoriented cycles (bracelets) of length n using up to k available colors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula