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

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

Offset: 1

Author

N. J. A. Sloane, Dec 25 2018

Keywords

• nonn
• tabl

Comments

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

Examples

			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;
  ...
From _Petros Hadjicostas_, Jan 16 2019: (Start)
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).
This, however, is not the j-th 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_{d|n} 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)
		

References

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

Links

• Freddy Barrera, Rows n = 1..100 of triangle, flattened.
• Miklos Bona, Handbook of Enumerative Combinatorics, CRC Press, 2015, annotated scan of page 520.
• P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Crossrefs

Rows 2, 3, 4 and 5 are A000358, A093305, A280218, A280303.

The rows converge to A008965.

Cf. A119458.

Programs

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

SageMath

# uses the L method from A125127
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

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/(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