cp's OEIS Frontend

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

%I A296167 #56 Jul 26 2020 07:42:55
%S A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 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 A296167 Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins:
%e A296167   1;
%e A296167   1,  0;
%e A296167   1,  1,  0;
%e A296167   1,  1,  0,  0;
%e A296167   1,  2,  0,  0,  0;
%e A296167   1,  2,  2,  1,  0,  0;
%e A296167   1,  3,  2,  1,  0,  0,  0;
%e A296167   1,  3,  4,  3,  0,  0,  0,  0;
%e A296167   1,  4,  6,  4,  2,  1,  0,  0,  0;
%e A296167   1,  4,  8, 11,  4,  1,  0,  0,  0,  0;
%e A296167   ...
%e A296167 Case n=6:
%e A296167 The included circular compositions are:
%e A296167 k=1: 6;                                => T(6,1) = 1
%e A296167 k=2: 15, 24;                           => T(6,2) = 2
%e A296167 k=3: 123, 321;                         => T(6,3) = 2
%e A296167 k=4: 1212;                             => T(6,4) = 1
%e A296167 k=5: none;                             => T(6,5) = 0
%e A296167 k=6: none;                             => T(6,6) = 0
%t A296167 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 A296167 A293595[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
%t A296167 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 A296167 Table[T[n, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 26 2020 *)
%Y A296167 Row sums are in A106369.
%Y A296167 Cf. A003242, A239327, A291941, A293595.
%K A296167 nonn,tabl
%O A296167 1,12
%A A296167 _Petros Hadjicostas_, Dec 07 2017