A347351 - OEIS

%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