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

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, 1, 5, 10, 13, 10, 3, 0, 0, 0, 0, 0, 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

Offset: 1

Author

Petros Hadjicostas, Dec 07 2017

Keywords

• nonn
• tabl

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

Examples

			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
		

Links

• P. Hadjicostas, Cyclic, dihedral and symmetrical Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

Crossrefs

Row sums are in A106369.

Cf. A003242, A239327, A291941, A293595.

Programs

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 *)

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