A064484 Triangle T(n,k), n >= 2, n+1 <= k <= 2*n-1, number of permutations p of 1,...,n, with max(p(i)+p(i-1), i=2..n) = k.

2, 2, 4, 4, 8, 12, 4, 32, 36, 48, 8, 64, 216, 192, 240, 8, 208, 648, 1536, 1200, 1440, 16, 416, 3024, 6144, 12000, 8640, 10080, 16, 1280, 9072, 37632, 60000, 103680, 70560, 80640, 32, 2560, 38880, 150528, 456000, 622080, 987840, 645120, 725760

Offset: 2

Author

Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Oct 05 2001

Keywords

• nice
• nonn
• tabl

Examples

			For n=3 we have:
T(3,4)=2 with the permutations {312, 213} and
T(3,5)=4 with {123, 321, 132, 231}.
		

Links

• Andrew Woods, Rows n = 2..101 of triangle, flattened

Crossrefs

Cf. A052849, A000142.

Programs

Mathematica

T[n_ /; n >= 2, k_] /; n+1 <= k <= 2n-1 := T[n, k] = If[EvenQ[k], (k-n)* T[n-1, k-1], (k-n+1)*T[n-1, k-1] + 2*Sum[T[n-1, i], {i, n, k-2}]];
T[1, 2] = 1; T[, ] = 0;
Table[T[n, k], {n, 2, 10}, {k, n+1, 2n-1}] // Flatten (* Jean-François Alcover, Jul 19 2022 *)

Python

# Generate n-th row (n>1) by checking all n! permutations
from itertools import permutations
def onerow(n):
  row=[0]*(n-1)
  for i in permutations(range(1, n+1)):
    row[max([j[0]+j[1] for j in zip(i, i[1:])])-n-1]+=1
  return row
# Andrew Woods, Jun 18 2013

Python

# Generate first twenty rows using recurrence
rows=[[2]]; row=[2]
for i in range(19):
  row=[(row[j]*(j+2)+sum(row[:j])*2) if (i+j)%2==1 else row[j]*(j+1) for j in range(i+1)]+[row[-1]*(i+2)]
  rows.append(row)
# Andrew Woods, Jun 18 2013

Formula

Sum_{k=n+1..2*n-1} T(n,k) = n! = A000142(n).

T(n,2*n-1) = 2*(n-1)! = A052849(n-1).

From Andrew Woods, Jun 16 2013: (Start)

T(n, even k) = (k-n)*T(n-1,k-1);

T(n, odd k) = (k-n+1)*T(n-1,k-1)+2*sum(T(n-1,i) for i=n..k-2);

T(n,2*n-1) = 2*(n-1)!;

T(n,2*n-2) = 2*(n-1)!-2*(n-2)! for n>2;

T(n,2*n-3) = 4*(n-1)!-12*(n-2)!+4*(n-3)! for n>3;

T(n,2*n-4) = 4*(n-1)!-24*(n-2)!+28*(n-3)!-4*(n-4)! for n>4;

T(n,2*n-5) = 6*(n-1)!-60*(n-2)!+152*(n-3)!-96*(n-4)!+8*(n-5)! for n>5.

(End)

Extensions

More terms from Naohiro Nomoto, Nov 26 2001