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

6, 36, 102, 216, 390, 636, 966, 1392, 1926, 2580, 3366, 4296, 5382, 6636, 8070, 9696, 11526, 13572, 15846, 18360, 21126, 24156, 27462, 31056, 34950, 39156, 43686, 48552, 53766, 59340, 65286, 71616, 78342, 85476, 93030, 101016, 109446, 118332

Offset

1,1

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

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

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

a(n) = 2*n*(n^2 + 3*n - 1) = 2*n*A014209(n). 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) = 2*m*(2*binomial(m+n-1, m)-n).

G.f.: 6*x*(1 + 2*x - x^2)/(1-x)^4. - Vincenzo Librandi, Jun 24 2012

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 24 2012

Mathematica

CoefficientList[Series[6*(1+2x-x^2)/(1-x)^4, {x, 0, 40}], x] (* Vincenzo Librandi, Jun 24 2012 *)

Prog

(Magma) I:=[6, 36, 102, 216]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..50]]; // Vincenzo Librandi, Jun 24 2012

Crossrefs

Cf. A032260, A016742, A086114, A086115.

Sequence in context: A207392 A207939 A207462 * A207903 A267714 A207747

Adjacent sequences: A086110 A086111 A086112 * A086114 A086115 A086116

Keyword

nonn,easy

Author

Vladimir Baltic, Vladeta Jovovic, Jul 10 2003

Status

approved