|
%I #111 Jan 16 2024 13:16:48
%S 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 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 29,15,1,1,2,3,5,7,13,18,31,43,48,19,1
%N 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 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 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 520.
%H Freddy Barrera, <a href="/A322057/b322057.txt">Rows n = 1..100 of triangle, flattened</a>.
%H Miklos Bona, <a href="/A322057/a322057.png">Handbook of Enumerative Combinatorics</a>, CRC Press, 2015, annotated scan of page 520.
%H 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 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 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 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 The first few antidiagonals are:
%e 1;
%e 1, 1;
%e 1, 2, 1;
%e 1, 2, 2, 1;
%e 1, 2, 3, 3, 1;
%e 1, 2, 3, 4, 3, 1;
%e 1, 2, 3, 5, 5, 5, 1;
%e 1, 2, 3, 5, 6, 9, 5, 1;
%e 1, 2, 3, 5, 7, 11, 11, 8, 1;
%e 1, 2, 3, 5, 7, 12, 15, 19, 10, 1;
%e ...
%e From _Petros Hadjicostas_, Jan 16 2019: (Start)
%e 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 This, however, is not the j-th row of the square array (see the scanned page above).
%e For example, the sixth row of the square array is as follows:
%e 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 To generate these numbers, we use T(6, n) = (1/n)*Sum_{d|n} phi(n/d)*L(6,d), where
%e 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 See the sixth row of A125127. See also the Sage program below by Freddy Barrera.
%e (End)
%o (SageMath) # uses the L method from A125127
%o def T(i, n):
%o return sum(euler_phi(n//d)*L(i, d) for d in n.divisors()) // n
%o [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 (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 Rows 2, 3, 4 and 5 are A000358, A093305, A280218, A280303.
%Y The rows converge to A008965.
%Y Cf. A119458.
%K nonn,tabl
%O 1,5
%A _N. J. A. Sloane_, Dec 25 2018
|
