A064484 - OEIS

%I #17 Jul 22 2022 10:48:33

%S 2,2,4,4,8,12,4,32,36,48,8,64,216,192,240,8,208,648,1536,1200,1440,16,

%T 416,3024,6144,12000,8640,10080,16,1280,9072,37632,60000,103680,70560,

%U 80640,32,2560,38880,150528,456000,622080,987840,645120,725760

%N 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.

%H Andrew Woods, <a href="/A064484/b064484.txt">Rows n = 2..101 of triangle, flattened</a>

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

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

%F From _Andrew Woods_, Jun 16 2013: (Start)

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

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

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

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

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

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

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

%F (End)

%e For n=3 we have:

%e T(3,4)=2 with the permutations {312, 213} and

%e T(3,5)=4 with {123, 321, 132, 231}.

%t 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 T[1, 2] = 1; T[_, _] = 0;

%t Table[T[n, k], {n, 2, 10}, {k, n+1, 2n-1}] // Flatten (* _Jean-François Alcover_, Jul 19 2022 *)

%o (Python)

%o # Generate n-th row (n>1) by checking all n! permutations

%o from itertools import permutations

%o def onerow(n):

%o ..row=[0]*(n-1)

%o ..for i in permutations(range(1,n+1)):

%o ....row[max([j[0]+j[1] for j in zip(i,i[1:])])-n-1]+=1

%o ..return row

%o # OR: Generate first twenty rows using recurrence

%o rows=[[2]]; row=[2]

%o for i in range(19):

%o ..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)]

%o ..rows.append(row)

%o # _Andrew Woods_, Jun 18 2013

%Y Cf. A052849, A000142.

%K nice,nonn,tabl

%O 2,1

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

%E More terms from _Naohiro Nomoto_, Nov 26 2001