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.

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)).

Links

Table of n, a(n) for n=0..90.

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

Cf. A000010, A000027, A000045, A000358, A113166, A034748.

Sequence in context: A158951 A126988 A280499 * A355342 A130026 A113287

Adjacent sequences: A347348 A347349 A347350 * A347352 A347353 A347354

Keyword

nonn,tabl

Author

Maxim Karimov and Vladislav Sulima, Aug 28 2021

Status

approved