A391315 - OEIS

%I #27 Jan 01 2026 23:37:42

%S 0,1,4,18,89,471,2630,15364,93346,587088,3807316,25372666,173245046,

%T 1208896742,8601775571,62291156787,458339039642,3421758474117,

%U 25886653957318,198242964340433,1535339654196002,12015301349761293,94944260613165185,757046141492539282

%N Number of 1324-avoiding permutations of [n] in which the largest element is not in the final position.

%C The 1324-avoiding permutations of [n] partition into two classes by position of n: (1) n in final position, counted by A000108(n-1); (2) n in interior position, counted by a(n). Machine-verified theorem (Coq, proven): A permutation [sigma, n] avoids 1324 if and only if sigma avoids 132, establishing that class (1) bijects with 132-avoiding permutations.

%C Shares first four terms with A000305 but differs at a(6): 471 vs 466.

%H Charles C. Norton, <a href="https://github.com/CharlesCNorton/1324-Avoiding-Permutation">1324-Avoiding Permutation Coq formalization</a>

%F a(n) = A061552(n) - A000108(n-1).

%e a(3) = 4: The 6 permutations of {1,2,3} all avoid 1324. Two have 3 at the end: (1,2,3), (2,1,3). The remaining 4 have 3 in an interior position: (3,1,2), (3,2,1), (1,3,2), (2,3,1).

%t avoids1324[p_] := !AnyTrue[Subsets[Range[Length[p]], {4}], p[[#[[1]]]] < p[[#[[3]]]] < p[[#[[2]]]] < p[[#[[4]]]] &]; a[n_] := Count[Permutations[Range[n]], p_ /; avoids1324[p] && Last[p] != n]; Table[a[n], {n, 1, 8}]

%o (Python)

%o from itertools import permutations, combinations

%o def avoids1324(p):

%o     for i, j, k, l in combinations(range(len(p)), 4):

%o         if p[i] < p[k] < p[j] < p[l]:

%o             return False

%o     return True

%o def a(n):

%o     return sum(1 for p in permutations(range(1, n+1)) if avoids1324(p) and p[-1] != n)

%o print([a(n) for n in range(1, 9)])

%Y Cf. A061552, A000108, A000305.

%K nonn

%O 1,3

%A _Charles Cornell Norton_, Dec 06 2025