cp's OEIS Frontend

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

Also number of ways to insert two pairs of parentheses into a string of n-4 letters (allowing empty pairs of parentheses). E.g., there are 30 ways for 2 letters. Cf. A002415.

2,10,30,70, ... gives orchard crossing number of complete graph K_n. - Ralf Stephan, Mar 28 2003

If Y is a 2-subset of an n-set X then, for n>=4, a(n-1) is the number of 4-subsets and 5-subsets of X having exactly one element in common with Y. - Milan Janjic, Dec 28 2007

Middle column of table on p. 6 of Feder and Garber. - Jonathan Vos Post, Apr 23 2009

Number of pairs of non-intersecting lines when each of n points around a circle is joined to every other point by straight lines. A pair of lines is considered non-intersecting if the lines do not intersect in either the interior or the boundary of a circle. - Melvin Peralta, Feb 05 2016

From a(2), convolution of the oblong numbers (A002378) with the nonnegative numbers (A001477). - Bruno Berselli, Oct 24 2016

Also the number of 3-cycles in the n-triangular honeycomb bishop graph. - Eric W. Weisstein, Aug 10 2017

T(n,k) = number of permutations of n elements with k fixed points.

T(n,n-1)=0 and T(n,n)=1 are omitted from the array. - Geoffrey Critzer, Nov 28 2011.

Row sums of triangle A131782 starting (1, 6, 17, 36, 65, 106, ...). - Gary W. Adamson, Jul 14 2007

a(n) is the number of triples (x,y,z) in {1,2,...,n}^3 with x <= y <= z or x >= y >= z. - Jack Kennedy, Mar 14 2009

a(2*n) is the difference between numbers of nonnegative multiples of 2*n+1 with even and odd digit sum in base 2*n in interval [0, 16*n^4). - Vladimir Shevelev, May 18 2012

Removing a factor of 2^m from the m-th subdiagonal (the main diagonal corresponds to m = 0) gives the triangle A080248. - Peter Bala, Oct 15 2023

(tan(x))^k = sum{n>0, If n+k is odd, T(n,k) = 0 = n!/k!*(-1)^((n+k)/2)*sum{j=k..n} (j!/n!) * Stirling2(n,j) * 2^(n-j) * (-1)^(n+j-k) * binomial(j-1,k-1)*x^n}. - Vladimir Kruchinin, Aug 13 2012

Also the Bell transform of A009006(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 26 2016

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 starts

....0.......0.........0...........0............0..............0...............0

....2.......8........20..........40...........70............112.............168

...10......72.......294.........896.........2268...........5040...........10164

...34.....450......3114.......15116........58036.........188034..........535106

...98....2420.....29120......232432......1402082........6872424........28658242

..258...12010....256020.....3441072.....33505396......255757328......1610555756

..642...56754...2173554....50108414....804566180.....9790184488.....95420380090

.1538..259628..18060096...724727082..19525545192...386105784866...5945425725202

.3586.1160936.147976270.10461499634.479803630966.15669594394610.387907415514308

First differs from A213364 at a(12).