A263484 is "Triangle read by rows: $T(n,k)$ ($n\geq 1$, $0 \leq k < n$) is the number of permutations of $n$ with $n! – k$ permutations in its connectivity set.", and the sequence is:
1,
1,1,
1,2,3,
1,3,7,13,
1,4,12,32,71,
1,5,18,58,177,461,
…
I have looked at various papers on connected and irreducible permutations, but I don't fully understand them. I also don't see anything in them that "looks" like what I am doing, but that is likely due to my lack of understanding. So here is what I am doing:
Let $P$ be the set of permutations of $n$, with $n \geq 2$, and let $p$ be any permutation in $P$. Let $Q$ be the set of permutations of the first $n-1$ symbols of $p$. We will be counting permutations, so let $C$ be an array of integers with $|C| = n-1$, used to record counts, and initialize it to all zeros. For each permutation $q$ in $Q$, append $q$ to $p$ to obtain $s$=the concatenation $p+q$. $s$ will always be of length $2n-1$. Count the number of substrings of contiguous symbols of length $n$ in $s$ that are permutations in $P$, and call this count $x$. $x$ will range from 2 to $n$, depending on $s$. Record this count in array $C$ by incrementing array element $x-2$ by one. After all $(n-1)!$ $s$'s have been checked, let row $n-1$ in $T(n,k)$ equal the reversed array $C$.
A small example:
Let $P$ = {(1,2,3,4),…,(4,3,2,1)}, $p$ = (2,3,4,1), Q ={(2,3,4),(2,4,3)…,(4,3,2)}, and $C$=[0,0,0]. First, let $s$=(2,3,4,1,2,3,4) and we find (2,1,3,4), (3,4,1,2), (4,1,2,3), and (1,2,3,4) are in $P$, so $x$=4. Increment element 4-2=2 in $C$ by one, so now $C$ = [0,0,1]. Now let $s$=(2,3,4,1,2,4,3) and we find (2,3,4,1), (3,4,1,2), and (1,2,4,3) are in $P$, but (4,1,2,4) is not, so $x$=3. Increment element 3-2=1 in $C$ by one, so now $C$=[0,1,1]. After all 3!=6 strings have been checked, C=[3,2,1] Now let row three of $T(n,k)$ equal the reverse of $C$ = [1,2,3].
The triangle I get from this is:
1,
1, 1,
1, 2, 3,
1, 3, 7, 13,
1, 4, 12, 32, 71,
1, 5, 18, 58, 177, 461,
1, 6, 25, 92, 327, 1142, 3447,
1, 7, 33, 135, 531, 2109, 8411, 29093,
1, 8, 42, 188, 800, 3440, 15366, 69692, 273343,
…
which appears to be A263484.
But why?
EDIT:
After reading darij grinberg's comment, I have corrected the definition of Q. Q was originally defined in this question as "Let Q be the set of permutations of (n−1).", which was not correct. I also changed $p$ and $Q$ the example, so it was clear I was not using the permutations of n-1.
Best Answer
This statistic is in the FindStat database, you find it and code to produce it at https://www.findstat.org/St000019. The next row is
What you computed is, up to a relabelling of the numbers $1$ through $n-1$, the same as the connectivity set:
First observe that your definition depends on the permutation $p \in P$. Without loss of generality, you may assume that $p$ is the identity permutation $[1,\dots,n]$. This is because you can relabel the numbers $i$ through $n$ according to your given $p$. For example, consider your example above and interchange the numbers $1$ and $2$ (since $p = [2,1,3,4]$) and observe that a subword is a permutation if and only if it is after interchanging $1$ and $2$.
After this simplification, you observe that you exactly count prefixes of permutations $q \in Q$ that correspond to sets of connectivity.