A293595 Triangle read by rows: T(n,k) = number of compositions of n into k parts such that no two cyclically adjacent parts are equal.

1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 1, 4, 0, 0, 0, 1, 4, 6, 2, 0, 0, 1, 6, 6, 4, 0, 0, 0, 1, 6, 12, 10, 0, 0, 0, 0, 1, 8, 18, 16, 10, 2, 0, 0, 0, 1, 8, 24, 40, 20, 6, 0, 0, 0, 0, 1, 10, 30, 52, 50, 18, 0, 0, 0, 0, 0, 1, 10, 42, 84, 90, 50, 14, 2, 0, 0, 0, 0

Offset: 1

Author

Andrew Howroyd, Oct 12 2017

Keywords

• nonn
• tabl

Comments

Compositions of length 1 are included.

See theorem 4 in Hadjicostas reference for generating function.

Examples

			Triangle begins:
  1;
  1,  0;
  1,  2,  0;
  1,  2,  0,  0;
  1,  4,  0,  0,  0;
  1,  4,  6,  2,  0,  0;
  1,  6,  6,  4,  0,  0,  0;
  1,  6, 12, 10,  0,  0,  0,  0;
  1,  8, 18, 16, 10,  2,  0,  0,  0;
  1,  8, 24, 40, 20,  6,  0,  0,  0,  0;
  ...
Case n=6:
The included compositions are:
k=1: 6;                                => T(6,1) = 1
k=2: 15, 24, 42, 51;                   => T(6,2) = 4
k=3: 123, 132, 213, 231, 312, 321;     => T(6,3) = 6
k=4: 1212, 2121;                       => T(6,4) = 2
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

Crossrefs

Row sums are in A212322.

Cf. A106351, A106369.

Programs

Mathematica

max = 10; gf = Sum[x^(2*j)*y^2/(1 + x^j*y), {j, 1, max}] + Sum[x^j*y/(1 + x^j*y)^2, {j, 1, max}]/(1 - Sum[ x^j*y/(1 + x^j*y), {j, 1, max}]) + O[x]^(max+1) + O[y]^(max+1) // Normal // Expand;
T[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
Table[T[n, k], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 19 2018 *)

PARI

gf(n,y) = {my(A=sum(j=1, n, x^(2*j)*y^2/(1+x^j*y) + O(x*x^n)),
B=sum(j=1, n, x^j*y/(1+x^j*y)^2 + O(x*x^n)),
C=sum(j=1, n, x^j*y/(1+x^j*y) + O(x*x^n)));
A + B/(1-C)}
for(n=1,10,my(p=polcoeff(gf(n,y),n));for(k=1,n,print1(polcoeff(p,k),", "));print)

Formula

G.f.: (Sum_{j>=1} x^(2*j)*y^2/(1+x^j*y)) + (Sum_{j>=1} x^j*y/(1+x^j*y)^2) / (1 - Sum_{j>=1} x^j*y/(1+x^j*y)).