A074650 -id:A074650 - cp's OEIS frontend

A309528 The number of non-equivalent distinguishing colorings of the cycle on n vertices with at most k colors (k>=1). The cycle graph is defined for n>=3; extended to n=1,2 using the closed form. Square array read by descending antidiagonals: the rows are indexed by n, the number of vertices of the cycle and the columns are indexed by k, the number of permissible colors.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 4, 3, 0, 0, 0, 0, 10, 15, 12, 1, 0, 0, 0, 20, 45, 72, 37, 2, 0, 0, 0, 35, 105, 252, 266, 117, 6, 0, 0, 0, 56, 210, 672, 1120, 1044, 333, 14, 0, 0, 0, 84, 378, 1512, 3515, 5270, 3788, 975, 30, 0, 0, 0, 120, 630, 3024, 9121, 19350, 23475, 14056, 2712, 62, 0

Offset: 1

Bahman Ahmadi, Aug 06 2019

A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. Two vertex-colorings of a graph are called equivalent if there is an automorphism of the graph which preserves the colors of the vertices. Given a graph G, we use the notation Phi_k(G) to denote the number of non-equivalent distinguishing colorings of G with at most k colors. The sequence here, displays A(n,k)=Phi_k(C_n), i.e., the number of non-equivalent distinguishing colorings of the cycle C_n on n vertices with at most k colors.

			The table begins:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 0, 1, 4, 10, 20, 35, 56, 84, 120, ...
0, 0, 3, 15, 45, 105, 210, 378, 630, 990, ...
0, 0, 12, 72, 252, 672, 1512, 3024, 5544, 9504, ...
0, 1, 37, 266, 1120, 3515, 9121, 20692, 42456, 80565, ...
0, 2, 117, 1044, 5270, 19350, 57627, 147752, 338364, 709290, ...
0, 6, 333, 3788, 23475, 102690, 355446, 1039248, 2673810, 6222150, ...
0, 14, 975, 14056, 106950, 555990, 2233469, 7440160, 21493836, 55505550, ...
0, 30, 2712, 51132, 483504, 3009426, 14089488, 53611992, 174189024, 499720518, ...
------
For n=4, we can color the vertices of the cycle C_4 with at most 3 colors, in 3 ways, such that all the colorings distinguish the graph (i.e., no non-identity automorphism of C_4 preserves the coloring) and that all the three colorings are non-equivalent. The color classes are as follows:
{ { 1 }, { 2 }, { 3, 4 } }
{ { 1 }, { 2, 3 }, { 4 } }
{ { 1, 2 }, { 3 }, { 4 } }

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Columns k=2..5 for n >= 3 are A032239, A032240, A032241, A032242.
Cf. A074650, A284856.
Different from A293496.

A(n,k)={sumdiv(n, d, moebius(n/d)*(k^d/n - if(d%2, k^((d+1)/2), (k+1)*k^(d/2)/2)))/2} \\ Andrew Howroyd, Aug 11 2019

A(n,k) = (A074650(n,k) - A284856(n,k))/2. - Andrew Howroyd, Aug 11 2019

A001693 Number of degree-n irreducible polynomials over GF(7); dimensions of free Lie algebras.

Original entry on oeis.org

1, 7, 21, 112, 588, 3360, 19544, 117648, 720300, 4483696, 28245840, 179756976, 1153430600, 7453000800, 48444446376, 316504099520, 2077057800300, 13684147881600, 90467419857752, 599941851861744

Offset: 0

N. J. A. Sloane

Number of aperiodic necklaces with n beads of 7 colors. - Herbert Kociemba, Nov 25 2016

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..1186 (terms 0..200 from T. D. Noe)
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
G. J. Simmons, The number of irreducible polynomials of degree n over GF(p), Amer. Math. Monthly, 77 (1970), 743-745.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
Index entries for sequences related to Lyndon words

Column 7 of A074650.

Cf. A027376, A000031, A001037, A032164.

with(numtheory); A001693 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+mobius(d)*7^(n/d); od; RETURN(s/n); fi; end;

a[n_]:=(1/n)*Sum[MoebiusMu[d]*7^(n/d), {d, Divisors[n]}]; a[0] = 1; Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Aug 31 2011, after formula *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,7],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n) = if(n, sumdiv(n, d, moebius(d)*7^(n/d))/n, 1) \\ Altug Alkan, Dec 01 2015

a(n) = (1/n)*Sum_{d|n} mu(d)*7^(n/d), for n>0.

G.f.: k=7, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016

Description corrected by Vladeta Jovovic, Feb 09 2001

A027380 Number of irreducible polynomials of degree n over GF(8); dimensions of free Lie algebras.

Original entry on oeis.org

1, 8, 28, 168, 1008, 6552, 43596, 299592, 2096640, 14913024, 107370900, 780903144, 5726600880, 42288908760, 314146029564, 2345624803704, 17592184995840, 132458812569720, 1000799909722368, 7585009898729256

Offset: 0

N. J. A. Sloane

nonn

Number of Lyndon words with 8 letters. - Joerg Arndt, Jul 29 2014

Number of aperiodic necklaces with n beads of 8 colors. - Herbert Kociemba, Nov 25 2016

			G.f. = 1 + 8*x + 28*x^2 + 168*x^3 + 1008*x^4 + 6552*x^5 + 43596*x^6 + ...

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Seiichi Manyama, Table of n, a(n) for n = 0..1110 (terms 0..200 from T. D. Noe)
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
Index entries for sequences related to Lyndon words

Column 8 of A074650.

Cf. A001037, A001693.

A027380 := proc(n)
    local d;
    if n = 0 then
        1;
    else
        add( 8^(n/d)*numtheory[mobius](d),d=numtheory[divisors](n)) ;
        %/n ;
    end if;
end proc: # R. J. Mathar, Jun 09 2016

f[n_] := (1/n)*Sum[MoebiusMu[d]*8^(n/d), {d, Divisors[n]}]; f[0] = 1; Array[f, 20, 0] (* Robert G. Wilson v, Jul 28 2014 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,8],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n) = if(n, sumdiv(n, d, moebius(d)*8^(n/d))/n, 1) \\ Altug Alkan, Dec 01 2015

G.f.: k=8, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016

a(n) = Sum_{d|n} mu(d)*8^(n/d)/n for n > 0. - Andrew Howroyd, Oct 13 2017

A027381 Number of irreducible polynomials of degree n over GF(9); dimensions of free Lie algebras.

Original entry on oeis.org

1, 9, 36, 240, 1620, 11808, 88440, 683280, 5380020, 43046640, 348672528, 2852823600, 23535749880, 195528140640, 1634056262280, 13726075468992, 115813759112820, 981010688215680, 8338590828280440, 71097458824894320

Offset: 0

N. J. A. Sloane

nonn

Number of aperiodic necklaces with n beads of 9 colors. - Herbert Kociemba, Nov 25 2016

			G.f. = 1 + 9*x + 36*x^2 + 240*x^3 + 1620*x^4 + 11808*x^5 + 88440*x^6 + ...

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Seiichi Manyama, Table of n, a(n) for n = 0..1051 (terms 0..200 from T. D. Noe)
A. Pakapongpun, T. Ward, Functorial Orbit Counting, JIS 12 (2009) 09.2.4, example 3.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
Index entries for sequences related to Lyndon words

Column 9 of A074650.

Cf. A001037.

f[n_] := (1/n)*Sum[ MoebiusMu[d]*9^(n/d), {d, Divisors[n]}]; f[0] = 1; Array[f, 20, 0] (* Robert G. Wilson v, Jul 28 2014 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,9],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n) = if(n, sumdiv(n, d, moebius(d)*9^(n/d))/n, 1) \\ Altug Alkan, Dec 01 2015

G.f.: k=9, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016

a(n) = Sum_{d|n} mu(d)*9^(n/d)/n for n > 0. - Andrew Howroyd, Oct 13 2017

A252764 Number of length n primitive (=aperiodic or period n) n-ary words.

Original entry on oeis.org

1, 2, 24, 240, 3120, 46410, 823536, 16773120, 387419760, 9999899910, 285311670600, 8916097441680, 302875106592240, 11112006720144330, 437893890380096640, 18446744069414584320, 827240261886336764160, 39346408075098144278664, 1978419655660313589123960

Offset: 1

Alois P. Heinz, Dec 21 2014

nonn

			a(3) = 24 because there are 24 primitive words of length 3 over 3-letter alphabet {a,b,c}: aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb.

Alois P. Heinz, Table of n, a(n) for n = 1..350

Main diagonal of A143324.

Cf. A008683, A074650, A075147, A143324, A143325.

with(numtheory):
a:= n-> add(n^d *mobius(n/d), d=divisors(n)):
seq(a(n), n=1..25);

a[n_] := DivisorSum[n, n^# * MoebiusMu[n/#]& ];
Array[a, 25] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

a(n) = Sum_{d|n} n^d * mu(n/d), mu = A008683.
a(n) = A075147(n)*n.
a(n) = A074650(n,n) * n.
a(n) = A143325(n,n) * n.
a(n) = A143324(n,n).

A320071 Number of length n primitive (=aperiodic or period n) 6-ary words which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 5, 35, 210, 1295, 7735, 46655, 279720, 1679580, 10076395, 60466175, 362789070, 2176782335, 13060647355, 78364162765, 470184704640, 2821109907455, 16926657757380, 101559956668415, 609359729932590, 3656158440016285, 21936950579911675, 131621703842267135

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Dirichlet convolution of mu(n) with 6^(n-1).

Alois P. Heinz, Table of n, a(n) for n = 1..1286

Column k=6 of A143325.
First differences of A320090.
Cf. A008683, A074650, A143324.

a:= n-> add(`if`(d=n, 6^(n-1), -a(d)), d=numtheory[divisors](n)):
seq(a(n), n=1..25);

nmax = 20; Rest[CoefficientList[Series[Sum[MoebiusMu[k] * x^k / (1 - 6*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = Sum_{d|n} 6^(d-1) * mu(n/d).

a(n) = 6^(n-1) - Sum_{d

a(n) = A143325(n,6).

a(n) = A074650(n,6) * n/6.

a(n) = A143324(n,6) / 6.

G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 6*x^k). - Ilya Gutkovskiy, Oct 25 2018

A320072 Number of length n primitive (=aperiodic or period n) 7-ary words which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 6, 48, 336, 2400, 16752, 117648, 823200, 5764752, 40351200, 282475248, 1977309600, 13841287200, 96888892752, 678223070400, 4747560686400, 33232930569600, 232630508205648, 1628413597910448, 11398895145019200, 79792266297494304, 558545863800808752

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Dirichlet convolution of mu(n) with 7^(n-1).

Alois P. Heinz, Table of n, a(n) for n = 1..1184

Column k=7 of A143325.
First differences of A320091.
Cf. A008683, A074650, A143324.

a:= n-> add(`if`(d=n, 7^(n-1), -a(d)), d=numtheory[divisors](n)):
seq(a(n), n=1..25);

a(n) = Sum_{d|n} 7^(d-1) * mu(n/d).

a(n) = 7^(n-1) - Sum_{d

a(n) = A143325(n,7).

a(n) = A074650(n,7) * n/7.

a(n) = A143324(n,7) / 7.

G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 7*x^k). - Ilya Gutkovskiy, Oct 25 2018

A320073 Number of length n primitive (=aperiodic or period n) 8-ary words which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 7, 63, 504, 4095, 32697, 262143, 2096640, 16777152, 134213625, 1073741823, 8589901320, 68719476735, 549755551737, 4398046506945, 35184369991680, 281474976710655, 2251799796875328, 18014398509481983, 144115187941637640, 1152921504606584769

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Dirichlet convolution of mu(n) with 8^(n-1).

Alois P. Heinz, Table of n, a(n) for n = 1..1108

Column k=8 of A143325.
First differences of A320092.
Cf. A008683, A074650, A143324.

a:= n-> add(`if`(d=n, 8^(n-1), -a(d)), d=numtheory[divisors](n)):
seq(a(n), n=1..25);

a(n) = Sum_{d|n} 8^(d-1) * mu(n/d).

a(n) = 8^(n-1) - Sum_{d

a(n) = A143325(n,8).

a(n) = A074650(n,8) * n/8.

a(n) = A143324(n,8) / 8.

G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 8*x^k). - Ilya Gutkovskiy, Oct 25 2018

A320074 Number of length n primitive (=aperiodic or period n) 9-ary words which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 8, 80, 720, 6560, 58960, 531440, 4782240, 43046640, 387413920, 3486784400, 31380999840, 282429536480, 2541865296880, 22876792448320, 205891127311680, 1853020188851840, 16677181656560880, 150094635296999120, 1350851717285570880, 12157665459056397280

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

Dirichlet convolution of mu(n) with 9^(n-1).

Alois P. Heinz, Table of n, a(n) for n = 1..1048

Column k=9 of A143325.
First differences of A320093.
Cf. A008683, A074650, A143324.

a:= n-> add(`if`(d=n, 9^(n-1), -a(d)), d=numtheory[divisors](n)):
seq(a(n), n=1..25);

a(n) = Sum_{d|n} 9^(d-1) * mu(n/d).

a(n) = 9^(n-1) - Sum_{d

a(n) = A143325(n,9).

a(n) = A074650(n,9) * n/9.

a(n) = A143324(n,9) / 9.

G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 9*x^k). - Ilya Gutkovskiy, Oct 25 2018

A006177 Witt vector *2!/2!.

Original entry on oeis.org

1, 1, 3, 8, 25, 72, 245, 772, 2692, 8925, 32065, 109890, 400023, 1402723, 5165327, 18484746, 68635477, 248339122, 930138521, 3406231198, 12810761323, 47306348881, 178987624513, 665627041157, 2528210175630, 9456885664122

Offset: 1

Simon Plouffe

nonn

The Somos transform sends sequence {a(n)} to sequence with g.f. Product_{i=1..n} 1/(1-a(i)*x^i).

If c is the Witt transform of b then b(n) = Sum_{d|n} A074650(n/d, c(d)).

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

H. Gaudier, Relèvement des coefficients binomiaux dans les vecteurs de Witt, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 16 (1988), 358/S-18, pp. 93-108.
H. Gaudier, Relèvement des coefficients binomiaux dans les vecteurs de Witt, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 16 (1988), 358/S-18, pp. 93-107. (Annotated scanned copy)

Cf. A006173, A006973.

Inverse Somos transform of A000108. - Wouter Meeussen, Aug 20 2002

Witt transform of A022553.

Edited by Christian G. Bower, Aug 20 2002, Aug 28 2002

Previous Showing 21-30 of 55 results. Next

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A001693 Number of degree-n irreducible polynomials over GF(7); dimensions of free Lie algebras.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A027380 Number of irreducible polynomials of degree n over GF(8); dimensions of free Lie algebras.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A027381 Number of irreducible polynomials of degree n over GF(9); dimensions of free Lie algebras.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A252764 Number of length n primitive (=aperiodic or period n) n-ary words.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320071 Number of length n primitive (=aperiodic or period n) 6-ary words which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320072 Number of length n primitive (=aperiodic or period n) 7-ary words which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Comments

Links