4 votos

Número de posibilidades para n personas en m tablas con al menos 5 personas por mesa

dado son n las personas y m tablas, con $ n \geq 5m $.

¿Cuántas posibilidades hay, para poner a las personas a la m tablas, de modo que en cada mesa son al menos 5 personas? La disposición de las personas en una mesa, no importa. También las tablas no son distinguibles.

Pensé en el segundo número de Stirling. Como se describe en el número de posibilidades para k no vacía de conjuntos de n elementos, de modo que cada elemento es exactamente un juego. Pero con este no me tome en cuenta, que necesito al menos 5 elementos en cada conjunto.

Cómo puedo solucionar este problema o es que hay un enfoque que se adapta mejor a este problema?

Saludos cordiales, Niklas

4voto

Andrew Woods Puntos 1579

Deje $S_5(n,m)$ el número de maneras para $n$ a las personas a sentarse en $m$ tablas idénticas, al menos, cinco en cada uno.

Supongamos que llega una nueva persona, lo que es una multitud de $n+1$ de la gente.

  • La nueva persona puede sentarse en una de las mesas que ya están allí. Tienen $m$ opciones, así que no hay $m\cdot S_5(n,m)$ acuerdos de este tipo, para ser incluido en $S_5(n+1,m)$.

  • La nueva persona puede sacar una nueva tabla (aumento de la $m$ por uno), y cuatro de las personas que ya están presentes a sentarse con ellos. Hay $\binom{n}4\cdot S_5(n-4,m)$ acuerdos de este tipo, para ser incluido en $S_5(n+1,m+1)$.

    • (Si la persona nueva reclutado a más de cuatro personas para la nueva tabla, entonces el resultado sería indistinguible de una situación incluidos en el primer caso para $m'=m+1$, en el que la nueva tabla ya estaba ocupado. Por esa razón, no deben ser considerados por separado en la recurrencia.)

Por lo tanto $$S_5(n+1,m)=m\cdot S_5(n,m)+\tbinom{n}4\cdot S_5(n-4,m-1)$$

(Tenga en cuenta que esta fórmula el índice final es $m-1$, tal y como este término representa un movimiento a partir de una situación con $m-1$ tablas a uno con $m$.)

Inicio de una hoja de cálculo con $S_5(n,1)=1$ todos los $n\ge5$, e $S_5(n,m)=0$$n<5m$.

A continuación,$S_5(10,2)=2\cdot0+\tbinom94\cdot1=126$, y la recurrencia puede continuar:

$$\begin{array}{c|crr}&1&2&3\\\hline 9&1\\10&1&126\\11&1&462\\12&1&1254\\13&1&3003\\14&1&6721\\15&1&14443&126126\\16&1&30251&1009008\\17&1&62322&5309304\\18&1&127024&23075052\end{array}$$

Este es OEIS A059024.

1voto

Markus Scheuer Puntos 16133

Aquí es una expresión algebraica enfoque basado en la generación de funciones. En primer lugar, tomamos nota de los números de Bell dando el número de particiones de un $n$ elemento del conjunto tiene la siguiente representación \begin{align*} {\mathop{Set}}_{\geq 0}({\mathop{Set}}_{\geq 1}(\{1\}))\qquad\Longrightarrow\qquad e^{e^z-1} \end{align*} Este enfoque y la siguiente considerable de generalización se puede encontrar en la sección II.3.1 en la Analítica de la combinatoria por P. Flajolet y R. Sedgewick.

La clase $S^{(A,B)}$ de las particiones del conjunto con tamaños de bloque en $A\subseteq \mathbb{Z}_{\geq 1}$ y con un número de bloques que pertenece a $B$ ha exponencial de generación de función

\begin{align*} S^{(A,B)}(z)=\beta(\alpha(z))\qquad\text{where}\qquad \alpha(z)=\sum_{a\in A}\frac{z^a}{a!},\quad \beta(z)=\sum_{b\in B}\frac{z^b}{b!}\tag{1} \end{align*}

Usamos (1) para obtener una generación de función para $S_5(n,m)$, el número de maneras para $n$ a las personas a sentarse en $m$ indistinguibles de las tablas, al menos, cinco en cada uno.

La generación de la función: Dado que el número de personas en cada mesa es de al menos $5$, podemos establecer \begin{align*} A=\mathbb{Z}_{\geq 5}\qquad\text{where}\qquad \alpha(z)=\sum_{n\geq 5}\frac{z^n}{n!}=e^z-\sum_{j=0}^4\frac{z^j}{j!} \end{align*} Dado que el número de mesas es $m$, podemos establecer \begin{align*} B=\mathbb{Z}_{= 4}=\{4\}\qquad\text{where}\qquad \beta(z)=\frac{z^4}{4!} \end{align*}

Obtenemos una generación de función $\beta(\alpha(z))$ $S_5(n,m)$ \begin{align*} \color{blue}{\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}=\frac{1}{m!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^m}\tag{2} \end{align*}

Podemos utilizar la generación de función (2) para obtener una relación de recurrencia para $S_5(n,m)$.

La recurrencia de la relación:

Obtenemos

\begin{align*} \frac{d}{dz}\left(\frac{1}{m!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^m\right) &=\frac{d}{dz}\left(\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}\right)\\ &=\sum_{n=5m}^\infty S_5(n,m)\frac{z^{n-1}}{(n-1)!}\\ &=\sum_{n=5m-1}^\infty S_5(n+1,m)\frac{z^{n}}{n!}\tag{3}\\ \end{align*}

Por otro lado, obtenemos \begin{align*} \frac{d}{dz}&\left(\frac{1}{m!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^m\right)\\ &=\frac{1}{(m-1)!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^{m-1} \left(e^z-\sum_{j=1}^4\frac{z^{j-1}}{(j-1)!}\right)\\ &=\frac{1}{(m-1)!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^m +\frac{z^4}{4!}\cdot\frac{1}{(m-1)!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^{m-1}\\ &=m\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}+\frac{z^4}{4!}\sum_{n=5m-5}^\infty S_5(n,m-1)\frac{z^n}{n!}\\ &=m\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}+\frac{1}{4!}\sum_{n=5m-1}^\infty S_5(n-4,m-1)\frac{z^{n}}{(n-4)!}\\ &=m\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}+\binom{n}{4}\sum_{n=5m-1}^\infty S_5(n-4,m-1)\frac{z^{n}}{n!}\tag{4}\\ \end{align*}

Coeficiente de comparación de (3) y (4) por $n\geq 5m$ resultados en \begin{align*} \color{blue}{S_5(n+1,m)=mS_5(n,m)+\binom{n}{4}S_5(n-4,m-1)} \end{align*}

0voto

andy.gurin Puntos 1516

Primero debe crear particiones válidas de$n$ con al menos$5$ personas en cada tabla. Para$m$ =$7$, por ejemplo, que una partición válida de$n$ sea$a,a,b,b,b,c,d,\;with\; a,b,c,d\ge5$

Entonces la cantidad de formas para esta partición =$\dfrac{\binom{2a+3b+c+d}{a,a,b,b,b,c,d}}{2!3!}= \dfrac{\binom{n}{a,a,b,b,b,c,d}}{2!3!}= $ $

Haga ejercicio de manera similar para todas las particiones válidas, y sume.

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