A368809 Number of 4 X n binary arrays with a path of adjacent 1's from top row to bottom row using only left, right, and downward steps.

1, 41, 1041, 22193, 433801, 8057625, 144762849, 2540882465, 43840779353, 746649798473, 12587443678705, 210491254232465, 3496816762316713, 57778098654714361, 950391251581267073, 15574198350636963201, 254405750326548970361, 4144508602760970898729, 67361936661916258817937

Offset

1,2

Comments

Unlike A069362, does not allow upward steps.

Links

Table of n, a(n) for n=1..19.

Index entries for linear recurrences with constant coefficients, signature (36,-413,1642,-2536,1152).

Formula

G.f.: x*(1 + 5*x - 22*x^2 + 8*x^3)/((1 - 16*x)*(1 - 20*x + 93*x^2 - 154*x^3 + 72*x^4)). - Pontus von Brömssen, Feb 05 2025

Example

For example, here is one such 4 X 4 array:
    0001
    1111
    1010
    1100
The following 4 X 5 array is a non-example, as there is no path using only left, right, and downward steps:
    10000
    10111
    11101
    00001

Crossrefs

Row 4 of A369892.

Cf. A069362, A359576.

Sequence in context: A104349 A091314 A059762 * A069362 A016093 A358713

Adjacent sequences: A368806 A368807 A368808 * A368810 A368811 A368812

Keyword

nonn,easy

Author

Caleb Stanford, Feb 05 2024

Extensions

More terms from Pontus von Brömssen, Feb 05 2025

Status

approved