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

%I #23 Sep 08 2022 08:45:11

%S 6,36,102,216,390,636,966,1392,1926,2580,3366,4296,5382,6636,8070,

%T 9696,11526,13572,15846,18360,21126,24156,27462,31056,34950,39156,

%U 43686,48552,53766,59340,65286,71616,78342,85476,93030,101016,109446,118332

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

%H Vincenzo Librandi, <a href="/A086113/b086113.txt">Table of n, a(n) for n = 1..1000</a>

%H Don Coppersmith, <a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/March2004.html">Ponder This: IBM Research Monthly Puzzles, March challenge</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).

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

%F G.f.: 6*x*(1 + 2*x - x^2)/(1-x)^4. - _Vincenzo Librandi_, Jun 24 2012

%F a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - _Vincenzo Librandi_, Jun 24 2012

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

%o (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

%Y Cf. A032260, A016742, A086114, A086115.

%K nonn,easy

%O 1,1

%A _Vladimir Baltic_, _Vladeta Jovovic_, Jul 10 2003