

A322057


Array read by upwards antidiagonals: T(i,n) is the number of binary necklaces of length n that avoid 00...0 (i 0's).


2



1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 2, 3, 4, 3, 1, 1, 2, 3, 5, 5, 5, 1, 1, 2, 3, 5, 6, 9, 5, 1, 1, 2, 3, 5, 7, 11, 11, 8, 1, 1, 2, 3, 5, 7, 12, 15, 19, 10, 1, 1, 2, 3, 5, 7, 13, 17, 27, 29, 15, 1, 1, 2, 3, 5, 7, 13, 18, 31, 43, 48, 19, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

1


REFERENCES

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 520.


LINKS



FORMULA

T(i,n) = (1/n) * Sum_{d divides n} totient(n/d)*L(i,d), where L(i,d) = A125127(i,d). See Zhang and Hadjicostas link.  Freddy Barrera, Jan 15 2019
G.f. for row i: Sum_{k>=1} (phi(k)/k) * log(1/(1B(i, x^k))) where B(i, x) = x*(1 + x + x^2 + ... + x^(i1)). (This is a generalization of Joerg Arndt's formulae for the g.f.'s of rows 2 and 3.)  Petros Hadjicostas, Jan 24 2019


EXAMPLE

The first few antidiagonals are:
1;
1, 1;
1, 2, 1;
1, 2, 2, 1;
1, 2, 3, 3, 1;
1, 2, 3, 4, 3, 1;
1, 2, 3, 5, 5, 5, 1;
1, 2, 3, 5, 6, 9, 5, 1;
1, 2, 3, 5, 7, 11, 11, 8, 1;
1, 2, 3, 5, 7, 12, 15, 19, 10, 1;
...
In the above triangle (first few antidiagonals, read upwards), the jth row corresponds to T(j,1), T(j1,2), T(j2,3), ..., T(1,j).
This, however, is not the jth row of the square array (see the scanned page above).
For example, the sixth row of the square array is as follows:
T(6,1) = 1, T(6,2) = 2, T(6,3) = 3, T(6,4) = 5, T(6, 5) = 7, T(6, 6) = 13, ...
To generate these numbers, we use T(6, n) = (1/n)*Sum_{dn} phi(n/d)*L(6,d), where
L(6,1) = 1, L(6,2) = 3, L(6,3) = 7, L(6,4) = 15, L(6,5) = 31, L(6,6) = 63, ...
See the sixth row of A125127. See also the Sage program below by Freddy Barrera.
(End)


PROG

def T(i, n):
return sum(euler_phi(n//d)*L(i, d) for d in n.divisors()) // n
[T(i, n) for d in (1..12) for i, n in zip((d..1, step=1), (1..d))] # Freddy Barrera, Jan 15 2019


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



