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,5

Comments

Compositions of length 1 are included.

See theorem 4 in Hadjicostas reference for generating function.

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.

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

Example

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

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

Prog

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

Crossrefs

Row sums are in A212322.

Cf. A106351, A106369.

Sequence in context: A079644 A072705 A072574 * A261249 A058650 A112177

Adjacent sequences: A293592 A293593 A293594 * A293596 A293597 A293598

Keyword

nonn,tabl

Author

Andrew Howroyd, Oct 12 2017

Status

approved