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

0, 1, 4, 18, 89, 471, 2630, 15364, 93346, 587088, 3807316, 25372666, 173245046, 1208896742, 8601775571, 62291156787, 458339039642, 3421758474117, 25886653957318, 198242964340433, 1535339654196002, 12015301349761293, 94944260613165185, 757046141492539282

Offset

1,3

Comments

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.

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

Links

Table of n, a(n) for n=1..24.

Charles C. Norton, 1324-Avoiding Permutation Coq formalization

Formula

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

Example

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

Mathematica

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}]

Prog

(Python)
from itertools import permutations, combinations
def avoids1324(p):
    for i, j, k, l in combinations(range(len(p)), 4):
        if p[i] < p[k] < p[j] < p[l]:
            return False
    return True
def a(n):
    return sum(1 for p in permutations(range(1, n+1)) if avoids1324(p) and p[-1] != n)
print([a(n) for n in range(1, 9)])

Crossrefs

Cf. A061552, A000108, A000305.

Sequence in context: A046984 A129323 A000305 * A200029 A020070 A197650

Adjacent sequences: A391312 A391313 A391314 * A391316 A391317 A391318

Keyword

nonn

Author

Charles Cornell Norton, Dec 06 2025

Status

approved