|
|
A051736
|
|
Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column.
|
|
9
|
|
|
1, 5, 17, 63, 227, 827, 2999, 10897, 39561, 143677, 521721, 1894607, 6879979, 24983923, 90725999, 329460929, 1196397873, 4344577397, 15776816033, 57291635519, 208047769363, 755500774443, 2743511349031, 9962735709201, 36178491743225, 131377896967213, 477083233044745
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Also the number of independent vertex sets and vertex covers in the 3 X n grid graph. - Eric W. Weisstein, Sep 21 2017
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*a(n-1) + 6*a(n-2) - a(n-4).
|
|
EXAMPLE
|
There are five 3 X 1 (0,1)-matrices with no consecutive 1's:
0 0 0
0 0 1
0 1 0
1 0 0
1 0 1
There are 17 3 X 2 (0,1)-matrices with no consecutive 1's:
0 0, 0 1, 0 0, 0 0, 0 1, 1 0, 1 0, 1 0, 0 0, 0 1, 0 0, 0 1, 0 0, 0 1, 0 0, 1 0, 1 0
0 0, 0 0, 0 1, 0 0, 0 0, 0 0, 0 1, 0 0, 1 0, 1 0, 1 0, 1 0, 0 0, 0 0, 0 1, 0 0, 0 1
0 0, 0 0, 0 0, 0 1, 0 1, 0 0, 0 0, 0 1, 0 0, 0 0, 0 1, 0 1, 1 0, 1 0, 1 0, 1 0, 1 0
|
|
MATHEMATICA
|
LinearRecurrence[{2, 6, 0, -1}, {1, 5, 17, 63}, 40] (* Harvey P. Dale, Mar 05 2013 *)
CoefficientList[Series[(1 + 3 x + x^2 - x^3)/(1 - 2 x - 6 x^2 + x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
Table[-RootSum[1 - 6 #1^2 - 2 #1^3 + #1^4 &, 263 #1^n - 657 #1^(n + 1) - 331 #1^(n + 2) + 81 #1^(n + 3) &]/1994, {n, 0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)
|
|
PROG
|
(Haskell)
a051736 n = a051736_list !! (n-1)
a051736_list = 1 : 5 : 17 : 63 : zipWith (-) (map (* 2) $ drop 2 $
zipWith (+) (map (* 3) a051736_list) (tail a051736_list)) a051736_list
(PARI) Vec((1+3*x+x^2-x^3)/(1-2*x-6*x^2+x^4)+O(x^50)) \\ Michel Marcus, Sep 17 2014
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,nice,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|