cp's OEIS Frontend

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

%I A322057 #111 Jan 16 2024 13:16:48
%S A322057 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,
%T A322057 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,
%U A322057 29,15,1,1,2,3,5,7,13,18,31,43,48,19,1
%N 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).
%C A322057 T(i,n) is the number of necklace compositions with sum n and parts at most i. For example, the T(3,5) = 5 compositions up to cyclic equivalence are 11111, 1112, 113, 122, 23. - _Andrew Howroyd_, Jan 08 2024
%D A322057 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 520.
%H A322057 Freddy Barrera, <a href="/A322057/b322057.txt">Rows n = 1..100 of triangle, flattened</a>.
%H A322057 Miklos Bona, <a href="/A322057/a322057.png">Handbook of Enumerative Combinatorics</a>, CRC Press, 2015, annotated scan of page 520.
%H A322057 P. Flajolet and M. Soria, <a href="http://dx.doi.org/10.1137/0404006">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H A322057 L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%F A322057 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
%F A322057 G.f. for row i: Sum_{k>=1} (phi(k)/k) * log(1/(1-B(i, x^k))) where B(i, x) = x*(1 + x + x^2 + ... + x^(i-1)). (This is a generalization of Joerg Arndt's formulae for the g.f.'s of rows 2 and 3.) - _Petros Hadjicostas_, Jan 24 2019
%e A322057 The first few antidiagonals are:
%e A322057   1;
%e A322057   1,  1;
%e A322057   1,  2,  1;
%e A322057   1,  2,  2,  1;
%e A322057   1,  2,  3,  3,  1;
%e A322057   1,  2,  3,  4,  3,  1;
%e A322057   1,  2,  3,  5,  5,  5,  1;
%e A322057   1,  2,  3,  5,  6,  9,  5,  1;
%e A322057   1,  2,  3,  5,  7, 11, 11,  8,  1;
%e A322057   1,  2,  3,  5,  7, 12, 15, 19, 10,  1;
%e A322057   ...
%e A322057 From _Petros Hadjicostas_, Jan 16 2019: (Start)
%e A322057 In the above triangle (first few antidiagonals, read upwards), the j-th row corresponds to T(j,1), T(j-1,2), T(j-2,3), ..., T(1,j).
%e A322057 This, however, is not the j-th row of the square array (see the scanned page above).
%e A322057 For example, the sixth row of the square array is as follows:
%e A322057 T(6,1) = 1, T(6,2) = 2, T(6,3) = 3, T(6,4) = 5, T(6, 5) = 7, T(6, 6) = 13, ...
%e A322057 To generate these numbers, we use T(6, n) = (1/n)*Sum_{d|n} phi(n/d)*L(6,d), where
%e A322057 L(6,1) = 1, L(6,2) = 3, L(6,3) = 7, L(6,4) = 15, L(6,5) = 31, L(6,6) = 63, ...
%e A322057 See the sixth row of A125127. See also the Sage program below by Freddy Barrera.
%e A322057 (End)
%o A322057 (SageMath) # uses the L method from A125127
%o A322057 def T(i, n):
%o A322057     return sum(euler_phi(n//d)*L(i, d) for d in n.divisors()) // n
%o A322057 [T(i, n) for d in (1..12) for i, n in zip((d..1, step=-1), (1..d))] # _Freddy Barrera_, Jan 15 2019
%o A322057 (PARI) T(i,n) = {my(p=1/(1 - x*(1 - x^i)/(1 - x))); polcoef(sum(d=1, n, eulerphi(d)*log(subst(p + O(x*x^(n\d)), x, x^d))/d), n)} \\ _Andrew Howroyd_, Jan 08 2024
%Y A322057 Rows 2, 3, 4 and 5 are A000358, A093305, A280218, A280303.
%Y A322057 The rows converge to A008965.
%Y A322057 Cf. A119458.
%K A322057 nonn,tabl
%O A322057 1,5
%A A322057 _N. J. A. Sloane_, Dec 25 2018