login
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
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
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
KEYWORD
nonn,tabl
AUTHOR
Maxim Karimov and Vladislav Sulima, Jan 25 2024
STATUS
approved