# Why does this appear to produce OEIS sequence A263484?

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.

• Just to make this question more self-contained, here's the definition of the connectivity set of a permutation, as given in arxiv.org/abs/math/0507224 Let $S_n$ denote the symmetric group of permutations of $[n] = \{1, 2, . . . , n\}$, and let $w = a_1a_2 \cdots a_n \in S_n$. Now define the connectivity set $C(w)$ by $C(w)=\{i : a_j <a_k {\rm\ for\ all\ }j\le i<k\}$. Jun 13 '19 at 2:03
• Is your $s$ really the concatenation or is it a shifted conactenation? If $p = (3,2,1)$ and $q = (1,2)$, then the concatenation is $p + q = (3,2,1,1,2)$, which has only $1$ permutation in $P$ inside it. Thus, $x$ is not between $2$ and $n$. Jun 13 '19 at 9:18
• @ darij grinberg My mistake. Q is the set of permutations of the first n-1 symbols, not the permutations of n-1. Thanks for catching that. Jun 15 '19 at 2:27

1, 9, 52, 252, 1146, 5226, 24892, 125316, 642581, 2829325

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.