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

%I #15 Jun 17 2017 03:53:50

%S 10,100,390,1080,2470,4980,9170,15760,25650,39940,59950,87240,123630,

%T 171220,232410,309920,406810,526500,672790,849880,1062390,1315380,

%U 1614370,1965360,2374850,2849860,3397950,4027240,4746430,5564820

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

%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_06">Index entries for linear recurrences with constant coefficients</a>, signature (6,-15,20,-15,6,-1).

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

%F G.f.: -10*x*(x^4-4*x^3+6*x^2-4*x-1) / (x-1)^6. [_Colin Barker_, Feb 22 2013]

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

%K nonn,easy

%O 1,1

%A _Vladimir Baltic_, _Vladeta Jovovic_, Jul 10 2003