OliForum Matematico

Siano $n,k$ due interi positivi fissati. Quante sono le sequenze di sottoinsiemi $X_1,X_2,\ldots,X_k$ di $\{1,2,\ldots,n\}$ tali che $\bigcap_{i=0}^k{X_i}= \emptyset$ ?

Scusa Jordan ma non capisco la domanda.
Supponiamo $ k=5 $ ed $ n=10 $. Devo trovare le sequenze di 5 sottoinsiemi in modo tale che: $ \bigcap_{i=0}^{10}{X_i}= \emptyset $, ma visto che $ n>k $ che senso ha? Non dovrebbe essere $ \bigcap_{i=0}^{k}{X_i}= \emptyset $?

Edito subito, thank you

Beh, se ad uno non viene in mente come contare subito tutti e soli i modi di prendere tali insiemi, può anche prenderne in eccesso, prima, quindi togliere il superfluo...

Fissato $k$ e detto $f(n)$ il numero cercato, vogliamo dimostrare per induzione su $n$ che $f(n)=(2^k-1)^n$
Per $n=0$ deve essere $ X_i=\emptyset \ \forall \ 1\leq i \leq k $, quindi $f(0)=1$.
Supponiamo che $f(i)=(2^k-1)^i \ \forall \ 0\leq i < n$.
Per ogni $Y\subseteq \{1,2,\ldots,n\}$ esistono esattamente $f(n-|Y|)$ ennuple di sottoinsiemi $X_1,X_2,\ldots,X_k$ di $\{1,2,\ldots,n\}$ tali che $\displaystyle\bigcap_{i=1}^k{X_i}=Y$, in quanto $\displaystyle \bigcap_{i=1}^k{\biggl(X_i\setminus Y \biggl)}= \emptyset$; inoltre abbiamo $\displaystyle \binom{n}{|Y|}$ modi di prendere $Y\subseteq \{1,2,\ldots,n\}$. Quindi
$\displaystyle f(n)=|\{(X_1,X_2,\ldots,X_k) \ : \ X_i\subseteq \{1,2,\ldots,n+1\} \}|-\sum_{j=1}^{n}{\biggl\{\biggl|(X_1,X_2,\ldots,X_k) \ : \ X_i\subseteq \{1,2,\ldots,n+1\} , \biggl|\bigcap_{i=1}^k{X_i}\biggl|= j\biggl|\biggl\}}=$
$\displaystyle =2^{kn}-\sum_{j=1}^{n}{\binom{n}{j}f(n-j)}=2^{kn}-\sum_{j=1}^{n}{\binom{n}{j}(2^k-1)^{n-j}}=2^{kn}-(2^{kn}-(2^k-1)^n)=(2^k-1)^n$

Seconda soluzione, un po' più decente.

Fissato $k$, sia $f(n)$ il numero cercato.
Sia $X_1,X_2,\ldots,X_k$ una sequenza di sottoinsiemi di $\{1,2,…,n\}$ tali che $\displaystyle \bigcap_{i=1}^k{X_i}= \emptyset$.
Per ogni $1\leq i \leq k$ sia $Y_i\subseteq \{1,2,…,n+1\}$ tale che $ Y_i=X_i \vee Y_i=X_i\cup\{n+1\} $, purchè valga $ Y_i=X_i $ per almeno un $i$. Osserviamo che $\displaystyle \bigcap_{i=1}^k{Y_i}= \emptyset$. Inoltre ovviamente per ogni $ (Y_1, Y_2,\ldots,Y_k) $ tale che $ Y_i\subseteq \{1,2,…,n+1\} $, $\displaystyle \bigcap_{i=1}^k{Y_i}= \emptyset$, vale $\displaystyle \bigcap_{i=1}^k{(Y_i\setminus\{n+1\})}= \emptyset$.
Quindi $ f(n+1)=(2^k-1)f(n) $, da cui, dato che $ f(0)=1 $, $ f(n)=(2^k-1)^n $

c'è una soluzione più breve (e forse più intuitiva)... hint nascosto.