login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 0
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,12

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

LINKS

Table of n, a(n) for n=1..105.

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

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

EXAMPLE

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

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

CROSSREFS

Row sums are in A106369.

Cf. A003242, A239327, A291941, A293595.

Sequence in context: A276205 A244966 A079100 * A244233 A227345 A123262

Adjacent sequences:  A296164 A296165 A296166 * A296168 A296169 A296170

KEYWORD

nonn,tabl

AUTHOR

Petros Hadjicostas, Dec 07 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 02:19 EDT 2020. Contains 337164 sequences. (Running on oeis4.)