¿Por qué son asintóticamente la mitad del entero de las composiciones de espacio libre?

Question

Pregunta resumen

La cantidad de espacio libre de composiciones de $n$ puede ya bastante pequeño $n$ ser muy bien aproximada por el número total de las composiciones de $n$ dividido por $2$. Esta pregunta busca entender por qué.

Los detalles

Una composición de un número entero $n$ es una manera de escribir $n$ como la suma de una secuencia de enteros positivos, donde el orden es importante. Esto es diferente de particiones, donde el orden es importante. Puede ser fácilmente demostrado que el número de composiciones de $n$$2^{n-1}$. Ver el artículo de Wikipedia para una prueba.

Mucho se ha publicado sobre cómo el número de composiciones cambia cuando se ponen restricciones sobre ellos. Realmente muy interesante, tal restricción es "la brecha de la libertad", es decir, que contiene todos los enteros que está entre el más pequeño y el entero más grande en la composición. Por ejemplo, $2+3+2+4+5$ es un espacio libre de la composición de $16$, pero $2+4+2+1+5+2$ es no, ya que hay una brecha entre las $2$$4$. Por otra parte, una composición que se llama "completo" si es libre de huecos y contiene el número de $1$, es decir, todos los números de $1$ hasta algunos entero $m$ se utilizan en la suma.

Un ejemplo, las composiciones de $n = 5$. g representa la brecha de la libre y c para completar.

5           g
4+1
3+2         g
3+1+1
2+3         g
2+2+1       g, c
2+1+2       g, c
2+1+1+1     g, c
1+4
1+3+1
1+2+2       g, c
1+2+1+1     g, c
1+1+3
1+1+2+1     g, c
1+1+1+2     g, c
1+1+1+1+1   g, c

Así, el número de composiciones de $n=5$$2^{5-1} = 16$, la cantidad de espacio libre de composiciones es $11$ y el número de composiciones completas es $8$.

Enumerar el número de composiciones (#c), la cantidad de espacio libre de composiciones (#gc) y el número de composiciones completas (#cc) para n de 1 a 10 le da la siguiente tabla.

n       #c      #gc     #cc
1       1       1       1
2       2       2       1
3       4       4       3
4       8       6       4
5       16      11      8
6       32      21      18
7       64      39      33
8       128     71      65
9       256     141     127
10      512     276     264

Las continuaciones de estas series se puede encontrar en oeis.org/A107428 y oeis.org/A107429 respectivamente.

A partir de esta breve muestra, puede ser conjeturado que el número de composiciones completas es asintóticamente la mitad del número total de las composiciones. (Esto también es cierto para el espacio libre de las composiciones, ya que casi todo el espacio libre de composiciones están completos, pero esto no es tan evidente a partir de esta breve muestra.)

Una parcela de la desviación entre el porcentaje de espacio libre de composiciones de $\frac12$ $50 \leqslant n \leqslant 4000$ es bastante notable.

$50 < n < 500$

$500 < n < 4000$

No sólo se parecen converger de manera bastante rápida, también muestra un extraño comportamiento oscilante.

Un par de pruebas de este hecho han sido publicadas $[1,2]$. El primer papel fue escrito por Hitczenko y Knopfmacher $[1]$, donde se utilizan generado aleatoriamente composiciones para obtener la probabilidad de que una composición completa (una probabilidad de que los enfoques $1/2$$n \to \infty$).

La prueba se lleva a probabilística de vista de la composición y no dice nada (al menos tal y como yo lo entiendo) acerca de por qué la relación es exactamente la mitad. Sin embargo, el hecho de que asintóticamente exactamente la mitad del número de composiciones completa me ha llevado a pensar que debe haber una manera de pensar acerca de esto que es más intuitivo o, tal vez, de la combinatoria en la naturaleza.

Por ejemplo, el número de composiciones completas de $n$ es asintóticamente igual a la suma del número de composiciones de $n-1$. Un bijection puede, por supuesto, no se puede encontrar, ya que es sólo una relación asintótica. Pero para un gran$n$, ¿hay alguna forma de hacer un salto cualitativo (y asintótica) relación entre estos dos conjuntos de composiciones? Hay otros "asintótica bijections" que puede ser utilizado para arrojar algo de luz sobre esto? Tal vez se puede decir algo acerca de cómo la integridad o la brecha de la libertad de restricción se relaciona con otras restricciones? Yo no estoy en busca de pruebas rigurosas de aquí, es sólo que parece como debería haber alguna manera de pensar de esta manera más intuitiva.

Referencias
$[1]$ $ Hitczenko y A. Knopfmacher, libre de huecos, la composición y la brecha de muestras gratis de geométrico de las variables aleatorias, Discretas Matemáticas. 294 (2005) 225-239
$[2]$ R. Warlimont, composiciones Completas de un número natural, Quaestiones Mathematicae Volumen 29, número 2, 2006

---

Edición 1 De Julio De 2013

No se ha avanzado aquí, pero pensé que me gustaría escribir algunos hechos que podrían dar un poco de inspiración y alimento para el pensamiento.

• El número de completar las particiones de $n$, $\# p_c(n)$, es el mismo que el número de particiones en partes distintas. El bijection puede ser visto fácilmente utilizando un diagrama de Ferrers. Este es un muy bien conocido de la serie con la generación de la función $\prod_{k \ge 1} (1+x^k)$. (A000009 en oeis.org)

• El número de completar las composiciones de $n$, $\# c_c(n)$, puede ser que se calcula contando el número de permutaciones de todas las particiones. En más detalle:

  • Generar una lista de todas las particiones de $n$.

  • Para cada partición $P$ en la lista, compruebe el máximo de la pieza a $m$. Para cada número de $k = \{1,2,\dots,m\}$, compruebe el número de ocurrencias $\alpha_k$$k$$P$. El número de composiciones completas generado por $P$$\frac{m!} {\alpha_1! \dots \alpha_m!}$, es decir, la multinomial $\binom{m}{\alpha_1,\dots,\alpha_m}$

  Puede algo ser dicho sobre el comportamiento asintótico de cómo la operación anterior mapas de $\# p_c(n)$$\# c_c(n)$? Si es así, $\# c_c(n) \sim f(n) \cdot \# p_c(n)$ donde $f(n)$ es este asintótica de la función.

• $\# p_c(n)$ es asintótica a $$\frac{e^{\pi(n-\frac{1}{24})^{1/2}}}{4 \cdot 3^{1/4}(n-\frac{1}{24})^{3/4}}$$ (según oeis.org).

• Le $\begin{cases} \text{know that} \\ \text{would like to prove that } \\ \text{would like to understand why} \end{cases} \Biggr\}$ el número de composiciones completas de $n$ $\# c_c(n) \sim 2^{n-2}$.

---

Edición Julio 9, 2013

Sólo una pequeña nota y una humilde petición. El número de composiciones de $n$ a partir de 1 es $2^{n-2}$. (Link)

Hay otras enumeraciones que tiene (asintóticamente) de la misma dependencia de $n$? Pensé que podría dar algunas ideas/visión.

---

Edición Feb 13, 2015

• La generación de la cantidad de espacio libre y composiciones completas se puede hacer uso de fórmulas recursivas publicado como Arce código en OEIS. El uso de memoization técnicas, las secuencias de las $n$ $4000$ fueron generados.

• La oscilación del comportamiento puede ser muy bien modelado por la siguiente función

$$f(n)=\frac{An^B}{\log Cn}\sin\left(\frac{2 \pi}D \log(Dn+E)+F\right)$$ $$\begin{align} A &= 3.53292387 \cdot 10^{-4}\\ B &= -8.47099853 \cdot 10^{-1}\\ C &= 9.11885892 \cdot 10^{-3}\\ D &= 6.94057582 \cdot 10^{-1}\\ E &= 1.35920759 \cdot 10^1\\ F &= -1.15542736 \cdot 10^1\\ \end{align}$$

Answer 1

Esto es muy de la mano-ondulado pero creo que es aceptable teniendo en cuenta que usted desea intuición. No es $1$ importante brecha en el resultado, pero tal vez alguien puede venir y llenar ese bien.

Primero la notación:

$N(n)$ es el número de composiciones completas de $n$

$N(n,a)$ es el número de composiciones completas de $n$ $a$ como el mayor plazo

$N(n,a,i)$ es el número de composiciones completas de $n$ $a$ como el mayor plazo y sólo un único plazo $i$ que tiene que estar en la final de la secuencia.

Para cada una de ellas, vamos a $\tilde{N}$ denota el conjunto de secuencias que se ajustan a la descripción.

Por ejemplo: $N(5)=8$, $N(5,1)=1$, $N(5,2)=7$, $N(5,2,2)=1$, $N(5,2,1)=1$, $\tilde{N}(5,1)=\{1+1+1+1+1\}$, $\tilde{N}(5,2,2)=\{1+1+1+2\}$, $\tilde{N}(5,2,1)=\{2+2+1\}$

Ahora presentamos a $2$ clave de las relaciones. La primera de ellas:

$$N(n)=\sum_{a=1}^{n}N(n,a)$$

Este debe tener sentido. El número total de composiciones completas de $n$, es el número de composiciones completas con un plazo máximo de $1$ + el número de composiciones completas con un plazo máximo de $2$ + etc.

El segundo:

$$N(n,a)=\sum_{i=1}^{a}N(n-i,a)+N(n,a,i)$$ Para ver esto, tomar una composición arbitraria $c\in \tilde{N}(n,a)$. Escribir $c=c_1+c_2+...+c_m$, y considerar la composición de la $c'=c_1+c_2+...+c_{m-1}$. Ahora hay $2$ posibilidades:

• $c'$ es una composición completa de $n-c_m$ con mayor plazo $a$
• $c'$ es incompleta composición de $n-c_m$

Si $c'$ es una composición completa de $n-c_m$ con mayor plazo$a$,$c'\in\tilde{N}(n-c_m,a)$. De lo contrario, ya que $c$ fue una composición completa de $n$ con mayor plazo $a$ $c'$ no está completa, $c_m$ debe haber sido el único término con este valor en $c$, por lo que la eliminación de los resultados en una incompleta de la composición. Por lo tanto, $c'\in \tilde{N}(n,a,c_m)$

Usted puede hacer este razonamiento de la otra manera alrededor así como para establecer la demanda.

Ahora debemos estar de acuerdo en que

$$\lim_{n\to \infty}\frac{\sum_{i=1}^{a}N(n,a,i)}{N(n,a)}=0$$

Para ver esto, pensar acerca de lo composiciones $\cup_{i=1}^{a}\tilde{N}(n,a,i)$ contiene. Este conjunto contiene todas las composiciones que contienen algunas término exactamente la vez, en que plazo tiene que ser el último término en la composición. "Es intuitivamente claro" que este es un muy subconjunto específico de $\tilde{N}(n,a)$.

Por lo que podemos reescribir*:

$$N(n,a)\approx\sum_{i=1}^{a}N(n-i,a)$$

Y ahora

$$ \begin{aligned} N(n+1) & =\sum_{a=1}^{n+1}N(n+1,a) \\ & \approx \sum_{a=1}^{n+1}\sum_{i=1}^{a}N(n-(i-1),a)\\ & = \sum_{a=1}^{n+1}\sum_{i=0}^{a-1}N(n-i,a)\\ & = \sum_{a=1}^{n}\sum_{i=0}^{a-1}N(n-i,a) + \sum_{i=0}^{n}N(n-i,n) \\ & = \sum_{a=1}^{n}[\sum_{i=1}^{a}[N(n-i,a)] + N(n,a) - N(n-a,a)]\\ & = \sum_{a=1}^{n}\sum_{i=1}^{a}N(n-i,a) + \sum_{a=1}^{n}N(n,a) - \sum_{a=1}^{n}N(n-a,a)\\ & \approx N(n) + N(n) - \sum_{a=1}^{n}N(n-a,a)\\ & \approx 2N(n) \end{aligned} $$

Así que ahora que hemos establecido que $N(n)$ asintóticamente se comportan como $c2^n$ para algunas constantes $c$. Ahora, desde el hecho de que el número total de las composiciones de $n$ es igual a $2^{n-1}$ sabemos que $c<\frac{1}{2}$. Y a partir de la observación sabemos, por supuesto, que $c=\frac{1}{4}$. Sin embargo, en realidad no he sido capaz de llegar con un argumento de por qué es $\frac{1}{4}$. Tal vez tenga sentido para decir que $c$ debe ser de la forma $\frac{1}{2^m}$ debido a que queremos que $N(n)$ a ser un número entero. Entonces todo lo que tenemos que hacer es encontrar un razonamiento de por qué $N(n)>2^{n-3}$. Así que tal vez alguien que lea esto va a ser capaz de completar este razonamiento a partir de aquí.

Así que esto podría parecer un inútil resultado, porque aún nos quedamos con la pregunta de por qué esta constante es exactamente $\frac{1}{4}$. Sin embargo, con este razonamiento que por lo menos ver por qué la relación converge en el primer lugar.

*Un resultado notable de esta aproximación es que resulta que $N(n,2)\approx\frac{1+\sqrt 5}{2}F_n$ donde $F_n$ $n$ésimo número de fibonacci. Y esta aproximación es muy buena (siempre sólo o $1$ o $2$ demasiado grande).