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
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).
Programs
-
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
-
Mathematica
CoefficientList[Series[6*(1+2x-x^2)/(1-x)^4,{x,0,40}],x] (* Vincenzo Librandi, Jun 24 2012 *)
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