A114715 Number A(n,m) of linear extensions of a 2 X n X m lattice; square array A(n,m), n>=1, m>=1, read by antidiagonals.

1, 2, 2, 5, 48, 5, 14, 2452, 2452, 14, 42, 183958, 4877756, 183958, 42, 132, 17454844, 20071150430, 20071150430, 17454844, 132, 429, 1941406508, 129586764260850, 6708527580006468, 129586764260850, 1941406508, 429

Offset: 1

Author

Mitch Harris, Dec 27 2005

Keywords

• nonn
• tabl
• hard

Examples

			Square array A(n,m) begins:
   1,      2,           5,               14, ...
   2,     48,        2452,           183958, ...
   5,   2452,     4877756,      20071150430, ...
  14, 183958, 20071150430, 6708527580006468, ...
		

References

• Stanley, R., Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices.

Links

• Alois P. Heinz, Antidiagonals n = 1..12, flattened

Crossrefs

Cf. A000108, A114714, A114716, A114717.

Main diagonal gives A370257.

Programs

Maple

b := proc(l) option remember; local n; n:= nops(l);
      `if`({seq(l[i][], i=1..n)}={0}, 1, add(`if`(l[i][1]>l[i][2] and
       l[i][1]>l[i+1][1], b(subsop(i=[l[i][1]-1, l[i][2]], l)), 0),
       i=1..n-1)+ add(`if`(l[i][2]>l[i+1][2], b(subsop(i=[l[i][1],
       l[i][2]-1], l)), 0), i=1..n-1)+ `if`(l[n][1]>l[n][2],
       b(subsop(n=[l[n][1]-1, l[n][2]], l)), 0)+ `if`(l[n][2]>0,
       b(subsop(n=[l[n][1], l[n][2]-1], l)), 0))
     end:
A:= (n, m)-> `if`(m>=n, b([[m$2]$n]), b([[n$2]$m])):
seq(seq(A(n, d+1-n), n=1..d), d=1..8);  # Alois P. Heinz, Jun 29 2012

Mathematica

b[l_List] := b[l] = With[{n = Length[l]}, If[Union[Table[l[[i]], {i, 1, n}] // Flatten] == {0}, 1, Sum[If[l[[i, 1]] > l[[i, 2]] && l[[i, 1]] > l[[i+1, 1]], b[ReplacePart[l, i -> {l[[i, 1]]-1, l[[i, 2]]}]], 0], {i, 1, n-1}] + Sum[If[l[[i, 2]] > l[[i+1, 2]], b[ReplacePart[l, i -> {l[[i, 1]], l[[i, 2]]-1}]], 0], {i, 1, n-1}] + If[l[[n, 1]] > l[[n, 2]], b[ReplacePart[l, n -> {l[[n, 1]]-1, l[[n, 2]]} ]], 0] + If[l[[n, 2]] > 0, b[ReplacePart[l, n -> {l[[n, 1]], l[[n, 2]]-1}]], 0]]] ; A[n_, m_] := If[m >= n, b[Array[{m, m}&, n]], b[Array[{n, n}&, m]]]; Table[ Table[A[n, d+1-n], {n, 1, d}], {d, 1, 8}] // Flatten (* Jean-François Alcover, Mar 11 2015, after Alois P. Heinz *)

Formula

A(n,1) = A(1,n) = A000108(n).

A(n,2) = A(2,n) = A114714(n).

A(n,3) = A(3,n) = A114716(n).

Extensions

Edited by Alois P. Heinz, Jun 29 2012