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

Links

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

Don Coppersmith, Ponder This: IBM Research Monthly Puzzles, March challenge

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

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]

Crossrefs

Cf. A032260, A016742, A086113, A086115.

Sequence in context: A207940 A016743 A340695 * A209651 A207071 A117219

Adjacent sequences: A086111 A086112 A086113 * A086115 A086116 A086117

Keyword

nonn,easy

Author

Vladimir Baltic, Vladeta Jovovic, Jul 10 2003

Status

approved