A369524 Array read by antidiagonals: T(n,k) is the number of length n necklaces using at most k colors with black beads always occurring in runs of even length.

0, 1, 1, 2, 2, 0, 3, 4, 2, 1, 4, 7, 6, 3, 0, 5, 11, 14, 11, 3, 1, 6, 16, 28, 34, 18, 5, 0, 7, 22, 50, 87, 81, 38, 5, 1, 8, 29, 82, 191, 276, 227, 70, 8, 0, 9, 37, 126, 373, 759, 983, 615, 151, 10, 1, 10, 46, 184, 666, 1782, 3301, 3500, 1789, 314, 15, 0, 11, 56, 258, 1109, 3717, 9180, 14545, 13007, 5206, 684, 19, 1

Offset

1,4

Comments

Equivalently, black beads can be considered to have length 2, while all other beads have length 1.

Column k is the "CIK" (necklace, indistinct, unlabeled) transform of {k-1, 1, 0, 0, 0, ...} (see C. Bower link). - Andrew Howroyd, Jan 25 2024

Links

Table of n, a(n) for n=1..78.

C. G. Bower, Transforms (2).

Formula

T(n,k) = (1/n) * Sum_{d|n} phi(n/d) * ((k-1)^d + Sum_{i=1..floor(d/2)} binomial(d-i-1,i-1) * d/i * (k-1)^(d-2*i)), where phi(n) = A000010.

G.f. of column k: Sum_{d>=1} (phi(d)/d) * log(1/(1 - (k-1)*x^d - x^(2*d))). - Andrew Howroyd, Jan 25 2024

Example

n\k| 1  2   3     4      5       6       7        8         9 ...
---+-----------------------------------------------------------------
 1 | 0  1   2     3      4       5       6        7         8 ...A001477
 2 | 1  2   4     7     11      16      22       29        37 ...A000124
 3 | 0  2   6    14     28      50      82      126       184 ...A033547
 4 | 1  3  11    34     87     191     373      666      1109
 5 | 0  3  18    81    276     759    1782     3717      7080
 6 | 1  5  38   227    983    3301    9180    22163     47997
 7 | 0  5  70   615   3500   14545   48210   135155    333400
 8 | 1  8 151  1789  13007   66166  260113   844691   2370229
 9 | 0 10 314  5206  48820  304970 1423790  5358934  17110376
10 | 1 15 684 15490 186195 1425453 7897006 34438104 125093109
...

Prog

(MATLAB)
function [res] = num2(n, k)
res=0;
for d=divisors(n)
    s=(k-1)^d;
    for i=1:floor(d/2)
        s=s + nchoosek(d-i-1, i-1) * d/i * (k-1)^(d-2*i);
    end
    res= res + eulerPhi(n/d) * s;
end
res=res/n;
end
(PARI) T(n, k) = sum(d=1, n, eulerphi(d)*polcoef(log(1/(1 - (k-1)*x^d - x^(2*d)) + O(x*x^n)), n)/d)  \\ Andrew Howroyd, Jan 25 2024

Crossrefs

Columns 1..2 are A000035(n-1), A000358.

Rows 1..3 are A001477(k-1), A000124(k-1), A033547(k-1).

Cf. A000010 (phi), A075195 (all beads of same length).

Sequence in context: A262879 A278482 A324657 * A339422 A367746 A094053

Adjacent sequences: A369521 A369522 A369523 * A369525 A369526 A369527

Keyword

nonn,tabl

Author

Maxim Karimov and Vladislav Sulima, Jan 25 2024

Status

approved