|
%I #69 Nov 09 2021 06:08:35
%S 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,
%T 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,
%U 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
%N 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.
%C Definitions:
%C 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.
%C 2. Length of the link is the number of elements in the link.
%C 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)).
%F 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.
%e For k > 0:
%e n\k | 1 2 3 4 5 6 7 8 9 10 ...
%e -----+---------------------------------------
%e 1 | 1
%e 2 | 2 1
%e 3 | 3 0 1
%e 4 | 4 2 0 1
%e 5 | 5 1 1 0 1
%e 6 | 6 4 2 1 0 1
%e 7 | 7 3 2 1 1 0 1
%e 8 | 8 8 3 3 1 1 0 1
%e 9 | 9 8 7 3 2 1 1 0 1
%e 10 | 10 18 9 5 4 2 1 1 0 1
%e ...
%e 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.
%e For k <= 0:
%e n\k | 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ...
%e -----+------------------------------------------------
%e 1 | 0 1 1 2 3 5 8 13 21 34 ... A000045
%e 2 | 1 2 3 5 8 13 21 34 55 89 ... A000045
%e 3 | 1 4 5 9 14 23 37 60 97 157 ... A000285
%e 4 | 3 6 9 15 24 39 63 102 165 267 ... A022086
%e 5 | 3 9 12 21 33 54 87 141 228 369 ... A022379
%e 6 | 8 14 22 36 58 94 152 246 398 644 ... A022112
%e 7 | 8 19 27 46 73 119 192 311 503 814 ... A206420
%e 8 | 17 30 47 77 124 201 325 526 851 1377 ... A022132
%e 9 | 23 44 67 111 178 289 467 756 1223 1979 ... A294116
%e 10 | 41 68 109 177 286 463 749 1212 1961 3173 ... A022103
%e ...
%o (MATLAB)
%o function [res] = calcLinks(n,k)
%o if k==1
%o res=n;
%o else
%o d=divisors(n);
%o res=0;
%o for i=1:length(d)
%o if d (i) >= k
%o res=res+eulerPhi(n/d(i))*fiboExt(d(i)-k-1);
%o end
%o end
%o end
%o function [s] = fiboExt(m) % extended fibonacci function (including negative arguments)
%o m=sym(m); % for large fibonacci numbers
%o if m>=0 || mod(m,2)==1
%o s=fibonacci(abs(m));
%o else
%o s=fibonacci(abs(m))*(-1);
%o end
%o (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
%Y Cf. A000010, A000027, A000045, A000358, A113166, A034748.
%K nonn,tabl
%O 0,2
%A _Maxim Karimov_ and Vladislav Sulima, Aug 28 2021
|
