¿Por qué parece que esto produce la secuencia A263484 de OEIS?

Question

A263484 es "Triángulo de lectura por filas: $T(n,k)$ ($n\geq 1$, $0 \leq k < n$) es el número de permutaciones de $n$ con $n! - k$ permutaciones en su conectividad.", y la secuencia es:

1,

1,1,

1,2,3,

1,3,7,13,

1,4,12,32,71,

1,5,18,58,177,461,

...

He mirado en varios papeles en conectado y irreductible permutaciones, pero no estoy totalmente de entender. Yo tampoco veo nada en ellos que se "ve" como lo estoy haciendo, pero que es probable que debido a mi falta de entendimiento. Así que aquí es lo que estoy haciendo:

Deje $P$ el conjunto de las permutaciones de $n$, con $n \geq 2$, y deje $p$ ser cualquier permutación en $P$. Deje $Q$ el conjunto de las permutaciones de la primera $n-1$ símbolos de $p$. Vamos a contar las permutaciones, así que vamos a $C$ ser una matriz de enteros con $|C| = n-1$, se utiliza para registrar la cuenta, y se inicializa a todos los ceros. Para cada permutación $q$ en $Q$, anexar $q$ a $p$ obtener $s$=la concatenación $p+q$. $s$ siempre será de longitud $2n-1$. Contar el número de subcadenas contiguo de los símbolos de la longitud de la $n$ en $s$ que son permutaciones en $P$, y llamar a este recuento $x$. $x$ estará en el intervalo de 2 a $n$, dependiendo de la $s$. Registro de esta cuenta en la matriz de $C$ por el incremento de los elemento de la matriz $x-2$ por uno. Después de todo $(n-1)!$ $s$'s han sido comprobadas, vamos a la fila $n-1$ en $T(n,k)$ igualdad de la inversa de la matriz de $C$.

Un pequeño ejemplo:

Deje $P$ = {(1,2,3,4),...,(4,3,2,1)}, $p$ = (2,3,4,1), Q ={(2,3,4),(2,4,3)...,(4,3,2)}, y $C$=[0,0,0]. En primer lugar, vamos a $s$=(2,3,4,1,2,3,4) y nos encontramos con (2,1,3,4), (3,4,1,2), (4,1,2,3), y (1,2,3,4) en $P$, lo $x$=4. Incremento elemento 4-2=2 en $C$ por uno, así que ahora $C$ = [0,0,1]. Ahora vamos a $s$=(2,3,4,1,2,4,3) y la que nos encontramos (2,3,4,1), (3,4,1,2), y (1,2,4,3) son de $P$, pero (4,1,2,4) no es, por lo $x$=3. Incremento elemento 3-2=1 en $C$ por uno, así que ahora $C$=[0,1,1]. Después de 3!=6 cuerdas han sido comprobadas, C=[3,2,1] Ahora vamos a la fila tres de $T(n,k)$ igual a la inversa de $C$ = [1,2,3].

El triángulo puedo obtener de esto es:

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,

...

que parece ser A263484.

Pero, ¿por qué?

EDITAR:

Después de leer darij grinberg comentario, he corregido la definición de Q. Q fue originalmente definido en esta pregunta como "Vamos Q ser el conjunto de permutaciones de (n−1).", que no fue la correcta. También he cambiado la $p$ e $Q$ el ejemplo, así que estaba claro que yo no estaba utilizando las permutaciones de n-1.

Answer 1

Este dato está en la FindStat de la base de datos, que se encuentran y el código de producir en la https://www.findstat.org/St000019. En la fila siguiente

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

Lo que se calcula es, hasta un reetiquetado de los números de $1$ través $n-1$, la misma que la conectividad:

• Primero observar que su definición depende de la permutación $p \in P$. Sin pérdida de generalidad, se puede asumir que $p$ es la identidad de permutación $[1,\dots,n]$. Esto es porque usted puede etiquetar de nuevo los números de $i$ través $n$ según su $p$. Por ejemplo, considere el ejemplo anterior y el intercambio de los números de $1$ e $2$ (desde $p = [2,1,3,4]$) y observar que un subword es una permutación si y sólo si es después de intercambiar $1$ e $2$.

• Después de esta simplificación, que usted observe exactamente recuento de los prefijos de las permutaciones $q \in Q$ que corresponden a conjuntos de conectividad.