%I #105 Jun 25 2020 02:06:47
%S 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,
%T 70,48,14,0,0,9,28,70,165,204,130,18,1,0,10,36,112,336,624,700,312,36,
%U 0,0,11,45,168,616,1554,2635,2340,834,58,1,0,12,55,240,1044,3360,7826,11160
%N 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).
%C 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
%C From _Petros Hadjicostas_, Nov 05 2017: (Start)
%C 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).
%C 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.
%C 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).
%C 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)
%H Andrew Howroyd, <a href="/A208535/b208535.txt">Table of n, a(n) for n = 1..1275</a> (first 313 terms from R. H. Hardin)
%H MathOverflow, <a href="http://mathoverflow.net/questions/184934/a-number-array-related-to-colored-necklaces-and-the-primes">A number array related to colored necklaces and the primes</a>, 2014.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Necklace_polynomial">Necklace polynomial</a> and <a href="http://en.wikipedia.org/wiki/P-derivation">p-derivation</a>.
%F Let S(n,k) = (1/n) Sum_{d|n} (k-1)^d phi(n/d), where phi is Euler's function.
%F 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
%F Empirical for row n:
%F n=1: a(k) = k
%F n=2: a(k) = (1/2)*k^2 - (1/2)*k
%F n=3: a(k) = (1/3)*k^3 - k^2 + (2/3)*k
%F n=4: a(k) = (1/4)*k^4 - k^3 + (7/4)*k^2 - k
%F n=5: a(k) = (1/5)*k^5 - k^4 + 2*k^3 - 2*k^2 + (4/5)*k
%F 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
%F 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
%F -----------
%F From _Tom Copeland_, Oct 20 2014: (Start)
%F 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)!.
%F 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.
%F Prime rows (> 1) appear to be a(m,n) = (n^m - n)/m. See Wikipedia link. (End)
%F 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
%e Table T(n,k) (with rows n >= 1 and columns k >= 1) starts:
%e 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
%e 0 1 3 6 10 15 21 28 36 45 55 66 78 ...
%e 0 0 2 8 20 40 70 112 168 240 330 440 572 ...
%e 0 1 6 24 70 165 336 616 1044 1665 2530 3696 5226 ...
%e 0 0 6 48 204 624 1554 3360 6552 11808 19998 32208 49764 ...
%e 0 1 14 130 700 2635 7826 19684 43800 88725 166870 295526 498004 ...
%e 0 0 18 312 2340 11160 39990 117648 299592 683280 1428570 2783880 5118828 ...
%e 0 1 36 834 8230 48915 210126 720916 2097684 5381685 12501280 26796726 53750346 ...
%e ...
%e All solutions for n = 4 and k = 3:
%e 1 2 1 1 1 1
%e 3 3 2 2 3 2
%e 2 2 3 1 1 1
%e 3 3 2 2 3 3
%t 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_ *)
%o (PARI)
%o T(n,k) = if(n==1, k, sumdiv(n,d,eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1));
%o for(n=1, 10, for(k=1, 10, print1(T(n,k), ", ")); print) \\ _Andrew Howroyd_, Oct 14 2017
%Y Columns 3..6: A106365, A106366, A106367, A106368.
%Y Rows 2..7: A000217(n-1), A007290, A006528(n-1), A208536, A006565(n-1), A208537.
%Y Cf. A111492, A185651, A238363.
%K nonn,tabl
%O 1,2
%A _R. H. Hardin_, Feb 27 2012
%E Name edited by _Petros Hadjicostas_, Jun 24 2020