cp's OEIS Frontend

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

%I A062200 #26 Nov 19 2023 08:25:17
%S A062200 1,1,1,3,2,6,6,11,16,22,37,49,80,113,172,257,377,573,839,1266,1874,
%T A062200 2798,4175,6204,9274,13785,20577,30640,45665,68072,101393,151169,
%U A062200 225193,335659,500162,745342,1110790,1655187,2466760,3675822,5477917,8163217,12164896,18128529,27015092
%N A062200 Number of compositions of n such that two adjacent parts are not equal modulo 2.
%C A062200 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.
%D A062200 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(Problems 2.4.3, 2.4.13).
%H A062200 Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 19.
%H A062200 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,2,1,-1).
%F A062200 a(n) = Sum_{j=0..n+1} binomial(n-j+1, 3*j-n+1).
%F A062200 a(n) = 2*a(n-2) + a(n-3) - a(n-4).
%F A062200 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)).
%F A062200 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
%e A062200 From _Joerg Arndt_, Oct 27 2012:  (Start)
%e A062200 The 11 such compositions of n=7 are
%e A062200   [ 1]  1 2 1 2 1
%e A062200   [ 2]  1 6
%e A062200   [ 3]  2 1 4
%e A062200   [ 4]  2 3 2
%e A062200   [ 5]  2 5
%e A062200   [ 6]  3 4
%e A062200   [ 7]  4 1 2
%e A062200   [ 8]  4 3
%e A062200   [ 9]  5 2
%e A062200   [10]  6 1
%e A062200   [11]  7
%e A062200 The 16 such compositions of n=8 are
%e A062200   [ 1]  1 2 1 4
%e A062200   [ 2]  1 2 3 2
%e A062200   [ 3]  1 2 5
%e A062200   [ 4]  1 4 1 2
%e A062200   [ 5]  1 4 3
%e A062200   [ 6]  1 6 1
%e A062200   [ 7]  2 1 2 1 2
%e A062200   [ 8]  2 1 2 3
%e A062200   [ 9]  2 1 4 1
%e A062200   [10]  2 3 2 1
%e A062200   [11]  3 2 1 2
%e A062200   [12]  3 2 3
%e A062200   [13]  3 4 1
%e A062200   [14]  4 1 2 1
%e A062200   [15]  5 2 1
%e A062200   [16]  8
%e A062200 (End)
%t A062200 LinearRecurrence[{0,2,1,-1},{1,1,1,3},50] (* _Harvey P. Dale_, Feb 26 2012 *)
%t A062200 Join[{1},Table[Sum[ Binomial[n-j+1,3j-n+1],{j,0,n-1}],{n,50}]] (* _Harvey P. Dale_, Feb 26 2012 *)
%o A062200 (PARI) x='x+O('x^66); Vec(-(x^2-x-1)/(x^4-x^3-2*x^2+1)) \\ _Joerg Arndt_, May 13 2013
%Y A062200 Cf. A003242, A062201, A062202, A062203.
%K A062200 nonn,easy
%O A062200 0,4
%A A062200 _Vladeta Jovovic_, Jun 13 2001