$\bigcap_{i=0}^n{X_i}= \emptyset$

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da jordan »

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$ ?
Ultima modifica di jordan il 14 gen 2013, 13:54, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: $\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da Hawk »

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 $?
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da jordan »

Edito subito, thank you
The only goal of science is the honor of the human spirit.
Avatar utente
Tess
Messaggi: 272
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: $\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da Tess »

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...
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: $\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da kalu »

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$
Ultima modifica di kalu il 17 gen 2013, 20:42, modificato 2 volte in totale.
Pota gnari!
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: $\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da kalu »

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 $
Pota gnari!
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: $\bigcap_{i=0}^n{X_i}= \emptyset$

Messaggio da ma_go »

c'è una soluzione più breve (e forse più intuitiva)... hint nascosto.
Testo nascosto:
se $\bigcap X_i = \varnothing$, allora $\bigcup X_i^c = ?$...
Rispondi