A086114 Number of 4 X n (0,1) matrices such that each row and each column is nondecreasing or nonincreasing.

8, 64, 216, 528, 1080, 1968, 3304, 5216, 7848, 11360, 15928, 21744, 29016, 37968, 48840, 61888, 77384, 95616, 116888, 141520, 169848, 202224, 239016, 280608, 327400, 379808, 438264, 503216, 575128, 654480, 741768, 837504, 942216, 1056448

Offset: 1

Author

Vladimir Baltic, Vladeta Jovovic, Jul 10 2003

Keywords

• nonn
• easy

Links

• Don Coppersmith, Ponder This: IBM Research Monthly Puzzles, March 2004 challenge
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Crossrefs

Cf. A032260, A016742, A086113, A086115.

Formula

a(n) = (2/3)*n*(n^3+6*n^2+11*n-6). More generally, number of m X n (0, 1) matrices such that each row and each column is increasing or decreasing is 2*n*(2*binomial(n+m-1, n)-m) = 4/Beta(m, n)-2*m*n.

G.f.: -8*x*(x^3-3*x^2+3*x+1) / (x-1)^5. [Colin Barker, Feb 22 2013]