

A208535


Square array read by descending antidiagonals: T(n,k) is the number of nbead necklaces of k colors not allowing reversal, with no adjacent beads having the same color (n, k >= 1).


15



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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
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)  (k  1). Thus, Sum_{n >= 1} T(n,k)*x^n = k*x + Sum_{n >= 1} (1/n)*Sum_{dn} (k  1)^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  (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 wellknown 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 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/(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)


LINKS



FORMULA

Let S(n,k) = (1/n) Sum_{dn} (k1)^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)  (k1), 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

The first three numbers in each row of the triangular array are given by T(n,k) = (1/k)*(nk+1)! / (n2*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+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.
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


EXAMPLE

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


MATHEMATICA

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


PROG

(PARI)
T(n, k) = if(n==1, k, sumdiv(n, d, eulerphi(n/d)*(k1)^d)/n  if(n%2, k1));
for(n=1, 10, for(k=1, 10, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 14 2017


CROSSREFS



KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



