A062200 Number of compositions of n such that two adjacent parts are not equal modulo 2.

1, 1, 1, 3, 2, 6, 6, 11, 16, 22, 37, 49, 80, 113, 172, 257, 377, 573, 839, 1266, 1874, 2798, 4175, 6204, 9274, 13785, 20577, 30640, 45665, 68072, 101393, 151169, 225193, 335659, 500162, 745342, 1110790, 1655187, 2466760, 3675822, 5477917, 8163217, 12164896, 18128529, 27015092

Offset: 0

Author

Vladeta Jovovic, Jun 13 2001

Keywords

• nonn
• easy

Comments

Also (0,1)-strings such that all maximal blocks of 1's have even length and all maximal blocks of 0's have odd length.

Examples

			From _Joerg Arndt_, Oct 27 2012:  (Start)
The 11 such compositions of n=7 are
  [ 1]  1 2 1 2 1
  [ 2]  1 6
  [ 3]  2 1 4
  [ 4]  2 3 2
  [ 5]  2 5
  [ 6]  3 4
  [ 7]  4 1 2
  [ 8]  4 3
  [ 9]  5 2
  [10]  6 1
  [11]  7
The 16 such compositions of n=8 are
  [ 1]  1 2 1 4
  [ 2]  1 2 3 2
  [ 3]  1 2 5
  [ 4]  1 4 1 2
  [ 5]  1 4 3
  [ 6]  1 6 1
  [ 7]  2 1 2 1 2
  [ 8]  2 1 2 3
  [ 9]  2 1 4 1
  [10]  2 3 2 1
  [11]  3 2 1 2
  [12]  3 2 3
  [13]  3 4 1
  [14]  4 1 2 1
  [15]  5 2 1
  [16]  8
(End)
		

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(Problems 2.4.3, 2.4.13).

Links

• Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 19.
• Index entries for linear recurrences with constant coefficients, signature (0,2,1,-1).

Crossrefs

Cf. A003242, A062201, A062202, A062203.

Programs

Mathematica

LinearRecurrence[{0,2,1,-1},{1,1,1,3},50] (* Harvey P. Dale, Feb 26 2012 *)
Join[{1},Table[Sum[ Binomial[n-j+1,3j-n+1],{j,0,n-1}],{n,50}]] (* Harvey P. Dale, Feb 26 2012 *)

PARI

x='x+O('x^66); Vec(-(x^2-x-1)/(x^4-x^3-2*x^2+1)) \\ Joerg Arndt, May 13 2013

Formula

a(n) = Sum_{j=0..n+1} binomial(n-j+1, 3*j-n+1).

a(n) = 2*a(n-2) + a(n-3) - a(n-4).

G.f.: -(x^2-x-1)/(x^4-x^3-2*x^2+1). More generally, g.f. for the number of compositions of n such that two adjacent parts are not equal modulo p is 1/(1-Sum_{i=1..p} x^i/(1+x^i-x^p)).

G.f.: W(0)/(2*x^2) -1/x^2, where W(k) = 1 + 1/(1 - x*(k - x)/( x*(k+1 - x) - 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013