login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A208535 Square array read by 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. 12

%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 n-bead 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) = 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.

%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/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-2k+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-2n)! 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 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]*(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 Column 3..6: A106365, A106366, A106367, A106368.

%Y Row 2..7: A000217(n-1), A007290, A006528(n-1), A208536, A006565(n-1), A208537.

%Y Cf. A185651.

%K nonn,tabl

%O 1,2

%A _R. H. Hardin_, Feb 27 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 04:30 EST 2019. Contains 320411 sequences. (Running on oeis4.)