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,1

Links

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

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)

Example

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

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

Prog

(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
# OR: 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

Crossrefs

Cf. A052849, A000142.

Sequence in context: A347206 A307240 A000013 * A063776 A378105 A287135

Adjacent sequences: A064481 A064482 A064483 * A064485 A064486 A064487

Keyword

nice,nonn,tabl

Author

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

Extensions

More terms from Naohiro Nomoto, Nov 26 2001

Status

approved