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

From Petros Hadjicostas, Nov 05 2017: (Start)

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

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.

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 313 terms from R. H. Hardin)

MathOverflow, A number array related to colored necklaces and the primes  (2014)

Wikipedia, Necklace polynomial and p-derivation.

FORMULA

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

-----------

From Tom Copeland, Oct 20 2014: (Start)

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

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.

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 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, 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]*(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 *)

PROG

(PARI)

T(n, k) = if(n==1, k, sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1));

for(n=1, 10, for(k=1, 10, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 14 2017

CROSSREFS

Column 3..6: A106365, A106366, A106367, A106368.

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

Cf. A185651.

Sequence in context: A144257 A257232 A208544 * A284856 A276550 A294438

Adjacent sequences:  A208532 A208533 A208534 * A208536 A208537 A208538

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Feb 27 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 04:29 EDT 2018. Contains 316431 sequences. (Running on oeis4.)