cp's OEIS Frontend

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

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