%I #26 Sep 10 2017 07:15:28
%S 4,12,33,87,223,559,1375,3327,7935,18687,43519,100351,229375,520191,
%T 1171455,2621439,5832703,12910591,28442623,62390271,136314879,
%U 296747007,643825663,1392508927,3003121663,6459228159,13857980415,29662117887,63350767615
%N Number of Bottleneck-Monge matrices with 2 rows. In the formula below, P = 2.
%C A Bottleneck-Monge matrix is a {0,1} matrix A in which, for every i < j and k < l, max(A[i,l], A[j,k]) <= max(A[i,k], A[j,l]).
%H Nathaniel Johnston, <a href="/A070050/b070050.txt">Table of n, a(n) for n = 1..400</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-18,20,-8).
%F a(P, N) = 1 + Sum_{n=1..N, p=1..P} (C(N, n) * C(P, p) * K(p, n)),
%F where:
%F C(i, j) = binomial(i,j),
%F K(p, n) = Sum_{i=1..n} (T(p, n, i)),
%F T(1, n, 1) = 1,
%F T(1, n, i) = 0, for i > 1,
%F T(p, n, i) = Sum_{j=i..n, k=1..i} T(p-1, j, k).
%F a(n) = (n^2 + 3*n + 16)*2^(n - 3) - 1. - _Vaclav Kotesovec_, Aug 15 2013
%F From _Colin Barker_, Sep 10 2017: (Start)
%F G.f.: x*(4 - 16*x + 21*x^2 - 8*x^3) / ((1 - x)*(1 - 2*x)^3).
%F a(n) = 7*a(n-1) - 18*a(n-2) + 20*a(n-3) - 8*a(n-4) for n>4.
%F (End)
%p A:=proc(P,N)return 1+add(add(binomial(N,n)*binomial(P,p)*K(p,n),p=1..P),n=1..N):end:
%p K:=proc(p,n)global k:if(not type(k[p,n],integer))then k[p,n]:=add(T(p,n,i),i=1..n):fi:return k[p,n]:end:
%p T:=proc(p,n,i)global t:if(not type(t[p,n,i],integer))then if(p=1 and i=1)then t[p,n,i]:=1:elif(p=1)then t[p,n,i]:=0:else t[p,n,i]:=add(add(T(p-1,j,k),k=1..i),j=i..n):fi:fi:return t[p,n,i]:end:
%p seq(A(2,n), n=1..20); # _Nathaniel Johnston_, Apr 13 2011
%t Table[(n^2 + 3*n + 16)*2^(n-3) - 1, {n, 1, 30}] (* _Vaclav Kotesovec_, Aug 15 2013 *)
%o (PARI) Vec(x*(4 - 16*x + 21*x^2 - 8*x^3) / ((1 - x)*(1 - 2*x)^3) + O(x^40)) \\ _Colin Barker_, Sep 10 2017
%Y Cf. A070051 (P=3), A070052 (P=4), A070053 (P=5), A070054 (P=6), A070055 (P=7), A070054 (P=8), A070057 (P=9).
%K nonn,easy
%O 1,1
%A Pascal Prea (pascal.preq(AT)lim.univ-mrs.fr), Apr 18 2002
%E Edited by _N. J. A. Sloane_, Jan 25 2011
%E a(10)-a(29) and corrected recurrence from _Nathaniel Johnston_, Apr 13 2011