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
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, Dec 25 2018
STATUS
approved