|
|
A062200
|
|
Number of compositions of n such that two adjacent parts are not equal modulo 2.
|
|
10
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
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.
|
|
REFERENCES
|
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(Problems 2.4.3, 2.4.13).
|
|
LINKS
|
Table of n, a(n) for n=0..44.
Index entries for linear recurrences with constant coefficients, signature (0, 2, 1, -1).
|
|
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
|
|
EXAMPLE
|
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)
|
|
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 *)
|
|
PROG
|
(PARI) x='x+O('x^66); Vec(-(x^2-x-1)/(x^4-x^3-2*x^2+1)) \\ Joerg Arndt, May 13 2013
|
|
CROSSREFS
|
Cf. A003242, A062201-A062203.
Sequence in context: A154028 A157793 A096375 * A114208 A014686 A053090
Adjacent sequences: A062197 A062198 A062199 * A062201 A062202 A062203
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Vladeta Jovovic, Jun 13 2001
|
|
STATUS
|
approved
|
|
|
|