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

Author

Maxim Karimov and Vladislav Sulima, Jan 25 2024

Keywords

• nonn
• tabl

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

Examples

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

Links

• C. G. Bower, Transforms (2).

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

Programs

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

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