login
A347351
Triangle read by rows: T(n,k) is the number of links of length k in a set of all necklaces A000358 of length n, 1 <= k <= n.
0
1, 2, 1, 3, 0, 1, 4, 2, 0, 1, 5, 1, 1, 0, 1, 6, 4, 2, 1, 0, 1, 7, 3, 2, 1, 1, 0, 1, 8, 8, 3, 3, 1, 1, 0, 1, 9, 8, 7, 3, 2, 1, 1, 0, 1, 10, 18, 9, 5, 4, 2, 1, 1, 0, 1, 11, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1, 12, 40, 24, 16, 8, 6, 3, 2, 1, 1, 0, 1, 13, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1
OFFSET
0,2
COMMENTS
Definitions:
1. A link is any 0 in any necklace from A000358 and all 1s following this 0 in this necklace to right until another 0 is encountered.
2. Length of the link is the number of elements in the link.
Sum of all elements n-row is Fibonacci(n-1)+n iff n=1 or n=p (follows from the identity for the sum of the Fibonacci numbers and the formula for the triangle T(n,k)).
FORMULA
If k=1, T(n,k)=n, otherwise T(n,k) = Sum_{d>=k, d|n} Phi(n/d)*Fibonacci(d-k-1), where Phi=A000010.
EXAMPLE
For k > 0:
n\k | 1 2 3 4 5 6 7 8 9 10 ...
-----+---------------------------------------
1 | 1
2 | 2 1
3 | 3 0 1
4 | 4 2 0 1
5 | 5 1 1 0 1
6 | 6 4 2 1 0 1
7 | 7 3 2 1 1 0 1
8 | 8 8 3 3 1 1 0 1
9 | 9 8 7 3 2 1 1 0 1
10 | 10 18 9 5 4 2 1 1 0 1
...
If we continue the calculation for nonpositive k, we get a table in which each row is a Fibonacci sequence, in which term(0) = A113166, term(1) = A034748.
For k <= 0:
n\k | 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ...
-----+------------------------------------------------
1 | 0 1 1 2 3 5 8 13 21 34 ... A000045
2 | 1 2 3 5 8 13 21 34 55 89 ... A000045
3 | 1 4 5 9 14 23 37 60 97 157 ... A000285
4 | 3 6 9 15 24 39 63 102 165 267 ... A022086
5 | 3 9 12 21 33 54 87 141 228 369 ... A022379
6 | 8 14 22 36 58 94 152 246 398 644 ... A022112
7 | 8 19 27 46 73 119 192 311 503 814 ... A206420
8 | 17 30 47 77 124 201 325 526 851 1377 ... A022132
9 | 23 44 67 111 178 289 467 756 1223 1979 ... A294116
10 | 41 68 109 177 286 463 749 1212 1961 3173 ... A022103
...
PROG
(MATLAB)
function [res] = calcLinks(n, k)
if k==1
res=n;
else
d=divisors(n);
res=0;
for i=1:length(d)
if d (i) >= k
res=res+eulerPhi(n/d(i))*fiboExt(d(i)-k-1);
end
end
end
function [s] = fiboExt(m) % extended fibonacci function (including negative arguments)
m=sym(m); % for large fibonacci numbers
if m>=0 || mod(m, 2)==1
s=fibonacci(abs(m));
else
s=fibonacci(abs(m))*(-1);
end
(PARI) T(n, k) = if (k==1, n, sumdiv(n, d, if (d>=k, eulerphi(n/d)*fibonacci(d-k-1)))); \\ Michel Marcus, Aug 29 2021
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Maxim Karimov and Vladislav Sulima, Aug 28 2021
STATUS
approved