[martiniano]

Buenos días.

Hace algún tiempo se me planteó el siguiente problema y a base de darle vueltas elaboré alguna respuesta, aunque no me quedé del todo satisfecho. A ver qué opináis. El contexto es un tema llamado combinatoria dentro de una asignatura llamada matemática discreta: variaciones, combinaciones, permutaciones (todas ellas con o sin repetición) y números de Stirling. El enunciado dice así:

Los tres reyes magos tienen que repartirse entre ellos la tarea de entregar 2017 reaglos diferentes a los niños. ¿De cuántas maneras
lo pueden hacer si cada rey debe repartir como mínimo 500 regalos?

La primera conclusión a la que llegué (no del todo satisfactoria para mí y no sé si correcta) fue que se podía expresar la cantidad pedida como suma de permutaciones con repetición:

\(   \displaystyle\sum_{\substack{a_i\geq{}500 \\ a_1+a_2+a_3=2017}}PR_{a_1,a_2,a_3}^{2017}= \displaystyle\sum_{\substack{a_i\geq{}500 \\ a_1+a_2+a_3=2017}}\displaystyle\frac{2017!}{a_1!a_2!a_3!}  \)

Luego, a base de darle vueltas y de manera similar a lo que se hace con los números de Stirling, se me ocurrió definir una función \( f(n,k,m) \) que expresase el número de \( k \)-particiones que se pueden generar en un conjunto de \( n \) elementos de manera que todos los subconjuntos de una de las particiones tengan al menos \( m \) elementos (imagino que ya hay "inventado" algo así, pero lo descononzco). Dicha función tendría las siguientes propiedades recursivas (no sé si están bien):

Tiene errores. Se explica más abajo

\( f(n,k,m)=k\cdot{}f(n-1,k,m)+\displaystyle\binom{n-1}{k-1}\cdot{}f(n-m,k-1,m) \)
\( f(n,k,m)=0 \)   si \( m\cdot{}k>n \)
\( f(n,1,m)=1 \)   si \( m\leq{}n \)

Con estas propiedades quedaría definida la función. Y, si no me equivoco, la respuesta al ejercicio sería: \( f(2017,3,500) \).

Agradezco de antemano cualquier tipo de comentario tanto sobre lo que yo pensé como sobre el problema en sí. No descarto que se confundiesen al plantearlo en esta asignatura (yo no la cursé), ya que la solución que se ofreció en clase no fue tampoco acertada  . Lo que a mí me gustaría saber es si alguien conoce algo equivalente a la función \( f \) que he definido unas líneas más arriba o si alguien sabe cómo expresar la solución del problema con las herramientas que se dieron en clase y sin recurrir a sumatorios inmanejables, si es que se puede. Saludos y gracias. 

[Luis Fuentes]

Hola

Buenos días.

Hace algún tiempo se me planteó el siguiente problema y a base de darle vueltas elaboré alguna respuesta, aunque no me quedé del todo satisfecho. A ver qué opináis. El contexto es un tema llamado combinatoria dentro de una asignatura llamada matemática discreta: variaciones, combinaciones, permutaciones (todas ellas con o sin repetición) y números de Stirling. El enunciado dice así:

Los tres reyes magos tienen que repartirse entre ellos la tarea de entregar 2017 reaglos diferentes a los niños. ¿De cuántas maneras
lo pueden hacer si cada rey debe repartir como mínimo 500 regalos?

La primera conclusión a la que llegué (no del todo satisfactoria para mí y no sé si correcta) fue que se podía expresar la cantidad pedida como suma de permutaciones con repetición:

\(   \displaystyle\sum_{\substack{a_i\geq{}500 \\ a_1+a_2+a_3=2017}}PR_{a_1,a_2,a_3}^{2017}= \displaystyle\sum_{\substack{a_i\geq{}500 \\ a_1+a_2+a_3=2017}}\displaystyle\frac{2017!}{a_1!a_2!a_3!}  \)

Está bien.

Luego, a base de darle vueltas y de manera similar a lo que se hace con los números de Stirling, se me ocurrió definir una función \( f(n,k,m) \) que expresase el número de \( k \)-particiones que se pueden generar en un conjunto de \( n \) elementos de manera que todos los subconjuntos de una de las particiones tengan al menos \( m \) elementos (imagino que ya hay "inventado" algo así, pero lo descononzco). Dicha función tendría las siguientes propiedades recursivas (no sé si están bien):

\( f(n,k,m)=k\cdot{}f(n-1,k,m)+\displaystyle\binom{n-1}{k-1}\cdot{}f(n-m,k-1,m) \)
\( f(n,k,m)=0 \)   si \( m\cdot{}k>n \)
\( f(n,1,m)=1 \)   si \( m\leq{}n \)

Quizá deberías de decir particiones etiquetadas o distinguidas, porque por ejemplo en nuestro caso no sólo dividimos en tres grupos los juguetes, sino que interesa distinguir que grupo tocó a cada rey mago.

Por otra parte no acabo de ver la relación recursiva. Yo lo veo así. Dada una partición de \( n \) elementos distintos en \( k \)-partes etiquetadas, pertenece a uno de estos dos grupos:

- Particiones en las que el elemento \( 1 \) va a un grupo de más de \( m \) elementos. Hay \( kf(n-1,k,m) \) de estas particiones.

- Particiones en las que el elemento \( 1 \) va a a un grupo de exactamente \( m \) elementos. Hay \( k\cdot \displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \) de estas particiones. Entonces sería:

\( f(n,k,m)=\color{red}k\color{black}f(n-1,k,m)+k\cdot \displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \)

Saludos.

CORREGIDO

[martiniano]

Hola. Muchas gracias, Luis, por tu respuesta.

Quizá deberías de decir particiones etiquetadas o distinguidas, porque por ejemplo en nuestro caso no sólo dividimos en tres grupos los juguetes, sino que interesa distinguir que grupo tocó a cada rey mago.

Sí claro, disculpa. Es que mi intención inicial era responder con \( 3!f(2017,3,500) \), pero al escribir me comí parte de la respuesta.

Por otra parte no acabo de ver la relación recursiva. Yo lo veo así. Dada una partición de \( n \) elementos distintos en \( k \)-partes etiquetadas, pertenece a uno de estos dos grupos:

- Particiones en las que el elemento \( 1 \) va a un grupo de más de \( m \) elementos. Hay \( kf(n-1,k,m) \) de estas particiones.

- Particiones en las que el elemento \( 1 \) va a a un grupo de exactamente \( m \) elementos. Hay \( k \)\( \cdot \displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \) de estas particiones.

Sí, también tengo errores ahí. Vaya hombre... En efecto, en la segunda parte me he confundido entre "emes" y "kas"  . No obstante, no entiendo por qué multiplicas por \( k \) (en rojo), en esa parte.

A ver si lo aclaramos. A los \( n \) elementos que tenemos le quitamos el primero y hacemos un subconjunto con \( m-1 \) elementos de los \( n-1 \) que quedan. Eso se puede hacer de \( \displaystyle\binom{n-1}{m-1} \) maneras diferentes. Colocamos en ese subconjunto el elemento que habíamos quitado y multiplicamos por el número de \( (k-1) \)-particiones que se pueden hacer con los elementos que quedan, que son \( n-m \), de manera que ningún subconjunto tenga menos de \( m \) elementos, es decir por \( f(n-m,k-1,m) \). ¿Y creo que ya estaría, no? ¿qué es lo que me falta?

Entonces sería:
\( f(n,k,m)=k \)\( ( \)\( f(n-1,k,m)+k\cdot \displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \)

Intuyo que el paréntesis en rojo sobra, pero pregunto por si se me ha escapado algo y tu intención era cerrarlo en algún sitio.

Saludos y muchas gracias.

[Luis Fuentes]

Hola

No obstante, no entiendo por qué multiplicas por \( k \) (en rojo), en esa parte.

A ver si lo aclaramos. A los \( n \) elementos que tenemos le quitamos el primero y hacemos un subconjunto con \( m-1 \) elementos de los \( n-1 \) que quedan. Eso se puede hacer de \( \displaystyle\binom{n-1}{m-1} \) maneras diferentes. Colocamos en ese subconjunto el elemento que habíamos quitado y multiplicamos por el número de \( (k-1) \)-particiones que se pueden hacer con los elementos que quedan, que son \( n-m \), de manera que ningún subconjunto tenga menos de \( m \) elementos, es decir por \( f(n-m,k-1,m) \). ¿Y creo que ya estaría, no? ¿qué es lo que me falta?

La clave está precisamente en si consideras particiones etiquetadas o no; yo estaba pensando en etiquetadas y tu no, de ahí la diferencia.

Me explico: si llamamos \( g(n,k,m) \) al número de particiones de \( n \) elementos distintos en \( k \) partes todas ellas con al menos \( m \) términos y \( f(n,k,m) \) al número de particiones de \( n \) elementos en \( k \) partes etiquetadas todas ellas con \( m \) términos, tenemos:

\( g(n,k,m)=kg(n-1,k,m)+\displaystyle\binom{n-1}{m-1}g(n-m,k-1,m) \) (*)

\( f(n,k,m)=kf(n-1,k,m)+k\displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \) (**)

En el segundo caso hay que multiplicar por \( k \), porque el grupo en el que está el elemento \( 1 \) puede ser cualquiera de nuestras \( k \) "cajas etiquetadas"; en el caso anterior esta distinción no procedía porque las cajas se suponen indistinguibles.

Fíjate que si en (**) tomas \( f(n,k,m)=k!g(n,k,m) \) obtienes (*).

Entonces sería:
\( f(n,k,m)=k \)\( ( \)\( f(n-1,k,m)+k\cdot \displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \)

Intuyo que el paréntesis en rojo sobra, pero pregunto por si se me ha escapado algo y tu intención era cerrarlo en algún sitio.

Iba a sacar factor común a \( k \) y luego me arrepentí...

Saludos.

[martiniano]

Hola

No obstante, no entiendo por qué multiplicas por \( k \) (en rojo), en esa parte.

A ver si lo aclaramos. A los \( n \) elementos que tenemos le quitamos el primero y hacemos un subconjunto con \( m-1 \) elementos de los \( n-1 \) que quedan. Eso se puede hacer de \( \displaystyle\binom{n-1}{m-1} \) maneras diferentes. Colocamos en ese subconjunto el elemento que habíamos quitado y multiplicamos por el número de \( (k-1) \)-particiones que se pueden hacer con los elementos que quedan, que son \( n-m \), de manera que ningún subconjunto tenga menos de \( m \) elementos, es decir por \( f(n-m,k-1,m) \). ¿Y creo que ya estaría, no? ¿qué es lo que me falta?

La clave está precisamente en si consideras particiones etiquetadas o no; yo estaba pensando en etiquetadas y tu no, de ahí la diferencia.

Me explico: si llamamos \( g(n,k,m) \) al número de particiones de \( n \) elementos distintos en \( k \) partes todas ellas con al menos \( m \) términos y \( f(n,k,m) \) al número de particiones de \( n \) elementos en \( k \) partes etiquetadas todas ellas con \( m \) términos, tenemos:

\( g(n,k,m)=kg(n-1,k,m)+\displaystyle\binom{n-1}{m-1}g(n-m,k-1,m) \) (*)

\( f(n,k,m)=kf(n-1,k,m)+k\displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \) (**)

En el segundo caso hay que multiplicar por \( k \), porque el grupo en el que está el elemento \( 1 \) puede ser cualquiera de nuestras \( k \) "cajas etiquetadas"; en el caso anterior esta distinción no procedía porque las cajas se suponen indistinguibles.

Fíjate que si en (**) tomas \( f(n,k,m)=k!g(n,k,m) \) obtienes (*).

Entonces sería:
\( f(n,k,m)=k \)\( ( \)\( f(n-1,k,m)+k\cdot \displaystyle\binom{n-1}{m-1}f(n-m,k-1,m) \)

Intuyo que el paréntesis en rojo sobra, pero pregunto por si se me ha escapado algo y tu intención era cerrarlo en algún sitio.

Iba a sacar factor común a \( k \) y luego me arrepentí...

Saludos.

 

Muchas gracias Luis. Una explicación clarísima que ha despejado toda oscuridad. Qué paciencia la tuya. Me había hecho un lío yo solito. Jajaja.

Saludos y gracias.

[martiniano]

Hola.

Voy a dejar mis mensajes anteriores tal y como están y voy a escribir aquí la solución para que nadie se pierda.

SOLUCIÓN DEFINITIVA:

Sea \( g(n,k,m) \) una función \( g:\mathbb{N}^3\rightarrow{}\mathbb{N} \) tal que:

\( g(n,k,m)=kg(n-1,k,m)+\displaystyle\binom{n-1}{m-1}g(n-m,k-1,m) \)
\( g(n,k,m)=0 \)  si \( m\cdot{}k>n \)
\( g(n,1,m)=1 \)  si \( m\leq{}n \)

Entonces los reyes magos pueden repartirse la tarea de \( 3!g(2017,3,500) \) maneras diferentes.

Saludos.