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

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

Author

R. H. Hardin, Feb 27 2012

Keywords

• nonn
• tabl

Comments

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)

Examples

			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
		

Links

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

Crossrefs

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.

Programs

Mathematica

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

PARI

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

Formula

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

Extensions

Name edited by Petros Hadjicostas, Jun 24 2020