Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
A069429
Half the number of 3 X n binary arrays with no path of adjacent 1's or adjacent 0's from top row to bottom row.
94
3, 16, 84, 440, 2304, 12064, 63168, 330752, 1731840, 9068032, 47480832, 248612864, 1301753856, 6816071680, 35689414656, 186872201216, 978475548672, 5123364487168, 26826284728320, 140464250421248, 735480363614208, 3851025180000256, 20164229625544704, 105581277033267200
OFFSET
1,1
FORMULA
Empirical G.f.: x*(3-2*x)/(1-6*x+4*x^2). - Colin Barker, Feb 22 2012
Empirical: a(n) = 3*A084326(n) - 2*A084326(n-1). - R. J. Mathar, Nov 09 2018
From Andrew Howroyd, Oct 27 2020: (Start)
The above conjectures are true and follow from formulas given in A069361 and A069396.
a(n) = (8^n)/2 - A069361(n) + A069396(n).
a(n) = 2^(n-1)*Fibonacci(2*n+2) = A084326(n+1)/2. (End)
EXAMPLE
From Andrew Howroyd, Oct 27 2020: (Start)
Some of the 2*a(2) = 32 arrays are:
0 0 0 0 0 0 0 1 0 1 0 0 0 1
0 0 0 1 1 1 1 0 1 0 1 1 1 0
1 1 1 1 1 1 1 1 0 1 0 0 1 1
(End)
MATHEMATICA
LinearRecurrence[{6, -4}, {3, 16}, 100] (* Jean-François Alcover, Nov 01 2020 *)
PROG
(PARI) Vec((3 - 2*x)/(1 - 6*x + 4*x^2) + O(x^30)) \\ Andrew Howroyd, Oct 27 2020
(PARI) a(n) = 2^(n-1)*fibonacci(2*n+2) \\ Andrew Howroyd, Oct 27 2020
CROSSREFS
Cf. 2 X n A000079, n X 1 A000225, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.
Cf. A084326.
Sequence in context: A041707 A037584 A030983 * A275402 A026131 A026160
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Mar 22 2002
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Oct 27 2020
STATUS
approved