Ordenado $k$ -cubiertas de $[n]$

Question

Una orden $k$ -cubierta de $[n]$ , para $k\in\mathbb{P}$ y $n\in\mathbb{N}$ es una secuencia $(A_1,\dots,A_k)$ de subconjuntos de $[n]$ tal que $A_1\cup\dots\cup A_k=[n]$ . Si $m(n,k)$ es el número de ordenadas $k$ -cubiertas de $[n]$ Entonces, ¿es correcta esta fórmula (por el principio de inclusión y exclusión)?

$$m(n,k)=2^{n}-\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}j^{n}$$

No sé cómo simplificarlo más .... Cualquier ayuda será muy apreciada.

Answer 1

Dado el comentario de Dome del 17/09/13 interpreto la pregunta de la siguiente manera: Tenemos que contar el número de $k$ -tuplas $(A_1,A_2,\ldots,A_k)$ de subconjuntos $A_i\subset[n]$ teniendo la propiedad $\bigcup_{1\leq i\leq k}A_i=[n]$ .

Esto significa que para cada número $\ell\in[n]$ podemos decidir libremente en qué $A_i$ , $\>1\leq i\leq k$ se producirá, con la única condición de que se produzca en al menos uno de los $A_i$ . En otras palabras: Tenemos que seleccionar para cada $\ell\in[n]$ un subconjunto no vacío $J_\ell\subset[k]$ . Cuando estos conjuntos $J_\ell$ han sido seleccionadas put $$A_i:=\bigl\{\ell\in[n]\ \bigm|\ i\in J_\ell\bigr\}\qquad(1\leq i\leq k)\ .$$ Hay $2^k-1$ subconjuntos no vacíos de $[k]$ y podemos seleccionar uno de ellos independientemente para cada $\ell\in[n]$ . Por lo tanto, el número total $N$ de admisibles $k$ -tuplas $(A_1,A_2,\ldots,A_k)$ viene dada por $$N=\left(2^k-1\right)^n\ .$$

Answer 2

Este es un argumento que utiliza la inclusión-exclusión, pero la solución de Christian Blatter es mucho más sencilla:

Sea S el conjunto de todas las selecciones ordenadas de k subconjuntos de $[n]$ y que $E_{i}$ sea el conjunto de selecciones que no tienen el elemento i en la unión de los subconjuntos, para $1\le i\le n$ .

Entonces $\displaystyle \vert \overline{E_{1}}\cap\cdots\cap\overline{E_{n}}\vert=\vert S\vert-\sum_{i}\vert E_{i}\vert+\sum_{i<j}\vert E_{i}\cap E_{j}\vert-\cdots$

$\displaystyle\;\;\;\;\;=2^{nk}-\binom{n}{1}2^{(n-1)k}+\binom{n}{2}2^{(n-2)k}-\binom{n}{3}2^{(n-3)k}+\cdots+(-1)^{n-1}\binom{n}{n-1}2^k+(-1)^n$

$\displaystyle\;\;\;\;\;=x^n-\binom{n}{1}x^{n-1}+\binom{n}{2}x^{n-2}-\binom{n}{3}x^{n-3}+\cdots+(-1)^{n-1}\binom{n}{n-1}x+(-1)^n$

$\displaystyle\;\;\;\;\;=(x-1)^n=(2^k-1)^n$ , utilizando $x=2^k$ .