A086115 -id:A086115 - cp's OEIS frontend

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

Vladimir Baltic, Vladeta Jovovic, Jul 10 2003

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

Cf. A032260, A016742, A086114, A086115.

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

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

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

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

Original entry on oeis.org

2, 16, 102, 528, 2470, 11016, 47950, 205792, 874998, 3694920, 15519262, 64899456, 270415262, 1123264408, 4653525150, 19234571968, 79342610902, 326704870152, 1343120023678, 5513861152000, 22606830725598, 92580354402712, 378737813468542, 1547884976787648

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Jun 25 2003

nonn

Eric M. Schmidt, Table of n, a(n) for n = 1..1000
Don Coppersmith, Ponder This: IBM Research Monthly Puzzles, March 2004 challenge

The number of n X n 0, 1 matrices such that each row and each column is increasing is in sequence A000984.

Cf. A000984, A062528, A045992, A016742, A086113 - A086115.

a(n) = 2*n*(binomial(2*n, n)-n). G.f.: 4*x/(1-4*x)^(3/2)-2*x*(1+x)/(1-x)^3. - Vladimir Baltic and Vladeta Jovovic, Jul 10 2003

Extended by Vladimir Baltic and Vladeta Jovovic, Jul 10 2003

More terms from Eric M. Schmidt, May 01 2013

A202052 T(n,k)=Number of (n+2)X(k+2) binary arrays avoiding patterns 001 and 110 in rows and columns.

Original entry on oeis.org

102, 216, 216, 390, 528, 390, 636, 1080, 1080, 636, 966, 1968, 2470, 1968, 966, 1392, 3304, 4980, 4980, 3304, 1392, 1926, 5216, 9170, 11016, 9170, 5216, 1926, 2580, 7848, 15760, 22092, 22092, 15760, 7848, 2580, 3366, 11360, 25650, 41088, 47950, 41088

Offset: 1

R. H. Hardin Dec 10 2011

Table starts
..102...216...390....636....966....1392....1926.....2580.....3366.....4296
..216...528..1080...1968...3304....5216....7848....11360....15928....21744
..390..1080..2470...4980...9170...15760...25650....39940....59950....87240
..636..1968..4980..11016..22092...41088...71964...120000...192060...296880
..966..3304..9170..22092..47950...95984..180054...320180...544390...890904
.1392..5216.15760..41088..95984..205792..411696...777760..1400080..2418432
.1926..7848.25650..71964.180054..411696..874998..1750140..3325410..6046344
.2580.11360.39940.120000.320180..777760.1750140..3694920..7390020.14108400
.3366.15928.59950.192060.544390.1400080.3325410..7390020.15519262.31038744
.4296.21744.87240.296880.890904.2418432.6046344.14108400.31038744.64899456

			Some solutions for n=5 k=3
..0..0..0..0..0....1..0..1..1..1....0..1..0..1..1....0..1..0..1..1
..1..1..1..1..1....0..1..0..0..0....1..0..1..0..0....1..0..0..0..0
..0..0..0..0..0....1..0..1..1..1....0..1..0..1..0....0..1..0..1..1
..0..1..1..1..1....0..0..0..0..0....0..0..0..0..0....1..0..0..0..0
..0..1..0..0..0....1..0..1..1..1....0..1..0..1..0....0..1..0..1..1
..0..1..0..1..1....0..0..0..0..0....0..1..0..1..0....0..0..0..0..0
..0..1..0..1..0....1..0..1..0..0....0..1..0..1..0....0..1..0..1..0

R. H. Hardin, Table of n, a(n) for n = 1..511

Column 1 is A086113(n+2)
Column 2 is A086114(n+2)
Column 3 is A086115(n+2)
Diagonal is A032260(n+2)

Empirical (via A086113): T(n,k)=2*(n+2)*(2*binomial(n+k+3,n+2)-k-2)
Empirical for columns:
T(n,1) = 2*n^3 + 18*n^2 + 46*n + 36
T(n,2) = (2/3)*n^4 + (28/3)*n^3 + (142/3)*n^2 + (284/3)*n + 64
T(n,3) = (1/6)*n^5 + (10/3)*n^4 + (155/6)*n^3 + (290/3)*n^2 + 164*n + 100
T(n,4) = (1/30)*n^6 + (9/10)*n^5 + (59/6)*n^4 + (111/2)*n^3 + (2552/15)*n^2 + (1278/5)*n + 144
T(n,5) = (1/180)*n^7 + (7/36)*n^6 + (511/180)*n^5 + (805/36)*n^4 + (4606/45)*n^3 + (2443/9)*n^2 + (1854/5)*n + 196
T(n,6) = (1/1260)*n^8 + (11/315)*n^7 + (59/90)*n^6 + (308/45)*n^5 + (7807/180)*n^4 + (7667/45)*n^3 + (14139/35)*n^2 + (17876/35)*n + 256
T(n,7) = (1/10080)*n^9 + (3/560)*n^8 + (211/1680)*n^7 + (67/40)*n^6 + (6709/480)*n^5 + (6041/80)*n^4 + (663941/2520)*n^3 + (79913/140)*n^2 + (4735/7)*n + 324

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

Original entry on oeis.org

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

Vladimir Baltic, Vladeta Jovovic, Jul 10 2003

Don Coppersmith, Ponder This: IBM Research Monthly Puzzles, March 2004 challenge
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A032260, A016742, A086113, A086115.

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]

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A202052 T(n,k)=Number of (n+2)X(k+2) binary arrays avoiding patterns 001 and 110 in rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula