cp's OEIS Frontend

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.

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