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

10, 100, 390, 1080, 2470, 4980, 9170, 15760, 25650, 39940, 59950, 87240, 123630, 171220, 232410, 309920, 406810, 526500, 672790, 849880, 1062390, 1315380, 1614370, 1965360, 2374850, 2849860, 3397950, 4027240, 4746430, 5564820

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 (6,-15,20,-15,6,-1).

Crossrefs

Cf. A032260, A016742, A086113, A086114.

Formula

a(n) = (1/6)*n*(n^4+10*n^3+35*n^2+50*n-36). 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.: -10*x*(x^4-4*x^3+6*x^2-4*x-1) / (x-1)^6. [Colin Barker, Feb 22 2013]