|
%I #56 Jul 26 2020 07:42:55
%S 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,
%T 0,0,1,4,6,4,2,1,0,0,0,1,4,8,11,4,1,0,0,0,0,1,5,10,13,10,3,0,0,0,0,0,
%U 1,5,14,22,18,10,2,1,0,0,0,0,1,6,16,29,32,20,6,1,0,0,0,0,0,1,6,20,44,50,40,18,4,0,0,0,0,0,0
%N Triangle read by rows: T(n,k) is the number of circular compositions of n with length k such that no two adjacent parts are equal (1 <= k <= n).
%C 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".
%C 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).
%C 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).
%H P. Hadjicostas,<a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Hadjicostas/hadji5.html"> Cyclic, dihedral and symmetrical Carlitz compositions of a positive integer</a>, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
%F 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.
%F 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).
%F 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)).
%e Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins:
%e 1;
%e 1, 0;
%e 1, 1, 0;
%e 1, 1, 0, 0;
%e 1, 2, 0, 0, 0;
%e 1, 2, 2, 1, 0, 0;
%e 1, 3, 2, 1, 0, 0, 0;
%e 1, 3, 4, 3, 0, 0, 0, 0;
%e 1, 4, 6, 4, 2, 1, 0, 0, 0;
%e 1, 4, 8, 11, 4, 1, 0, 0, 0, 0;
%e ...
%e Case n=6:
%e The included circular compositions are:
%e k=1: 6; => T(6,1) = 1
%e k=2: 15, 24; => T(6,2) = 2
%e k=3: 123, 321; => T(6,3) = 2
%e k=4: 1212; => T(6,4) = 1
%e k=5: none; => T(6,5) = 0
%e k=6: none; => T(6,6) = 0
%t 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;
%t A293595[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
%t 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]]}];
%t Table[T[n, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 26 2020 *)
%Y Row sums are in A106369.
%Y Cf. A003242, A239327, A291941, A293595.
%K nonn,tabl
%O 1,12
%A _Petros Hadjicostas_, Dec 07 2017
|
