Si se permiten repeticiones, ¿de cuántas maneras puede seleccionar K de N sin tomar 2 elementos consecutivos?

Generalización:

Tenemos un conjunto ordenado de elementos [math] n \ in \ mathbb {N} [/ math]. Deseamos contar la cantidad de formas de seleccionar elementos [math] k \ in \ mathbb {N} [/ math] del conjunto. Se nos permite repetir elementos del conjunto en nuestra selección. No contamos las selecciones de manera diferente según el orden en que se eligen los elementos de las selecciones. También tenemos la restricción de que ningún elemento seleccionado [math] 2 [/ math] distinto (no repetido) puede ser [math] \ leq s \ in \ mathbb {N} [/ math] índices separados entre sí en el original conjunto ordenado

Para la pregunta específica formulada, [math] s = 1 [/ math].


Responder:

La respuesta es el coeficiente de [matemáticas] x ^ {k} y ^ {n-1} z ^ {n + k-1} [/ matemáticas] en [matemáticas] (1- (x + y) z- \ sum \ limits_ {m = 1} ^ {s} {\ text {weight} [C (m)]}) ^ {- 1} [/ math]. En esta respuesta, los valores de [matemáticas] \ {\ text {peso} [C (m)] \} | _ {m = 1} ^ {s} [/ matemáticas] se determinan resolviendo el siguiente sistema lineal de [ matemáticas] s [/ matemáticas] ecuaciones: [matemáticas] \ {\ text {peso} [C (m)] = – x ^ 2y ^ mz ^ {m + 2} -x \ sum \ limits_ {i = 1} ^ {s} {y ^ iz ^ {i + 1} \ text {peso} [C (i)]} \} | _ {m = 1} ^ {s} [/ math].

La respuesta a la pregunta específica se simplifica bastante, ya que [math] s = 1 [/ math]. Es el coeficiente de [matemáticas] x ^ {k} y ^ {n-1} z ^ {n + k-1} [/ matemáticas] en [matemáticas] \ frac {1 + xyz ^ 2} {1- ( x + y) z + xyz ^ 2-xy ^ 2z ^ 3} [/ math].

Por ejemplo, si [matemática] n = 7 [/ matemática], [matemática] k = 3 [/ matemática] y [matemática] s = 1 [/ matemática], entonces la respuesta es el coeficiente de [matemática] x ^ 3y ^ 6z ^ 9 [/ math] en [math] \ frac {1 + xyz ^ 2} {1- (x + y) z + xyz ^ 2-xy ^ 2z ^ 3} = 1 + z (x + y ) + z ^ 2 (x ^ 2 + 2xy + y ^ 2) + z ^ 3 (x ^ 3 + 2x ^ 2y + 3xy ^ 2 + y ^ 3) + z ^ 4 (x ^ 4 + 2x ^ 3y + 4x ^ 2y ^ 2 + 4x y ^ 3 + y ^ 4) + z ^ 5 (x ^ 5 + 2x ^ 4y + 5x ^ 3y ^ 2 + 7x ^ 2y ^ 3 + 5xy ^ 4 + y ^ 5) + z ^ 6 (x ^ 6 + 2x ^ 5y + 6x ^ 4y ^ 2 + 10x ^ 3y ^ 3 + 11x ^ 2y ^ 4 + 6xy ^ 5 + y ^ 6) + z ^ 7 (x ^ 7 + 2x ^ 6y + 7x ^ 5y ^ 2 + 13x ^ 4y ^ 3 + 18x ^ 3y ^ 4 + 16x ^ 2y ^ 5 + 7xy ^ 6 + y ^ 7) + z ^ 8 (x ^ 8 + 2x ^ 7y + 8x ^ 6y ^ 2 + 16x ^ 5y ^ 3 + 26x ^ ​​4y ^ 4 + 30x ^ 3y ^ 5 + 22x ^ 2y ^ 6 + 8xy ^ 7 + y ^ 8) + z ^ 9 (x ^ 9 + 2x ^ 8y + 9x ^ 7y ^ 2 + 19x ^ 6y ^ 3 + 35x ^ 5y ^ 4 + 48x ^ 4y ^ 5 + 47x ^ 3y ^ 6 + 29 x ^ 2y ^ 7 + 9xy ^ 8 + y ^ 9) + O (z ^ {10}) [/matemáticas]. Esto es [matemática] 47 [/ matemática], como se ve al leer el coeficiente relevante en la expansión anterior.

Editar:

Por supuesto, hay una respuesta que es mucho más fácil de comprender. Sin embargo, utiliza programación dinámica (que el interrogador no quería explícitamente). Incluiré la relación de recurrencia de todos modos, en aras de la integridad. La respuesta es [matemáticas] f_ {n, s} (k, 1) [/ matemáticas], donde [matemáticas] f_ {n, s} (p, m) = \ begin {cases} 1 & \ text {,} p = 0 \\ 0 & \ text {,} m> n \\ \ sum \ limits_ {i = m} ^ {n} {\ sum \ limits_ {j = 1} ^ {p} {f_ {n, s } (pj, i + s + 1)}} & \ text {, de lo contrario} \ end {cases} [/ math].


Razonamiento:

Primero, creamos una biyección de nuestro problema a uno de contar cadenas de bits relevantes. Primero podemos poner una línea de [math] n-1 [/ math] [math] 1 [/ math] s (creando separadores entre cada elemento del conjunto ordenado). Ahora, si entremezclamos [matemáticas] k [/ matemáticas] [matemáticas] 0 [/ matemáticas] s en la línea de [matemáticas] 1 [/ matemáticas] s, estaremos modelando nuestro problema. Específicamente, el número de formas de elegir elementos [matemáticos] k [/ matemáticos] (permitiendo repeticiones) de elementos distintos de [matemáticos] n [/ matemáticos] es el mismo que el número de modos de colocar [matemáticos] k [/ matemáticos] objetos indistinguibles en [math] n [/ math] cubos distinguibles.

Pero lo anterior no modela la restricción de que no hay elementos [matemáticos] 2 [/ matemáticos] distintos (no repetidos) dentro de los índices [matemáticos] s [/ matemáticos] separados en el conjunto ordenado original. Manejamos esto observando que una situación en la que los elementos [math] 2 [/ math] son ​​[math] m [/ math] índices separados uno del otro corresponde exactamente a ver un [math] 01 … 10 [/ math] en el bit cadena ([matemática] m [/ matemática] [matemática] 1 [/ matemática] s entre [matemática] 2 [/ matemática] [matemática] 0 [/ matemática] s). Entonces, lo que realmente queremos hacer es contar el número de cadenas de bits posibles con [matemática] n-1 [/ matemática] [matemática] 1 [/ matemática] s, [matemática] k [/ matemática] [matemática] 0 [ / math] s, y ninguna subcadena que contenga cualquiera de [math] \ {01… 10 | m \ text {} 1 \ text {s entre}} \ text {} 0 \ text {s} \} | _ {m = 1} ^ {s} [/ matemáticas].

Las páginas [math] 7 [/ math] a [math] 9 [/ math] en https://arxiv.org/pdf/math/98060… (que amplía el poderoso Método de Cluster Gouldon-Jackson) describen cómo resolver no solo el problema de la cadena de bits al que hemos convertido nuestro problema, pero también una clase de problemas mucho más genérica. Para nuestra aplicación, el vocabulario es [matemáticas] V = \ {0,1 \} [/ matemáticas] y el conjunto de palabras malas es [matemáticas] B = \ {01… 10 | m \ text {} 1 \ text { s entre} 2 \ text {} 0 \ text {s} \} | _ {m = 1} ^ {s} [/ math]. Aplicando los resultados en ese documento (escrito por John Noonan y Doron Zeilberger en 1998), llegamos a nuestra Respuesta final.


Otro ejemplo:

Tenga en cuenta que el enfoque en Razonamiento es lo suficientemente flexible como para resolver el problema de varios otros tipos de restricciones iniciales también (filtrando las selecciones permitidas basadas en reglas con respecto a las ubicaciones de sus elementos (relativas entre sí) en el conjunto ordenado original). Por ejemplo, dadas las restricciones heterogéneas de que {no [math] 3 [/ math] elementos seleccionados distintos (no repetidos) pueden ser de [math] 3 [/ math] índices consecutivos} AND {no [math] 2 [/ math ] elementos seleccionados distintos (no repetidos) pueden ser exactamente [matemática] 2 [/ matemática] índices separados uno del otro}, podemos llegar a la respuesta siendo el coeficiente de [matemática] x ^ ky ^ {n-1} z ^ {n + k-1} [/ matemática] en [matemática] \ frac {x ^ 2 y ^ 3 z ^ 5 + x ^ 2 y ^ 2 z ^ 4 + xy ^ 2 z ^ 3 + xyz ^ 2 + 1} {- x ^ 5 y ^ 4 z ^ 9 + 2 x ^ 4 y ^ 4 z ^ 8-x ^ 3 y ^ 4 z ^ 7-x ^ 2 y ^ 4 z ^ 6 + x ^ 2 y ^ 2 z ^ 4-x ^ 2 yz ^ 3-xy ^ 3 z ^ 4 + xyz ^ 2-x zy z + 1} [/ matemática]. Esto se debe a que el conjunto de malas palabras sería [matemáticas] B = \ {01010,0110 \} [/ matemáticas]. Entonces nuestro sistema lineal de ecuaciones sería [matemáticas] \ text {peso} [C (01010)] = – x ^ 3y ^ 2z ^ 5-xy ^ 2z ^ 3 \ text {peso} [C (0110)] – ( xyz ^ 2 + x ^ 2y ^ 2z ^ 4) \ text {weight} [C (01010)] [/ math] y [math] \ text {weight} [C (0110)] = – x ^ 2y ^ 2z ^ 4-x ^ 2y ^ 2z ^ 4 \ text {peso} [C (01010)] – xy ^ 2z ^ 3 \ text {peso} [C (0110)] [/ math]. Resolviendo, obtendríamos [matemáticas] \ text {peso} [C (01010)] = \ frac {x ^ 3 y ^ 2 z ^ 5 (-xy ^ 2 z ^ 3 + y ^ 2 z ^ 2-1) } {x ^ 2 y ^ 3 z ^ 5 + x ^ 2 y ^ 2 z ^ 4 + xy ^ 2 z ^ 3 + xyz ^ 2 + 1} [/ matemática]. Por lo tanto, [matemáticas] \ text {peso} [C] = \ text {peso} [C (01010)] + \ text {peso} [C (0110)] = \ frac {x ^ 2 y ^ 2 z ^ 4 (x ^ 3 y ^ 2 z ^ 5-2 x ^ 2 y ^ 2 z ^ 4 + xy ^ 2 z ^ 3-xyz ^ 2-x z-1)} {x ^ 2 y ^ 3 z ^ 5 + x ^ 2 y ^ 2 z ^ 4 + xy ^ 2 z ^ 3 + xyz ^ 2 + 1} [/ math]. La función racional final, como siempre, sería [matemáticas] (1- (x + y) z- \ text {peso} [C]) ^ {- 1} [/ matemáticas], lo que simplificaría la respuesta anterior.

Si se permiten repeticiones, ¿de cuántas maneras puede seleccionar K de N sin tomar 2 elementos consecutivos?


Sin la restricción de elementos consecutivos contamos los vectores de solución entera no negativa [matemática] (x_1, x_2, \ cdots, x_N) [/ matemática] a la ecuación

[matemáticas] x_1 + x_2 + \ cdots + x_N = K [/ matemáticas]

El argumento aquí es que contamos los arreglos de [matemática] K [/ matemática] “1” sy [matemática] N-1 [/ matemática] “+” s para dar el número de vectores de solución [matemática] \ binom {K + N-1} {N-1} [/ matemáticas].

Su condición en elementos consecutivos es equivalente a requerir que contemos los vectores de solución que tienen al menos 1 “0” entre cualesquiera dos no cero [matemática] x_j [/ matemática] s.

Si hay [matemática] i [/ matemática] distinta de cero [matemática] x_j [/ matemática] s, entonces hay [matemática] Ni [/ matemática] “0” sy podemos contar de manera equivalente los arreglos de las cadenas de [matemática] i [/ math] “A” sy [math] Ni [/ math] “0” s de modo que cada par de “A” s consecutivas esté separado por al menos 1 “0”. Esto es dado por

[matemáticas] \ dbinom {N- (i-1)} {i} [/ matemáticas]

Entonces, para cada una de estas cadenas [math] \ binom {N- (i-1)} {i} [/ math] de “0” sy “A” s (que representan valores distintos de cero [math] x_j [/ math ] s) ahora contamos los vectores de solución para los no-cero [matemática] x_j [/ matemática] s

[matemáticas] x_ {j_1} + x_ {j_2} + \ cdots + x_ {j_i} = K [/ matemáticas]

con cada [math] x_ {j_r} \ ge 1 [/ math] y [math] j_1

[matemáticas] \ dbinom {K-1} {i-1} [/ matemáticas]

tales vectores de solución. Por lo tanto, por el principio de multiplicación hay

[matemáticas] \ dbinom {N- (i-1)} {i} \ dbinom {K-1} {i-1} [/ matemáticas]

Vectores de solución con [math] i [/ math] distinto de cero [math] x_j [/ math] s.

Dado que debemos tener al menos 1 no-cero [matemática] x_j [/ matemática] el número total de vectores de solución [matemática] v_1 (N, K) [/ matemática] sin dos consecutivos distintos de cero [matemática] x_j [/ math] s se obtiene sumando [math] i [/ math] con un límite inferior de 1 y un límite superior determinado por los coeficientes binomiales y es el más pequeño de [math] \ left \ lfloor \ frac {N + 1} { 2} \ right \ rfloor [/ math] y [math] K [/ math]

[matemáticas] v_1 (N, K) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (\ left \ lfloor \ frac {N + 1} {2} \ right \ rfloor, K \ right)} \ dbinom {N- (i-1)} {i} \ dbinom {K-1} {i-1} \ qquad \ blacksquare [/ math]

Por supuesto, esto se generaliza fácilmente al caso en que los elementos elegidos están separados por al menos [math] m [/ math] others. En este caso [matemáticas] m = 1 [/ matemáticas].

Actualizar

Para generalizar, en lugar de [matemáticas] \ binom {N- (i-1)} {i} [/ matemáticas] en el primer paso tenemos [matemáticas] \ binom {Nm (i-1)} {i} [/ matemática] ya que requerimos que los pares de [matemática] i [/ matemática] “A” s estén separados por al menos [matemática] m [/ matemática] “0” s. El resto sigue como dar normal

[matemáticas] v_m (N, K) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (\ left \ lfloor \ frac {N + m} {m + 1} \ right \ rfloor, K \ right )} \ dbinom {Nm (i-1)} {i} \ dbinom {K-1} {i-1} \ qquad \ blacksquare [/ math]


Su caso de [matemáticas] m = 1 [/ matemáticas]:

Para el ejemplo [matemáticas] N = 7, \, K = 3, m = 1 [/ matemáticas] tenemos

[matemáticas] v_1 (7,3) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (4,3 \ right)} \ dbinom {N- (i-1)} {i} \ dbinom { K-1} {i-1} [/ matemáticas]

[matemáticas] v_1 (7,3) = \ dbinom {7} {1} \ dbinom {2} {0} + \ dbinom {6} {2} \ dbinom {2} {1} + \ dbinom {5} { 3} \ dbinom {2} {2} = 7 + 3 \ cdot 5 \ cdot 2 + 5 \ cdot 2 = 47 [/ matemáticas]


Actualizar

Ejemplos de casos donde [math] m> 1 [/ math]:

Para el ejemplo de [matemáticas] N = 7, \, K = 3, m = 2 [/ matemáticas] tenemos

[matemáticas] v_2 (7,3) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (3,3 \ right)} \ dbinom {N-2 (i-1)} {i} \ dbinom {K-1} {i-1} [/ matemáticas]

[matemáticas] v_2 (7,3) = \ dbinom {7} {1} \ dbinom {2} {0} + \ dbinom {5} {2} \ dbinom {2} {1} + \ dbinom {3} { 3} \ dbinom {2} {2} = 7 + 5 \ cdot 2 \ cdot 2 + 1 \ cdot 1 = 28 [/ matemáticas]

Para el ejemplo de [matemáticas] N = 7, \, K = 3, m = 3 [/ matemáticas] tenemos

[matemáticas] v_3 (7,3) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (2,3 \ right)} \ dbinom {N-3 (i-1)} {i} \ dbinom {K-1} {i-1} [/ matemáticas]

[matemáticas] v_3 (7,3) = \ dbinom {7} {1} \ dbinom {2} {0} + \ dbinom {4} {2} \ dbinom {2} {1} = 7 + 2 \ cdot 3 \ cdot 2 = 19 [/ matemáticas]

Para el ejemplo de [matemáticas] N = 7, \, K = 3, m = 4 [/ matemáticas] tenemos

[matemáticas] v_4 (7,3) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (2,3 \ right)} \ dbinom {N-4 (i-1)} {i} \ dbinom {K-1} {i-1} [/ matemáticas]

[matemáticas] v_4 (7,3) = \ dbinom {7} {1} \ dbinom {2} {0} + \ dbinom {3} {2} \ dbinom {2} {1} = 7 + 3 \ cdot 2 = 13 [/ matemáticas]

Para el ejemplo de [matemáticas] N = 7, \, K = 3, m = 5 [/ matemáticas] tenemos

[matemáticas] v_5 (7,3) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (2,3 \ right)} \ dbinom {N-5 (i-1)} {i} \ dbinom {K-1} {i-1} [/ matemáticas]

[matemáticas] v_5 (7,3) = \ dbinom {7} {1} \ dbinom {2} {0} + \ dbinom {2} {2} \ dbinom {2} {1} = 7 + 1 \ cdot 2 = 9 [/ matemáticas]

Para el ejemplo de [matemáticas] N = 7, \, K = 3, m = 6 [/ matemáticas] tenemos

[matemáticas] v_6 (7,3) = \ displaystyle \ sum_ {i = 1} ^ {\ min \ left (1,3 \ right)} \ dbinom {N-6 (i-1)} {i} \ dbinom {K-1} {i-1} [/ matemáticas]

[matemáticas] v_6 (7,3) = \ dbinom {7} {1} \ dbinom {2} {0} = 7 [/ matemáticas]