A208536 -id:A208536 - cp's OEIS frontend

A074650 Table T(n,k) read by downward antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n >= 1, k >= 1.

1, 2, 0, 3, 1, 0, 4, 3, 2, 0, 5, 6, 8, 3, 0, 6, 10, 20, 18, 6, 0, 7, 15, 40, 60, 48, 9, 0, 8, 21, 70, 150, 204, 116, 18, 0, 9, 28, 112, 315, 624, 670, 312, 30, 0, 10, 36, 168, 588, 1554, 2580, 2340, 810, 56, 0, 11, 45, 240, 1008, 3360, 7735, 11160, 8160, 2184, 99, 0

Offset: 1

Christian G. Bower, Aug 28 2002

D. E. Knuth uses the term 'prime strings' for Lyndon words because of the fundamental theorem stating the unique factorization of strings into nonincreasing prime strings (see Knuth 7.2.1.1). With this terminology T(n,k) is the number of k-ary n-tuples (a_1,...,a_n) such that the string a_1...a_n is prime. - Peter Luschny, Aug 14 2012
Also, for k a power of a prime, the number of monic irreducible polynomials of degree n over GF(k). - Andrew Howroyd, Dec 23 2017
An equivalent description: Array read by antidiagonals: T(n,k) = number of conjugacy classes of primitive words of length k >= 1 over an alphabet of size n >= 1.
There are a few incorrect values in Table 1 in the Perrin-Reutenauer paper (Christophe Reutenauer, personal communication), see A294438. - Lars Blomberg, Dec 05 2017
The fact that T(3,4) = 20 coincides with the number of the amino acids encoded by DNA made Francis Crick, John Griffith and Leslie Orgel conjecture in 1957 that the genetic code is a comma-free code, which later turned out to be false. [Hayes] - Andrey Zabolotskiy, Mar 24 2018

			T(4, 3) counts the 18 ternary prime strings of length 4 which are: 0001, 0002, 0011, 0012, 0021, 0022, 0102, 0111, 0112, 0121, 0122, 0211, 0212, 0221, 0222, 1112, 1122, 1222.
Square array starts:
  1,  2,   3,    4,     5,     6,      7, ...
  0,  1,   3,    6,    10,    15,     21, ...
  0,  2,   8,   20,    40,    70,    112, ...
  0,  3,  18,   60,   150,   315,    588, ...
  0,  6,  48,  204,   624,  1554,   3360, ...
  0,  9, 116,  670,  2580,  7735,  19544, ...
  0, 18, 312, 2340, 11160, 39990, 117648, ...
  ...
The transposed array starts:
   1  0  0     0     0      0       0        0         0          0,
   2  1  2     3     6      9      18       30        56         99,
   3  3  8    18    48    116     312      810      2184       5880,
   4  6  20   60   204    670    2340     8160     29120     104754,
   5 10  40  150   624   2580   11160    48750    217000     976248,
   6 15  70  315  1554   7735   39990   209790   1119720    6045837,
   7 21 112  588  3360  19544  117648   720300   4483696   28245840,
   8 28 168 1008  6552  43596  299592  2096640  14913024  107370900,
   9 36 240 1620 11808  88440  683280  5380020  43046640  348672528,
  10 45 330 2475 19998 166485 1428570 12498750 111111000  999989991,
  11 55 440 3630 32208 295020 2783880 26793030 261994040 2593726344,
  12 66 572 5148 49764 497354 5118828 53745120 573308736 6191711526,
  ...
The initial antidiagonals are:
   1
   2  0
   3  1   0
   4  3   2    0
   5  6   8    3    0
   6 10  20   18    6     0
   7 15  40   60   48     9     0
   8 21  70  150  204   116    18     0
   9 28 112  315  624   670   312    30     0
  10 36 168  588 1554  2580  2340   810    56    0
  11 45 240 1008 3360  7735 11160  8160  2184   99   0
  12 55 330 1620 6552 19544 39990 48750 29120 5880 186 0

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 97 (2.3.74)
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 495.
D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, pp. 26-27, Addison-Wesley, 2005.

Alois P. Heinz, Antidiagonals n = 1..141, flattened
B. Hayes, The invention of the genetic code, American Scientist, Vol. 86, No. 1 (January-February 1998), pp. 8-14.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Irem Kucukoglu and Yilmaz Simsek, On k-ary Lyndon words and their generating functions, AIP Conference Proceedings 1863, 300004 (2017).
R. C. Lyndon, On Burnside's problem, Transactions of the American Mathematical Society 77, (1954) 202-215.
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, arXiv preprint arXiv:1609.05438 [math.CO] (2016).
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, Discrete Math., 341 (2018), 232-243.
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, Discrete Math., 341 (2018), 232-243. [Annotated scanned copy of page 236 only.]
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Columns k: A001037 (k=2), A027376 (k=3), A027377 (k=4), A001692 (k=5), A032164 (k=6), A001693 (k=7), A027380 (k=8), A027381 (k=9), A032165 (k=10), A032166 (k=11), A032167 (k=12), A060216 (k=13), A060217 (k=14), A060218 (k=15), A060219 (k=16), A060220 (k=17), A060221 (k=18), A060222 (k=19).
Rows n: A000027 (n=1), A000217(k-1) (n=2), A007290(k+1) (n=3), A006011 (n=4), A208536(k+1) (n=5), A292350 (n=6), A208537(k+1) (n=7).
Cf. A000010, A008683, A075147 (main diagonal), A102659, A215474 (preprime strings), A383011.

t:= func< n,k | (&+[MoebiusMu(Floor(n/d))*k^d: d in Divisors(n)])/n >; // array
A074650:= func< n,k | t(k, n-k+1) >; // downward diagonals
[A074650(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Aug 01 2024

with(numtheory):
T:= proc(n, k) add(mobius(n/d)*k^d, d=divisors(n))/n end:
seq(seq(T(i, 1+d-i), i=1..d), d=1..11);  # Alois P. Heinz, Mar 28 2008

max = 12; t[n_, k_] := Total[ MoebiusMu[n/#]*k^# & /@ Divisors[n]]/n; Flatten[ Table[ t[n-k+1, k], {n, 1, max}, {k, n, 1, -1}]] (* Jean-François Alcover, Oct 18 2011, after Maple *)

T(n,k)=sumdiv(n,d,moebius(n/d)*k^d)/n \\ Charles R Greathouse IV, Oct 18 2011

# This algorithm generates and counts all k-ary n-tuples (a_1,..,a_n) such
# that the string a_1...a_n is prime. It is algorithm F in Knuth 7.2.1.1.
def A074650(n, k):
    a = [0]*(n+1); a[0]=-1
    j = 1; count = 0
    while(j != 0) :
        if j == n : count += 1; # print("".join(map(str,a[1:])))
        else: j = n
        while a[j] >= k-1 : j -= 1
        a[j] += 1
        for i in (j+1..n): a[i] = a[i-j]
    return count   # Peter Luschny, Aug 14 2012

T(n,k) = (1/n) * Sum_{d|n} mu(n/d)*k^d.
T(n,k) = (k^n - Sum_{dAlois P. Heinz, Mar 28 2008
From Richard L. Ollerton, May 10 2021: (Start)
T(n,k) = (1/n)*Sum_{i=1..n} mu(gcd(n,i))*k^(n/gcd(n,i))/phi(n/gcd(n,i)).
T(n,k) = (1/n)*Sum_{i=1..n} mu(n/gcd(n,i))*k^gcd(n,i)/phi(n/gcd(n,i)). (End)
From Seiichi Manyama, Apr 12 2025: (Start)
G.f. of column k: -Sum_{j>=1} mu(j) * log(1 - k*x^j) / j.
Product_{n>=1} 1/(1 - x^n)^T(n,k) = 1/(1 - k*x). (End)

A208535 Square array read by descending antidiagonals: T(n,k) is the number of n-bead necklaces of k colors not allowing reversal, with no adjacent beads having the same color (n, k >= 1).

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 3, 0, 0, 5, 6, 2, 1, 0, 6, 10, 8, 6, 0, 0, 7, 15, 20, 24, 6, 1, 0, 8, 21, 40, 70, 48, 14, 0, 0, 9, 28, 70, 165, 204, 130, 18, 1, 0, 10, 36, 112, 336, 624, 700, 312, 36, 0, 0, 11, 45, 168, 616, 1554, 2635, 2340, 834, 58, 1, 0, 12, 55, 240, 1044, 3360, 7826, 11160

Offset: 1

R. H. Hardin, Feb 27 2012

For prime rows, these appear to be evaluations of Moreau's necklace polynomials at the integers with several combinatorial interpretations (see Wikipedia link). - Tom Copeland, Oct 20 2014
From Petros Hadjicostas, Nov 05 2017: (Start)
The g.f. for column k follows easily from I. Gessel's formulas for this sequence. Since S(1,k) = k-1, we have T(1,k) = k + S(1,k) - (k - 1). Thus, Sum_{n >= 1} T(n,k)*x^n = k*x + Sum_{n >= 1} (1/n)*Sum_{d|n} (k - 1)^d*phi(n/d)*x^n - Sum_{s=0} (k-1)*x^{2*s+1}. Letting m = n/d, we get that (column k g.f.) = k*x - (k - 1)*x/(1 -x^2) + Sum_{m >= 1} (phi(m)/m)*Sum_{d >= 1}((k - 1)*x^m)^d/d. But Sum_{d>=1} z^d/d = -log(1 - z), and so (column k g.f.) = k*x - (k - 1)*x/(1 - x^2) - Sum_{m >= 1} (phi(m)/m)*log(1 - (k - 1)*x^m).
The other formula for the g.f. of column k of this sequence follows from the formula Sum_{n >= 1} (phi(n)/n)*log(1 + t^n) = t/(1 - t^2), which in turn follows from the well-known series Sum_{n >= 1} phi(n)*t^n/(1 + t^n) = t*(1 + t^2)/(1 - t^2)^2.
The extra term k*x in the g.f. for column k is due to the fact that we conventionally assume that a necklace with only one bead, colored with one of the k colors available, is such that there are "no adjacent beads having the same color" (even though, strictly speaking, a single bead is adjacent to itself when we go around the circle of the necklace).
One can use the g.f. for column k to derive the so-called "Empirical for row n" formulae that are denoted by a(k) and given in the formula section below (from n = 1 to n = 7). For example, for n = 3, a(k) = a(k, x=0), where a(k, x) = (1/3!)*d^3/dx^3 (column k g.f.). Here, d^3/dx^3 stands for "third derivative w.r.t. x". If we let f(x) = x/(1 - x^2) and g(x, m) = -log(1 - (k - 1)*x^m), then f^{(3)}(0) = 6, while g^{(3)}(0,m) = 2*(k - 1)^3 for m = 1, 0 for m=2, 6*(k - 1) for m = 3, and 0 for m >= 4. Then, a(k) = (1/6)*(-6*(k - 1) + 2*(k - 1)^3 + (2/3)*6*(k - 1)) = (1/3)*k^3 - k^2 + (2/3)*k. Using this method, one can derive an "Empirical for row n" formula for a(k) for any positive integer n. (End)

			Table T(n,k) (with rows n >= 1 and columns k >= 1) 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  2   8   20    40     70    112     168     240      330      440      572 ...
  0 1  6  24   70   165    336    616    1044    1665     2530     3696     5226 ...
  0 0  6  48  204   624   1554   3360    6552   11808    19998    32208    49764 ...
  0 1 14 130  700  2635   7826  19684   43800   88725   166870   295526   498004 ...
  0 0 18 312 2340 11160  39990 117648  299592  683280  1428570  2783880  5118828 ...
  0 1 36 834 8230 48915 210126 720916 2097684 5381685 12501280 26796726 53750346 ...
  ...
All solutions for n = 4 and k = 3:
  1    2    1    1    1    1
  3    3    2    2    3    2
  2    2    3    1    1    1
  3    3    2    2    3    3

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 313 terms from R. H. Hardin)
MathOverflow, A number array related to colored necklaces and the primes, 2014.
Wikipedia, Necklace polynomial and p-derivation.

Columns 3..6: A106365, A106366, A106367, A106368.
Rows 2..7: A000217(n-1), A007290, A006528(n-1), A208536, A006565(n-1), A208537.
Cf. A111492, A185651, A238363.

T[n_, k_] := If[n == 1, k, Sum[ EulerPhi[n/d]*(k-1)^d, {d, Divisors[n]}]/n - If[OddQ[n], k-1, 0]]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)

T(n,k) = if(n==1, k, sumdiv(n,d,eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1));
for(n=1, 10, for(k=1, 10, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 14 2017

Let S(n,k) = (1/n) Sum_{d|n} (k-1)^d phi(n/d), where phi is Euler's function.
Then for n even, T(n,k) = S(n,k) and for n > 1 and odd, T(n,k) = S(n,k) - (k-1), and T(1,k) = k. - Ira M. Gessel, Oct 21 2014, Sep 25 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/3)*k^3 - k^2 + (2/3)*k
n=4: a(k) = (1/4)*k^4 - k^3 + (7/4)*k^2 - k
n=5: a(k) = (1/5)*k^5 - k^4 + 2*k^3 - 2*k^2 + (4/5)*k
n=6: a(k) = (1/6)*k^6 - k^5 + (5/2)*k^4 - (19/6)*k^3 + (7/3)*k^2 - (5/6)*k
n=7: a(k) = (1/7)*k^7 - k^6 + 3*k^5 - 5*k^4 + 5*k^3 - 3*k^2 + (6/7)*k
-----------
From Tom Copeland, Oct 20 2014: (Start)
The first three numbers in each row of the triangular array are given by T(n,k) = (1/k)*(n-k+1)! / (n-2*k+1)!.
For the table here, the first three rows, aside from initial zeros, are given by a(n,k) = (1/n)*(k + 1 - n)! / (k + 1 - 2*n)! or, with no leading zeros, by a(n,k) = (1/n)*(n+k-1)! / (k-1)!. The first three elements of each column correspond to the last three elements of a row in A238363 and the first three of A111492.
Prime rows (> 1) appear to be a(m,n) = (n^m - n)/m. See Wikipedia link. (End)
G.f. for column k: Sum_{n >= 1} T(n,k)*x^n = k*x - Sum_{n >= 1} (phi(n)/n)*((k - 1)*log(1 + x^n) + log(1 - (k - 1)*x^n)) = k*x - (k - 1)*x/(1 - x^2) - Sum_{n >= 1} (phi(n)/n)*log(1 - (k - 1)*x^n). - Petros Hadjicostas, Nov 05 2017

Name edited by Petros Hadjicostas, Jun 24 2020

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

Original entry on oeis.org

0, 0, 18, 312, 2340, 11160, 39990, 117648, 299592, 683280, 1428570, 2783880, 5118828, 8964072, 15059070, 24408480, 38347920, 58619808, 87460002, 127695960, 182857140, 257298360, 356336838, 486403632, 655210200, 871930800, 1147401450

Offset: 1

R. H. Hardin, Feb 27 2012

This sequence would be better defined as a(n) = (n^7-n)/7 with offset 0, which is an integer by Fermat's little theorem. - N. J. A. Sloane, Nov 13 2023
Row 7 of A208535.
Also, row 7 (with different offset) of A074650. - Eric M. Schmidt, Dec 08 2017

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

J. Jeffries, Differentiating by prime numbers, Notices Amer. Math. Soc., 70:11 (2023), 1772-1779.

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

Cf. A208535.

A208537[n_]:=((n-1)^7-(n-1))/7;Array[A208537,50] (* Paolo Xausa, Nov 14 2023 *)

Vec(6*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/7)*n^7 - 1*n^6 + 3*n^5 - 5*n^4 + 5*n^3 - 3*n^2 + (6/7)*n.
Empirical formula confirmed by Petros Hadjicostas, Nov 05 2017 (see A208535).
a(n+2) = delta(-n) = -delta(n) for n >= 0, where delta is the p-derivation over the integers with respect to prime p = 7. - Danny Rorabaugh, Nov 10 2017
From Colin Barker, Nov 11 2017: (Start)
G.f.: 6*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)
a(n) = ((n-1)^7 - (n-1))/7. (inspired by Hassler's formula in A208536) - Eric M. Schmidt, Dec 08 2017

A138426 a(n) = ((prime(n))^5-prime(n))/5.

Original entry on oeis.org

6, 48, 624, 3360, 32208, 74256, 283968, 495216, 1287264, 4102224, 5725824, 13868784, 23171232, 29401680, 45868992, 83639088, 142984848, 168919248, 270025008, 360845856, 414614304, 615411264, 787808112, 1116811872

Offset: 1

Artur Jasinski, Mar 19 2008

Number of monic irreducible polynomials of degree 5 over GF(prime(n)). - Robert Israel, Jan 07 2015

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Wikipedia, Necklace polynomial

Cf. A008837, A127919, A138420, A208536.

[(NthPrime((n))^5 - NthPrime((n)))/5: n in [1..30] ]; // Vincenzo Librandi, Jun 18 2011

seq((ithprime(i)^5-ithprime(i))/5, i = 1 .. 50); # Robert Israel, Jan 07 2015

a = {}; Do[p = Prime[n]; AppendTo[a, (p^5 - p)/5], {n, 1, 50}]; a
(#^5-#)/5&/@Prime[Range[30]] (* Harvey P. Dale, Mar 12 2018 *)

forprime(p=2,1e3,print1((p^5-p)/5", ")) \\ Charles R Greathouse IV, Jul 15 2011

a(n) = A138404(n)/5. - R. J. Mathar, Oct 15 2017

A366488 a(n) = (n^11 - n)/11.

Original entry on oeis.org

0, 0, 186, 16104, 381300, 4438920, 32981550, 179756976, 780903144, 2852823600, 9090909090, 25937424600, 67546215516, 162923672184, 368142288150, 786341441760, 1599289640400, 3115626937056, 5842582734474, 10590023536200, 18618181818180, 31843409140200, 53119845582846, 86619068901264, 138334649379000, 216744162819600

Offset: 0

N. J. A. Sloane, Nov 13 2023

If p is a prime, (n^p-n)/p is an integer by Fermat's Little Theorem. For p = 2, 3, 5, 7, ..., this gives A000217, A007290, A208536, A208537, this sequence, A366489, A366490, A366491.

Stefano Spezia, Table of n, a(n) for n = 0..10000
Jack Jeffries, Differentiating by prime numbers, Notices Amer. Math. Soc., 70:11 (2023), 1772-1779.
Index entries for linear recurrences with constant coefficients, signature (12,-66,220,-495,792,-924,792,-495,220,-66,12,-1).

Cf. A000217, A007290, A208536, A208537, A366489, A366490, A366491.

A366488[n_]:=(n^11-n)/11;Array[A366488,30,0] (* Paolo Xausa, Nov 14 2023 *)
LinearRecurrence[{12,-66,220,-495,792,-924,792,-495,220,-66,12,-1},{0,0,186,16104,381300,4438920,32981550,179756976,780903144,2852823600,9090909090,25937424600},30] (* Harvey P. Dale, Aug 03 2025 *)

a(n) == 0 (mod 6). - Hugo Pfoertner, Nov 14 2023

cp's OEIS Frontend

A074650 Table T(n,k) read by downward antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A208535 Square array read by descending antidiagonals: T(n,k) is the number of n-bead necklaces of k colors not allowing reversal, with no adjacent beads having the same color (n, k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A138426 a(n) = ((prime(n))^5-prime(n))/5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A366488 a(n) = (n^11 - n)/11.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A366489 a(n) = (n^13 - n)/13.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A366490 a(n) = (n^17 - n)/17.

Views

Author

Keywords