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

Author

Caleb Stanford, Feb 05 2024

Keywords

• nonn
• easy

Comments

Unlike A069362, does not allow upward steps.

Examples

			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
		

Links

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

Crossrefs

Row 4 of A369892.

Cf. A069362, A359576.

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

Extensions

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