Función generadora del número de formas en que n personas pueden elegir un total de r1 sillas de tipo 1, r2 sillas de tipo 2, etc.

Question

Esta es una pregunta de tarea para mi clase de combinatoria que sólo necesito que me indiquen la dirección correcta para empezar.

Encontrar una función generadora $x_1, x_2, . . . , x_m$ cuyo coeficiente de $x_1^{r_1} x_2^{r_2} . . . x_m^{r_m}$ es el número de formas $n$ la gente puede elegir un total de $r_1$ sillas de tipo $1$ , $r_2$ sillas de tipo $2$ , . . . $r_m$ sillas de tipo $m$ si (a, b y c son escenarios únicos y separados)

(a) Cada persona elige una silla

(b) Cada persona elige dos sillas de un tipo o ninguna silla

(c) Persona $i$ recoge hasta $i$ sillas de un solo tipo

Answer 1

Idea básica: [Estoy resolviendo sólo la parte a]

a)

---

Dejemos que $P(r_1,r_2,...,r_m)$ denotan el número de formas en que n personas pueden elegir un total de $r_1$ sillas de tipo 1, $r_2$ sillas de tipo 2, . . . $r_m$ sillas de tipo m de forma que cada persona elija una silla. Claramente, $$n=r_1+r_2+...+r_m$$

Reclamación $$P(r_1,r_2,...,r_m) = {n\choose r_1}*{(n-r_1)\choose r_2}...{(n-(r_1+r_2+...+r_{m-2})\choose r_{m-1}}*{r_m\choose r_m} $$ $$= n! / (r_1!r_2!...r_m!) = {n \choose r_1,r_2,..,r_m}$$ [Conocido como coeficiente multinomial]

Prueba :Usted selecciona $r_1$ personas de n que recibirán silla de tipo 1 en ${n\choose r_1}$ formas, a continuación se selecciona $r_2$ personas de las restantes que recibirán silla de tipo 2 en ${(n-r_1)\choose r_2}$ formas, etc.

---

Así, su función generadora F es, $$ F(x_1,x_2,..,x_m) = \sum_{r_1+r_2+...+r_m=n}P(r_1,r_2,...,r_m)*x_1^{r_1}*x_2^{r_2}...*x_2^{r_m}$$ $$=\sum_{r_1+r_2+...+r_m=n}{n \choose r_1,r_2,..,r_m}*x_1^{r_1}*x_2^{r_2}...*x_m^{r_m} = (x_1+x_2+...+x_m)^n$$

También se conoce como distribución multinomial. Se puede encontrar la función generadora para b) y c) de forma similar.