20 votos

Secuencias combinatorias cuyos cocientes $a_{n+1}/a_{n}$ son números enteros.

Tengo una técnica de prueba en busca de ejemplos. Estoy buscando secuencias combinatorias significativas $\{a_n\}$ para que $a_{n+1}/a_n$ se sabe o se conjetura que es un número entero, tal que existe una relación entre el $n$ el caso y $n+1$ st, pero no una obviedad $a_{n+1}/a_n\to 1$ mapa. Esto significa que $a_n$ es el $n$ producto parcial de una secuencia infinita de enteros, pero no hay una estructura de producto obvia.

  • El prototipo era una enumeración de dominó de un Azteca diamante de orden $n$ , $a_n = 2^{n(n+1)/2}$ Así que $a_{n+1}/a_n = 2^{n+1}$ . (Hay un bonito $2^{n+1}$ a 1 mapa no relacionado con mi técnica, pero no es obvio.)

  • Otra aplicación fue una prueba de que $\det \{B_{i+j}\}_{i,j=0}^n = \prod_{i=1}^n i! $ donde $B_n$ es el $n$ th Número de timbre , ecuación 25 en la página enlazada.

  • Las cuentas de las matrices de signo alterno 1, 2, 7, 42, ... son no un ejemplo, ya que $ASM(n+1)/ASM(n) = \frac{ (3n+1)!n!}{2n! (2n+1)!}$ que no siempre es un número entero, por ejemplo, 7/2 no lo es.

¿Cuáles son otras familias combinatorias interesantes cuyos cocientes $a_{n+1}/a_n$ son conocidos o (preferiblemente) conjeturados como enteros?

Gracias.

20voto

Richard Stanley Puntos 19788

El número de pares $(P,Q)$ de cuadros estándar de Young de la misma forma y con $n$ cuadrados es $n!$ .

El número de cuadros oscilantes de longitud $2n$ y la forma vacía es $1\cdot 3\cdot 5\cdots (2n-1)$ .

El número de árboles binarios completos (desordenados) etiquetados con hojas con $n$ hojas es $1\cdot 3\cdot 5\cdots (2n-3)$ (tercer problema de Schröder).

El número de animales dirigidos de raíz compacta de tamaño $n$ es $3^n$ . Véase MathSciNet MR0956559 (90c:05009).

Dejemos que $f(n)$ sea el número de $n\times n$ matrices $M=(m_{ij})$ de enteros no negativos con vector de suma de filas y columnas $(1,3,6,\dots,{n+1\choose 2})$ tal que $m_{ij}=0$ si $j>i+1$ . Entonces $f(n)=C_1C_2\cdots C_n$ , donde $C_i$ es un número catalán. No se conoce ninguna prueba combinatoria de este resultado. Véase el ejercicio 6.C12 en la página 38 (solución en la página 84) de http://math.mit.edu/~rstan/ec/catadd.pdf

7voto

Silas Puntos 990

Hay 345 secuencias en el OEIS con la palabra "cociente" en sus nombres, ¿eso ayuda?

4voto

Sam Meldrum Puntos 243

Que a n sea la mayor potencia de 2 que divide a R n el número de cuadrados latinos reducidos de orden n. Conocemos el valor de a n para n≤11 (ver este por ejemplo). La secuencia comienza (1,1,1,2 2 ,2 3 ,2 6 ,2 10 ,2 17 ,2 21 ,2 28 ,2 35 ...) para n≥1.

Yo no conjeturaría que un n+1 /a n es siempre un número entero (aunque, parece plausible). Sin embargo, sabemos que un n+1 /a n es un número entero para 1≤n≤10.

3voto

randuser Puntos 432

El número de $n$ -Bloque de torres de dominó es $3^{n-1}$ . La prueba biyectiva más sencilla utiliza el hecho de que para la función generadora de Motzkin $M=M(z)$ tenemos $$\frac{M}{(1-zM)^2}=\frac{1}{1-3z}.$$ Véanse las páginas 19-21 de este documento (y las referencias que contiene):

http://math.sfsu.edu/federico/Clase/AC/algmethods.pdf

(Este es el capítulo 1 del Handbook of Enumerative Combinatorics).

Asimismo, el número de pares de trayectorias grand Dyck de semilongitud combinada $n$ es $4^n$ .

1voto

El número de orientaciones acíclicas en el gráfico completo en $n$ vértices es $n!$ y el número de orientaciones acíclicas en un gráfico de intervalo unitario en $n$ vértices viene dado por un producto con $n$ factores, por lo que se pueden construir fácilmente muchas secuencias a partir de esto.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X