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,5

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

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.

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

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

Prog

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

Crossrefs

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

The rows converge to A008965.

Cf. A119458.

Sequence in context: A323211 A110537 A144434 * A323767 A357824 A159936

Adjacent sequences: A322054 A322055 A322056 * A322058 A322059 A322060

Keyword

nonn,tabl

Author

N. J. A. Sloane, Dec 25 2018

Status

approved