OFFSET
1,12
COMMENTS
By "circular compositions" here we mean equivalence classes of compositions with parts on a circle such that two compositions are equivalent if one is a cyclic shift of the other. We may call them "circular Carlitz compositions".
The formula below for T(n,k) involves indicator functions of conditions because unfortunately circular compositions of length 1 are considered Carlitz by most authors (even though, strictly speaking, they are not since the single number in such a composition is "next to itself" if we go around the circle).
To prove that the two g.f.'s below are equal to each other, use the geometric series formula, change the order of summations where it is necessary, and use the result Sum_{n >= 1} (phi(n)/n)*log(1 + x^n) = Sum_{n >= 1} (phi(n)/n)*log(1 - x^(2*n)) - Sum_{n >= 1} (phi(n)/n)*log(1 - x^n) = -x^2/(1 - x^2) + x/(1 - x) = x/(1 - x^2).
LINKS
P. Hadjicostas, Cyclic, dihedral and symmetrical Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
FORMULA
T(n,k) = [k = 1] + (1/k)*Sum_{d | gcd(n,k)} phi(d)*A293595(n/d, k/d) * [k/d <> 1], where [ ] is the Iverson Bracket.
G.f.: Sum_{n,k >= 1} T(n,k)*x^n*y^k = x*y/(1-x) - Sum_{s>=1} (phi(s)/s)*f(x^s,y^s), where f(x,y) = log(1 - Sum_{n >= 1} x^n*y/(1 + x^n*y)) + Sum_{n >= 1} log(1 + x^n*y).
G.f.: -Sum_{s >= 1} (x*y)^(2*s + 1)/(1-x^(2*s + 1)) - Sum_{s >= 1} (phi(s)/s)*g(x^s,y^s), where g(x,y) = log(1 + Sum_{n >= 1} (-x*y)^n/(1 - x^n)).
EXAMPLE
Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins:
1;
1, 0;
1, 1, 0;
1, 1, 0, 0;
1, 2, 0, 0, 0;
1, 2, 2, 1, 0, 0;
1, 3, 2, 1, 0, 0, 0;
1, 3, 4, 3, 0, 0, 0, 0;
1, 4, 6, 4, 2, 1, 0, 0, 0;
1, 4, 8, 11, 4, 1, 0, 0, 0, 0;
...
Case n=6:
The included circular compositions are:
k=1: 6; => T(6,1) = 1
k=2: 15, 24; => T(6,2) = 2
k=3: 123, 321; => T(6,3) = 2
k=4: 1212; => T(6,4) = 1
k=5: none; => T(6,5) = 0
k=6: none; => T(6,6) = 0
MATHEMATICA
nmax = 14; gf (* of A293595 *) = Sum[x^(2j) y^2/(1 + x^j y), {j, 1, nmax}] + Sum[x^j y/(1 + x^j y)^2, {j, 1, nmax}]/(1 - Sum[x^j y/(1 + x^j y), {j, 1, nmax}]) + O[x]^(nmax + 1) + O[y]^(nmax + 1) // Normal // Expand;
A293595[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
T[n_, k_] := Boole[k == 1] + (1/k) Sum[EulerPhi[d] A293595[n/d, k/d]* Boole[k/d != 1], {d, Divisors[GCD[n, k]]}];
Table[T[n, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2020 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Petros Hadjicostas, Dec 07 2017
STATUS
approved