OFFSET
1,1
COMMENTS
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]).
LINKS
Nathaniel Johnston, Table of n, a(n) for n = 1..400
Index entries for linear recurrences with constant coefficients, signature (7,-18,20,-8).
FORMULA
a(P, N) = 1 + Sum_{n=1..N, p=1..P} (C(N, n) * C(P, p) * K(p, n)),
where:
C(i, j) = binomial(i,j),
K(p, n) = Sum_{i=1..n} (T(p, n, i)),
T(1, n, 1) = 1,
T(1, n, i) = 0, for i > 1,
T(p, n, i) = Sum_{j=i..n, k=1..i} T(p-1, j, k).
a(n) = (n^2 + 3*n + 16)*2^(n - 3) - 1. - Vaclav Kotesovec, Aug 15 2013
From Colin Barker, Sep 10 2017: (Start)
G.f.: x*(4 - 16*x + 21*x^2 - 8*x^3) / ((1 - x)*(1 - 2*x)^3).
a(n) = 7*a(n-1) - 18*a(n-2) + 20*a(n-3) - 8*a(n-4) for n>4.
(End)
MAPLE
A:=proc(P, N)return 1+add(add(binomial(N, n)*binomial(P, p)*K(p, n), p=1..P), n=1..N):end:
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:
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:
seq(A(2, n), n=1..20); # Nathaniel Johnston, Apr 13 2011
MATHEMATICA
Table[(n^2 + 3*n + 16)*2^(n-3) - 1, {n, 1, 30}] (* Vaclav Kotesovec, Aug 15 2013 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Pascal Prea (pascal.preq(AT)lim.univ-mrs.fr), Apr 18 2002
EXTENSIONS
Edited by N. J. A. Sloane, Jan 25 2011
a(10)-a(29) and corrected recurrence from Nathaniel Johnston, Apr 13 2011
STATUS
approved