|
|
A225034
|
|
a(n) is the number of binary words containing n 1's and at most n 0's that do not contain the substring 101.
|
|
3
|
|
|
1, 3, 7, 18, 48, 131, 363, 1017, 2873, 8169, 23349, 67024, 193086, 557949, 1616501, 4694034, 13657896, 39809649, 116218701, 339762942, 994553160, 2914608177, 8550424953, 25107964077, 73793368593, 217057617567, 638936722403, 1882096946232, 5547613247418, 16361808691243
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of weakly increasing words of length n+1 with n+2 letters such that no up-step is by 1, see example. - Joerg Arndt, Jun 10 2013
|
|
LINKS
|
|
|
FORMULA
|
Theorem: G.f. = 2*(1-x^2)/(3*x^2-4*x+1+sqrt((1-x^2)^2-4*(x-x^2)*(1-x^2))).
Conjecture: (n+1)*a(n) - (2*n+3)*a(n-1) - 3*(n-2)*a(n-2) = 0 for n>1. - Bruno Berselli, May 02 2013
|
|
EXAMPLE
|
The binary words having two 1's (n=2) and at most two 0's and which do not have 101 as a substring are:
01: 11,
02: 1001,
03: 011,
04: 0110,
05: 110,
06: 1100,
07: 0011,
therefore a(2)=7.
The binary words having three 1's (n=3) and at most three 0's and which do not have 101 as a substring are:
01: 111,
02: 1110,
03: 0111,
04: 11100,
05: 11001,
06: 10011,
07: 00111,
08: 01110,
09: 111000,
10: 110001,
11: 100011,
12: 000111,
13: 011100,
14: 001110,
15: 010011,
16: 011001,
17: 100110,
18: 110010,
therefore a(3)=18.
There are a(3)=18 weakly increasing length-4 words of 5 letters (0,1,2,3,4) with no up-step by 1:
01: [ 0 0 0 ]
02: [ 0 0 2 ]
03: [ 0 0 3 ]
04: [ 0 0 4 ]
05: [ 0 2 2 ]
06: [ 0 2 4 ]
07: [ 0 3 3 ]
08: [ 0 4 4 ]
09: [ 1 1 1 ]
10: [ 1 1 3 ]
11: [ 1 1 4 ]
12: [ 1 3 3 ]
13: [ 1 4 4 ]
14: [ 2 2 2 ]
15: [ 2 2 4 ]
16: [ 2 4 4 ]
17: [ 3 3 3 ]
18: [ 4 4 4 ]
(End)
|
|
MATHEMATICA
|
CoefficientList[Series[2 (1 - x^2)/(3 x^2 - 4 x + 1 + Sqrt[(1 - x^2)^2 - 4 (x - x^2) (1 - x^2)]), {x, 0, 30}], x] (* Bruno Berselli, May 02 2013 *)
|
|
PROG
|
(PARI) x='x+O('x^66); Vec((2*(1-x^2))/(3*x^2-4*x+1+sqrt((1-x^2)^2-4*(x-x^2)*(1-x^2)))) \\ Joerg Arndt, May 02 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|