5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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\}$. $\endgroup$ – Gerry Myerson Jun 13 at 2:03
  • 1
    $\begingroup$ 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$. $\endgroup$ – darij grinberg Jun 13 at 9:18
  • $\begingroup$ @ 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. $\endgroup$ – jnthn Jun 15 at 2:27
2
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.