Problema de conteo: generación de función usando particiones de números impares y los permutando

Question

Hemos bloques de construcción de las siguientes longitudes: $3, 5, 7, 9, 11$ y así sucesivamente, incluyendo todos los otros números impares otros de $1$. Cada longitud está disponible en dos colores, rojo y azul. Para un determinado número de $n$, ¿de cuántas maneras distintas podemos combinar bloques en un único pedido (con respecto a colores y longitudes de usa) que tiene una longitud total de $n$?

Ejemplo: $n=9$ $10$ total maneras. Vemos que podemos utilizar una secuencia de $3$ bloques de longitud $3$, cada una con $2$ opciones de color, lo que hace la $2^3=8$ maneras. También podemos utilizar un $1$ bloque de $9$ en rojo o en azul. Por lo tanto, el total es de $10$.

Finalmente, podemos utilizar funciones de generación de encontrar el número de combinaciones para cualquier $n$, y he estado buscando en la generación de la función de particiones con números impares. Hay un par de maneras este problema difiere el problema de cómo encontrar muchas maneras en que podemos usar los números impares de la suma a un determinado $n$. En primer lugar, estamos mirando las permutaciones de estos bloques, no sólo combinaciones. Segundo, cada bloque tiene dos colores para elegir, por lo tanto una combinación de $5$ bloques de ha $2^5$ formas de asignar estos colores.

Cualquier consejo sobre cómo abordar esta usando funciones de generación o simplemente en general?

Answer 1

Dado $n$, vamos a $f_n$ denotar el número requerido de bloque de arreglos.

Si tenemos en cuenta las posibilidades para el primer bloque de este tipo de acuerdos, vemos que, desde el primer bloque puede ser de color rojo o azul y tienen una longitud de $3$, $5$, $7$, etc,

\begin{eqnarray*} f_n &=& 2(f_{n-3} + f_{n-5} + f_{n-7} + \cdots + f_k) \\ && \\ && \mbox{where } k = \begin{cases} 0 & \text{if %#%#% is odd} \\ 1 & \text{if %#%#% is even.} \end{casos} \end{eqnarray*}

Del mismo modo,

\begin{eqnarray*} f_{n+2} &=& 2(f_{n-1} + f_{n-3} + f_{n-5} + \cdots + f_k). \end{eqnarray*}

La combinación de estas dos ecuaciones obtenemos

$n$$

Esta es una de tercer orden lineal homogénea de la recurrencia de la relación. Su ecuación característica es

$n$$

Por desgracia, sus raíces (uno real y un par de complejos conjugados) son complicadas de forma exacta. Aquí está la solución de Wolfram Alpha, a la vez exacto y la aproximación numérica.

Por ahora, vamos a la etiqueta de estas raíces:$$f_{n+2} - f_n- 2f_{n-1} = 0.$$$x^3 - x - 2 = 0.$.

Para tales relaciones de recurrencia, la solución general es conocido por ser:

$\quad a\quad $$

para algunas constantes $\quad b \pm ic$ e con $$\mathbf{f_n = Aa^n + r^n\left(B \cos(n\theta) + C \sin(n\theta)\right)}\qquad\qquad\qquad\qquad\mbox{(*)}$$A,B,C$, siendo estos el módulo y el argumento de $r = \sqrt{b^2+c^2}$.

Para encontrar $\theta = \tan^{-1}\left(\frac{c}{b}\right)$ tenemos los casos iniciales:

\begin{eqnarray*} f_0 &=& 1 \\ f_1 &=& 0 \\ f_2 &=& 0. \\ &&\\ \end{eqnarray*} \begin{eqnarray*} 1 = f_0 &=& Aa^0 + r^0\left(B \cos(0) + C \sin(0)\right) \\ &=& A + B \\ \therefore B &=& 1-A.\\ &&\\ 0 = f_1 &=& Aa + r\left(B \cos(\theta) + C \sin(\theta)\right) \\ &=& Aa + r\left(B \frac{b}{r} + C \frac{c}{r}\right) \\ &&\qquad\qquad\mbox{(since %#%#% and %#%#%)} \\ &=& Aa + Bb + Cc \\ &=& Aa -Ab + b + Cc \qquad\mbox{(using %#%#%).} \\ && \\ 0 = f_2 &=& Aa^2 + r^2\left(B \cos(2\theta) + C \sin(2\theta)\right) \\ &=& Aa^2 + r^2\left(B -2B\sin^2\theta + 2C \cos\theta\,\sin\theta\right) \qquad\mbox{(using double-angle formulae)} \\ &=& Aa^2 + r^2\left(B -2B\frac{c^2}{r^2} + 2C \frac{bc}{r^2}\right) \\ &=& Aa^2 + Br^2 -2Bc^2 + 2Cbc \\ &=& Aa^2 + r^2 - Ar^2 -2c^2 + 2Ac^2 + 2b(Ab - Aa - b) \\ && \qquad\qquad\mbox{(using %#%#% and %#%#%)} \\ &=& A(a^2 - r^2 + 2b^2 + 2c^2 -2ab) + r^2 -2b^2 - 2c^2 \\ &=& A(a^2 + b^2 + c^2 -2ab) -b^2 - c^2. \\ &&\\ \therefore A &=& \dfrac{b^2 + c^2}{a^2 + b^2 + c^2 -2ab}. \\ &&\\ \therefore B &=& 1-A = \dfrac{a^2 - 2ab}{a^2 + b^2 + c^2 -2ab}. \\ &&\\ \therefore C &=& \dfrac{A(b-a) - b}{c} = \dfrac{b^3 + bc^2 - ab^2 - ac^2 - b}{c(a^2 + b^2 + c^2 -2ab)}. \\ \end{eqnarray*}

El enlace de arriba para Wolfram Alpha tiene los valores aproximados:

\begin{eqnarray*} a &=& 1.52137970680457 \\ b &=& -0.760689853402284 \\ c &=& 0.857873626595179. \end{eqnarray*}

De estos también obtenemos: \begin{eqnarray*} r &=& 1.14655842078664 \\ \theta &=& 2.29622326401129 \mbox{ radians}\\ A &=& 0.221171426610117 \\ B &=& 0.778828573389883 \\ C &=& 0.298367108176176. \end{eqnarray*}

El uso de estos valores con la ecuación (*) se puede calcular los valores reales de a $b+ic$:

\begin{eqnarray*} n && f_n \\ \hline 3 && 2 \\ 4 && 0 \\ 5 && 2 \\ 6 && 4 \\ 7 && 2 \\ 8 && 8 \\ 9 && 10 \\ 10 && 12 \\ 11 && 26 \\ 12 && 32 \\ 13 && 50 \\ 14 && 84 \\ 15 && 114 \\ 16 && 184 \\ 17 && 282 \\ 18 && 412 \\ 19 && 650 \\ 20 && 976. \end{eqnarray*}

Answer 2

Suponiendo que usted se refiere a las particiones, la generación de la función que se busca es la $$ P_{impar,redblue}(z) = \prod_{n=1}^{\infty} \frac{1}{1-2z^{2n+1}}. $$ No sé todavía si la función tiene una mejor forma o lo que las propiedades de la función.
Cómo llegar: Primero debe estar familiarizado con el conjunto múltiple de la construcción, de Flajolet del libro de la Analítica de la Combinatoria, la página 29 y ss. Para una combinatoria de la clase $\mathcal B$ ( $\mathcal B_0 = \emptyset$ ), el conjunto múltiple de construcción se define como $$ \mathrm{MSET}(\mathcal B) = \prod_{ \beta \in \mathcal B} \mathrm{SEQ}( \{ \beta \}). $De$la generación de la función de la "normal" de las particiones es $$ P(z) = \prod_{n=1}^{\infty} \frac{1}{1-z^n}. $$ Si sólo podemos utilizar números enteros impares mayores que uno, se obtiene de la misma manera: $$ P_{impar}(z) = \prod_{n=1}^{\infty} \frac{1}{1-z^{2n+1}}. $$ Ahora tenemos dos posibilidades para cada número impar, por lo que simplemente el doble del coeficiente de $z$: $$ P_{impar,redblue}(z) = \prod_{n=1}^{\infty} \frac{1}{(1-z^{2n+1})^2}. $$ Los coeficientes de $n=8..12$$4,6,7,8,13$, respectivamente.

Answer 3

Nota: Esta es realmente una buena pregunta , ya que proporciona una buena oportunidad para considerar similares pero diferentes conceptos en un no-trivial, pero manejable manera!

Pero primero algunas aclaraciones: El ejemplo con $n=9$ en la pregunta anterior, dando un resultado de $10$ significa que el número de diferentes composiciones de $9$$10$. Más tarde en la generación de la función de particiones se le pide. Estos son conceptos diferentes. Así que, vamos a aclarar estos términos.

Composiciones vs Particiones de un entero ($\geq 1$)

• Descripción Informal:

Composiciones de un entero son representaciones por sumandos donde el orden de los asuntos. por ejemplo, $8=3+5=5+3$ da dos composiciones diferentes de $8$.

Las particiones de un entero son representaciones por sumandos donde el orden no importa. Por lo $8=3+5=5+3$ es considerado como una sola partición de $8$.

La siguiente definición de la Analítica de la Combinatoria de Flajolet y Sedgewick (Def. I. 9)

• Descripción precisa:

Una composición de un número entero $n$ es una secuencia $(x_1,x_2,\ldots,x_k)$ de enteros (para algunos $k$) tales que $$n=x_1+x_2+\ldots+x_k,\qquad\qquad x_j\geq 1$$

Una partición de un número entero $n$ es una secuencia $(x_1,x_2,\ldots,x_k)$ de enteros (para algunos $k$) tales que $$n=x_1+x_2+\ldots+x_k \qquad\text{and} \qquad\qquad x_1\geq x_2\geq \ldots \geq x_k\geq 1$$

---

La respuesta se divide en cuatro pasos:

• Primer paso: Hemos estado en la generación de funciones para las composiciones , así como para las particiones de dos colores, números enteros impares $> 1$

• Segundo paso: Ejemplos con números pequeños (comprobación)

• Tercer paso: Prueba de la generación de la función de composiciones

• Cuarto paso: Prueba de la generación de la función de particiones

---

Primer paso: la Generación de funciones

El siguiente es válido:

La generación de la función $C(z)$ para el número de composiciones de dos colores, números enteros impares $>1$ es

\begin{align*} C(z)&=\frac{1-z^2}{1-z^2-2z^3}\\ \\ &=1+2z^3+2z^5+4z^6+2z^7+8z^8+10z^9+12z^{10}+\ldots\tag{1}\\ \\ \end{align*}

La generación de la función $P(z)$ para el número de particiones de dos colores, números enteros impares $>1$ es

\begin{align*} P(z)&=\prod_{n=1}^{\infty}\left(\frac{1}{1-z^{2n+1}}\right)^2\\ \\ &=\left(\frac{1}{1-z^{3}}\right)^2\left(\frac{1}{1-z^{5}}\right)^2\left(\frac{1}{1-z^{7}}\right)^2\cdot\ldots\\ \\ &=1+2z^3+2z^5+3z^6+2z^7+4z^8+6z^9+7z^{10}+\ldots\tag{2}\\ \\ \end{align*}

Deja que el color de los números enteros en el etiquetado de la azul enteros con b y el rojo enteros con r. Vemos por ejemplo, que el coeficiente de $z^6$ en la generación de funciones de composiciones es $4$ y para las particiones es $3$: \begin{align*} [z^6]C(z)=4&\qquad\longrightarrow\qquad 6 = 3_b+3_b=3_b+3_r=3_r+3_b=3_b+3_b\\ [z^6]P(z)=3&\qquad\longrightarrow\qquad 6 = 3_b+3_b=3_b+3_r=3_b+3_b \end{align*} Observamos, que el $C(z)$ respeta el orden de $3_b+3_r$ $3_r+3_b$ mientras $P(z)$ ¿ no distinguir entre estos y por lo que se cuenta sólo una vez. El primer sumando $1=z^0$ $C(z)$ $P(z)$ es simplemente por comodidad que denota que hay una posibilidad de que el vacío composición resp. el vacío de la partición. Por la forma en que los coeficientes en (1) y (2) se calcula a partir de la generación de funciones con la ayuda de Wolfram Alpha.

---

Segundo paso: Composiciones y Particiones de números pequeños

Esto es simplemente una prueba de plausibilidad de (1) y (2) y también una manera de familiarizarse con la diferencia entre las composiciones y las particiones

Comenzamos con el número de composiciones de $3$ $10$

Composiciones: \begin{array}{lll} \text{n}&\text{compositions}&\text{nr of comp.}\\ \hline 3\qquad&3_b,3_r&\qquad2\\ 4\qquad&-&\qquad0\\ 5\qquad&5_b,5_r&\qquad2\\ 6\qquad&3_b+3_b,3_b+3_r,3_r+3_b,3_r+3_r&\qquad4\\ 7\qquad&7_b,7_r&\qquad2\\ 8\qquad&3_b+5_b,3_b+5_r,3_r+5_b,3_r+5_r&\qquad8\\ &5_b+3_b,5_b+3_r,5_r+3_b,5_r+3_r&\\ 9\qquad&3_b+3_b+3_b&\qquad10\\ &3_b+3_b+3_r,3_b+3_r+3_b,3_r+3_b+3_b,&\\ &3_b+3_r+3_r,3_r+3_b+3_r,3_r+3_r+3_b,&\\ &3_r+3_r+3_r&\\ &9_b,9_r&\\ 10\qquad&3_b+7_b,\ldots,7_b+3_b&\qquad12(=8+4)\\ &5_b+5_b,\ldots,5_r+5_r&\\ \end{array}

y vaya con el número de particiones de $3$ $10$

Particiones:

\begin{array}{lll} \text{n}&\text{partitions}&\text{nr of part.}\\ \hline 3\qquad&3_b,3_r&\qquad2\\ 4\qquad&-&\qquad0\\ 5\qquad&5_b,5_r&\qquad2\\ 6\qquad&3_b+3_b,3_b+3_r,3_r+3_r&\qquad3\\ 7\qquad&7_b,7_r&\qquad2\\ 8\qquad&3_b+5_b,3_b+5_r,3_r+5_b,3_r+5_r&\qquad4\\ 9\qquad&3_b+3_b+3_b,3_b+3_b+3_r&\qquad 6\\ &3_b+3_r+3_r,3_r+3_r+3_r&\\ &9_b,9_r&\\ 10\qquad&3_b+7_b,3_b+7_r,3_r+7_b,3_r+7_r&\qquad7(=4+3)\\ &5_b+5_b,5_b+5_r,5_r+5_r&\\ \end{array}

Observamos las columnas número de composiciones y el número de particiones de coincidir con el indicado coeficientes de $C(z)$ $P(z)$ en (1) y (2).

---

Nota: ahora seguimos Flajolet (sección I. 3) muy de cerca. Podemos construir lo que se llama construcciones. Estas son ciertos conjuntos que contienen objetos simbólicos correspondientes a las composiciones resp. las particiones que queremos contar. Y el clou es que también hay un poderoso mecanismo de traducción de estas construcciones en la generación de funciones. Eso es todo ... :-)

Tercer paso: la Generación de la función $C(z)$ de composiciones

Comenzamos con la definición de un conjunto para el azul, enteros impares $> 1$ y el rojo, los enteros impares $>1$.

Vamos \begin{align*} \mathcal{B}_b&=\{3_b,5_b,7_b,\ldots\}\cong\{\bullet\bullet\bullet,\bullet\bullet\bullet\bullet\bullet,\ldots\}=\text{SEQ}_{(odd,>1)}\{\bullet\}\tag{3}\\ \mathcal{B}_r&=\{3_r,5_r,7_r,\ldots\}\cong\{\circ\circ\circ,\circ\circ\circ\circ\circ,\ldots\}=\text{SEQ}_{(odd,>1)}\{\circ\}\tag{4}\\ \end{align*}

El próximo consideramos que la separe de la unión de $\mathcal{B}_{(b,r)}$ $\mathcal{B}_b$ $\mathcal{B}_r$.

Vamos \begin{align*} \mathcal{B}_{(b,r)}&=\mathcal{B}_b+\mathcal{B}_r\\ &=\{3_b,3_r,5_b,5_r,7_b,7_r\ldots\}\\ &\cong\{\bullet\bullet\bullet,\circ\circ\circ,\bullet\bullet\bullet\bullet\bullet,\circ\circ\circ\circ\circ,\ldots\}\\ &=\text{SEQ}_{(odd,>1)}\{\bullet,\circ\}\\ \end{align*}

Observar, que $\text{SEQ}_{(odd,>1)}\{\bullet\}$ es sólo una notación abreviada para el conjunto $\{\bullet\bullet\bullet,\bullet\bullet\bullet\bullet\bullet,\ldots\}$ que simplemente es $\mathcal{B}_b =\{3_b,5_b,7_b,\ldots\}$ en unario la notación.

La generación de la función $B_b(z)$ para la construcción de la $\mathcal{B}_b$ puede ser fácilmente derivados de:

Vamos \begin{align*} B_b(z)&=z^3+z^5+z^7+\ldots\\ &=z^3\left(1+z^2+z^4+\ldots\right)\\ &=\frac{z^3}{1-z^2}\tag{5} \end{align*} Del mismo modo obtenemos \begin{align*} B_r(z)&=\frac{z^3}{1-z^2} \end{align*} Presentamos $B_{(b,r)}(z)$, la generación de la función de $\mathcal{B}_{(b,r)}$. Desde $\mathcal{B}_{(b,r)}$ es la combinatoria suma (distinto de la unión) $\mathcal{B}_b+\mathcal{B}_r$, podemos observar

\begin{align*} B_{(b,r)}(z)&=B_b(z)+B_r(z)\\ &=\frac{2z^3}{1-z^2}\tag{6} \end{align*}

Ahora podemos definir la construcción de todas las composiciones de $\mathcal{B}_{(b,r)}$. Desde las composiciones de hacer respetar el orden de sus componentes pueden ser especificados como una secuencia de elementos de $\mathcal{B}_{(b,r)}$.

La construcción de la $\mathcal{C}$ de todas las composiciones de $\mathcal{B}_{(b,r)}$ y la correspondiente generación de función $C(z)$ se dan como \begin{align*} \mathcal{C}&=\text{SEQ}(\mathcal{B}_{(b,r)})\\ &=\{\varepsilon\}+\mathcal{B}_{(b,r)}+\mathcal{B}_{(b,r)}\times\mathcal{B}_{(b,r)} +\mathcal{B}_{(b,r)}\times\mathcal{B}_{(b,r)}\times\mathcal{B}_{(b,r)}+\ldots\\ \\ C(z)&=1+B_{(b,r)}(z)+\left(B_{(b,r)}(z)\right)^2+\left(B_{(b,r)}(z)\right)^3+\ldots\\ &=\frac{1}{1-B_{(b,r)}(z)}\\ &=\frac{1}{1-\frac{2z^3}{1-z^2}}\\ &=\frac{1-z^2}{1-z^2-2z^3} \end{align*}

lo que demuestra (1).

---

Cuarto paso: la Generación de la función $P(z)$ de las particiones

Utilizamos las siguientes construcciones y sus correspondientes funciones de generación de arriba: \begin{array}{ll} \mathcal{B}_b=\text{SEQ}_{(odd,>1)}\{\bullet\}\qquad&\qquad B_b(z)=\frac{z^3}{1-z^2}\\ \mathcal{B}_r=\text{SEQ}_{(odd,>1)}\{\circ\}\qquad&\qquad B_r(z)=\frac{z^3}{1-z^2}\\ \mathcal{B}_{(b,r)}=\text{SEQ}_{(odd,>1)}\{\bullet,\circ\}\qquad&\qquad B_{(b,r)}(z)=\frac{2z^3}{1-z^2}\\ \end{array}

Observar, que las particiones pueden ser considerados multisets. E. g. la partición de $13=3+5+5$ corresponde al conjunto múltiple $\{3,5,5\}$. Ahora nos referimos a Flajolets sección de un conjunto múltiple de la construcción.

De acuerdo con el conjunto múltiple de la construcción (Flajolet I. 2.2, número (24)), la construcción de la $\mathcal{P}$ de todas las particiones de $\mathcal{B}_{(b,r)}$ y la correspondiente generación de función $P(z)$ es \begin{align*} \mathcal{P}&=\text{MSET}\left(\mathcal{B}_{(b,r)}\right)\\ &\cong\prod_{\beta\in\mathcal{B}_{(b,r)}}\text{SEQ}\left(\{\beta\}\right)\\ &=\prod_{\beta\in\mathcal{B}_b+\mathcal{B}_r}\text{SEQ}\left(\{\beta\}\right)\\ &=\prod_{\beta\in\mathcal{B}_b}\text{SEQ}\left(\{\beta\}\right) \times \prod_{\beta\in\mathcal{B}_r}\text{SEQ}\left(\{\beta\}\right)\\ \\ P(z)&=\prod_{n=1}^{\infty}\frac{1}{1-z^{2n+1}}\prod_{n=1}^{\infty}\frac{1}{1-z^{2n+1}}\\ &=\prod_{n=1}^{\infty}\left(\frac{1}{1-z^{2n+1}}\right)^2\\ \end{align*}

lo que demuestra (2).

---

Sugerencia: Flajolets libro es un excelente clásico. Tal vez te gustaría tener una mirada en mi respuesta a esta pregunta si usted está interesado en la literatura correspondiente.