A395725 Triangle read by rows: T(n,k) is the number of permutations of [n] avoiding the pattern 1324 with the maximum element n in position k, 1 <= k <= n.

1, 1, 1, 2, 2, 2, 6, 6, 6, 5, 23, 23, 23, 20, 14, 103, 103, 103, 92, 70, 42, 513, 513, 513, 466, 373, 252, 132, 2762, 2762, 2762, 2537, 2097, 1520, 924, 429, 15793, 15793, 15793, 14619, 12348, 9362, 6206, 3432, 1430, 94776, 94776, 94776, 88226, 75674, 59168, 41470, 25352, 12870, 4862

Offset

1,4

Comments

This triangle refines A061552 by the position of the maximum element n inside each 1324-avoiding permutation of [n]. Row sums recover A061552(n); the rightmost column equals A000108(n-1), and A391315(n) = A061552(n) - T(n,n) recovers the existing entry as the partial row sum Sum_{k=1..n-1} T(n,k).

Machine-verified theorem (Coq, proven): appending the pair [n; v] to a prefix bounded below n preserves 1324-avoidance if and only if the prefix avoids 132, independently of v. The next-to-rightmost diagonal is therefore A000984(n-2).

Machine-verified theorem (Coq, proven): a permutation in Av_n(1324) starts with 1 iff its tail (the last n-1 entries) avoids 213. Combined with the standard Catalan convolution identity, this yields a closed form for the count of 1324-avoiders that simultaneously pin the smallest element to a fixed position j and the largest to a fixed position k, for j = 1 (and dually k = n by reverse-complement invariance of 1324).

Links

Sean A. Irvine, Table of n, a(n) for n = 1..120 (rows 1..15 flattened)

Charles C. Norton, 1324-Joint-Positions Coq formalization

Formula

T(n,n) = A000108(n-1).

T(n,n-1) = (n-1)*A000108(n-2) = A000984(n-2).

T(n,k) = A061552(n-1) for 1 <= k <= 3.

Sum_{k=1..n} T(n,k) = A061552(n).

A391315(n) = A061552(n) - A000108(n-1) = Sum_{k=1..n-1} T(n,k).

Example

Triangle begins:
      n=1:   1;
      n=2:   1,   1;
      n=3:   2,   2,   2;
      n=4:   6,   6,   6,   5;
      n=5:  23,  23,  23,  20,  14;
      n=6: 103, 103, 103,  92,  70,  42;
      n=7: 513, 513, 513, 466, 373, 252, 132;
T(4,4) = 5: among the 23 permutations of [4] avoiding 1324, five have 4 at the last position, namely (1,2,3,4), (1,3,2,4), (2,1,3,4), (2,3,1,4), and (3,2,1,4); they biject with the 5 = A000108(3) permutations of [3] avoiding 132 by deleting the trailing 4.

Mathematica

avoids1324[p_] := !AnyTrue[Subsets[Range[Length[p]], {4}], p[[#[[1]]]] < p[[#[[3]]]] < p[[#[[2]]]] < p[[#[[4]]]] &]; T[n_, k_] := Count[Permutations[Range[n]], p_ /; Position[p, n][[1, 1]] == k && avoids1324[p]]; Table[T[n, k], {n, 1, 9}, {k, 1, n}] // Flatten

Prog

(Python)
from itertools import permutations, combinations
def avoids1324(p):
    return not any(p[i]<p[k]<p[j]<p[l] for i, j, k, l in combinations(range(len(p)), 4))
def T(n, k): return sum(1 for p in permutations(range(1, n+1)) if p[k-1]==n and avoids1324(p))
print([T(n, k) for n in range(1, 10) for k in range(1, n+1)])

Crossrefs

Cf. A000108, A000984, A061552, A391315.

Sequence in context: A198472 A171698 A339385 * A080969 A214078 A155453

Adjacent sequences: A395720 A395721 A395723 * A395726 A395727 A395728

Keyword

nonn,tabl

Author

Charles Cornell Norton, May 04 2026

Extensions

More terms from Sean A. Irvine, May 11 2026

Status

approved