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,1

Links

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

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).

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]

Crossrefs

Cf. A032260, A016742, A086113, A086114.

Sequence in context: A208024 A207804 A060522 * A209652 A207072 A207405

Adjacent sequences: A086112 A086113 A086114 * A086116 A086117 A086118

Keyword

nonn,easy

Author

Vladimir Baltic, Vladeta Jovovic, Jul 10 2003

Status

approved