%I
%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 antidiagonals: T(n,k) is the number of nbead necklaces of k colors not allowing reversal, with no adjacent beads having the same color.
%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) = k1, we have T(1,k) = k + S(1,k)  (k1). Thus, Sum_{n>=1} T(n,k)*x^n = k*x + Sum_{n>=1} (1/n)*Sum_{dn} (k1)^d*phi(n/d)*x^n  Sum_{s=0} (k1)*x^{2*s+1}. Letting m=n/d, we get that (column k g.f.) = k*x  (k1)*x/(1x^2) + Sum_{m>=1} (phi(m)/m)*Sum_{d>=1}((k1)*x^m)^d/d. But Sum_{d>=1} z^d/d = log(1z), and so (column k g.f.) = k*x  (k1)*x/(1x^2)  Sum_{m>=1} (phi(m)/m)*log(1(k1)*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/(1t^2), which in turn follows from the wellknown series Sum_{n>=1} phi(n)*t^n/(1+t^n) = t*(1+t^2)/(1t^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 socalled "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/(1x^2) and g(x,m) = log(1(k1)*x^m), then f^{(3)}(0) = 6, while g^{(3)}(0,m) = 2(k1)^3 for m=1, 0 for m=2, 6(k1) for m=3, and 0 for m >= 4. Then, a(k) = (1/6)*(6*(k1) + 2*(k1)^3 + (2/3)*6*(k1)) = (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.
%C (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/anumberarrayrelatedtocolorednecklacesandtheprimes">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/Pderivation">pderivation</a>.
%F Let S(n,k) = (1/n) Sum_{dn} (k1)^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)  (k1), 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)*(nk+1)! / (n2k+1)!.
%F For the table here, the first three rows, aside from initial zeros, are given by a(n,k)= (1/n)*(k+1n)! / (k+12n)! or, with no leading zeros, by a(n,k)= (1/n)*(n+k1)! / ( k1)!. 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)*((k1)*log(1+x^n) + log(1(k1)*x^n)) = k*x  (k1)*x/(1x^2)  Sum_{n>=1} (phi(n)/n)*log(1(k1)*x^n).  _Petros Hadjicostas_, Nov 05 2017
%e Table 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, 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]*(k1)^d, {d, Divisors[n]}]/n  If[OddQ[n], k1, 0]]; Table[T[nk+1, k], {n, 1, 12}, {k, n, 1, 1}] // Flatten (* _JeanFrançois Alcover_, Oct 31 2017, after _Andrew Howroyd_ *)
%o (PARI)
%o T(n,k) = if(n==1, k, sumdiv(n,d,eulerphi(n/d)*(k1)^d)/n  if(n%2, k1));
%o for(n=1, 10, for(k=1, 10, print1(T(n,k), ", ")); print) \\ _Andrew Howroyd_, Oct 14 2017
%Y Column 3..6: A106365, A106366, A106367, A106368.
%Y Row 2..7: A000217(n1), A007290, A006528(n1), A208536, A006565(n1), A208537.
%Y Cf. A185651.
%K nonn,tabl
%O 1,2
%A _R. H. Hardin_, Feb 27 2012
