Esercizio di combinatoria (numero di terne tali che...)
Sia $X={1,2,...,n}$
Calcolare il numero di terne ordinate $(A,B,C)$ di sottoinsiemi di $X$ a due a due disgiunti con $A U B U C=X$
Non sono pratico di esercizi di combinatoria, forse non è neanche la sezione giusta.
Gradirei comunque un qualsiasi hint, non una soluzione completa (almeno per ora), perchè al momento brancolo nella penombra piuttosto scura.
Vi dico a grandi linee la mia grossolana idea: chiamo $a=|A|$, $b=|B|$, $c=|C|$. Poichè i tre insiemi devono formare una partizione di $X$, deve essere $a+b+c=n$.
L'insieme $A$ (con $a$ elementi) posso sceglierlo in $((n),(a))$ modi, l'insieme $B$ è un insieme di b elementi scelti fra $n-b$ (devono essere a due a due disgiunti), quindi B lo scelgo in $((n-a),(b))$ modi. Infine l'insieme C posso sceglierlo in $((n-a-b),(c))=((c),(c))=1$ modi. Quindi ho $((n),(a))*((n-a),(b))$ scelte, una volta scelti $a$ e $b$ (e una volta scelti $a$ e $b$ ho che $c$ è univoco). I modo di scegliere una coppia $(a,b)$ sono $n-c+1$, cioè il numero di soluzioni di $a+b=n-c$.
Ma qui mi blocco, probabilmente è un approccio totalmente sbagliato.
Vi ringrazio per l'aiuto che sicuramente mi offrirete.
Calcolare il numero di terne ordinate $(A,B,C)$ di sottoinsiemi di $X$ a due a due disgiunti con $A U B U C=X$
Non sono pratico di esercizi di combinatoria, forse non è neanche la sezione giusta.
Gradirei comunque un qualsiasi hint, non una soluzione completa (almeno per ora), perchè al momento brancolo nella penombra piuttosto scura.
Vi dico a grandi linee la mia grossolana idea: chiamo $a=|A|$, $b=|B|$, $c=|C|$. Poichè i tre insiemi devono formare una partizione di $X$, deve essere $a+b+c=n$.
L'insieme $A$ (con $a$ elementi) posso sceglierlo in $((n),(a))$ modi, l'insieme $B$ è un insieme di b elementi scelti fra $n-b$ (devono essere a due a due disgiunti), quindi B lo scelgo in $((n-a),(b))$ modi. Infine l'insieme C posso sceglierlo in $((n-a-b),(c))=((c),(c))=1$ modi. Quindi ho $((n),(a))*((n-a),(b))$ scelte, una volta scelti $a$ e $b$ (e una volta scelti $a$ e $b$ ho che $c$ è univoco). I modo di scegliere una coppia $(a,b)$ sono $n-c+1$, cioè il numero di soluzioni di $a+b=n-c$.
Ma qui mi blocco, probabilmente è un approccio totalmente sbagliato.
Vi ringrazio per l'aiuto che sicuramente mi offrirete.
Risposte
C'è un rilancio. Il secondo punto dice:
"Dimostrare che il numero di terne ordinate $(A,B,C,)$ di sottoinsiemi di $X$ tali che $AuuBuuC=X$ è $7^n$"
Stavolta non devono essere a due a due disgiunti.
Il fatto che non vada trovato il numero, ma dimostrare che è uguale a un valore dato, mi fa pensare che:
1) è difficile trovarlo autonomamente
2)si debba dimostrare per induzione.
Vi propongo la mia dimostrazione, attendendo commenti.
caso base: se $n=1$ l'insieme è $X={1}$, con un solo elemento. In quanto modi posso mettere questo unico elemento nei tre insiemi. Vediamo ( nel seguito "0" indica l'insieme vuoto, e una colonna indica una terna )
$A$ 1 0 0 1 0 1 1
$B$ 0 1 0 1 1 0 1
$C$ 0 0 1 0 1 1 1
Per $A$ ho 2 scelte ($emptyset$ e ${1}$), per $B$ e $C$ lo stesso, per un totale di $2^3$ scelte, ma da queste devo togliere la terna $(emptyset,emptyset,emptyset)$, dato che l'unione deve fare $X$. Ho quindi $7$ scelte, e il caso base è dimostrato.
Suppongo ora che le terne del tipo richiesto, con $X_n={1,...,n}$, siano $7^n$, e vediamo se questo mi implica che anche le terne di insiemi la cui unione copre $X_(n+1)={1,...,n+1}$ siano $7^(n+1)$
Prese le $7^n$ terne che "coprono" $X_n$, devo aggiungere in qualche modo l'elemento $n+1$.
La situazione è adesso la stessa del caso base, in quanto se $u=(A',B',C')$ è una terna di quelle contate prima (di quelle che coprono $X_n$), una terna $w$ che copre $X_(n+1)$ sarà del tipo $w=(A'uuA'',B'uuB'',C'uuC'')$, dove $A''$, $B''$, $C''$ sono insiemi che possono contenere o no l'n+1-esimo elemento, cioè $A''$ è uguale a ${n+1}$ o a $emptyset$, e cosi gli altri 2.
Il numero di terne $w$ sarà quindi uguale al numero di terne del tipo $u$ per il numero di modi di scegliere $A''$, $B''$, $C''$. Ognuno di questi 3 insiemi può essere scelto in $2$ modi, ottenendo $8$ scelte, da cui però va ancora tolto il caso $A''=B''=C''=emptyset$, poichè sennò non si coprirebbe più l'intero insieme $X_(n+1)$. Di conseguenza le scelte per la terne di tipo $w$ sono $7^n*7=7^(n+1)$, e la per il principio di induzione la tesi è dimostrata per ogni $n$.
Che ne dite, va bene?
EDIT: A ben pensarci, forse è più semplice del previsto, anche senza induzione. Nell'esercizio precedente, avevo che per l'elemento $1$ avevo 3 scelte ( in A,B,o C), per il $2$ uguale,e così via fino all'elemento $n$, per un totale di $3^n$ scelte. Stavolta posso ragionare così: ogni elemento posso mandarlo in $7$ posti (in A, in B, in C, in A e B, A e C, B e C, A e B e C). Quindi ho $7^n$ modi. Regge quest'ultimo ragionamento?
"Dimostrare che il numero di terne ordinate $(A,B,C,)$ di sottoinsiemi di $X$ tali che $AuuBuuC=X$ è $7^n$"
Stavolta non devono essere a due a due disgiunti.
Il fatto che non vada trovato il numero, ma dimostrare che è uguale a un valore dato, mi fa pensare che:
1) è difficile trovarlo autonomamente
2)si debba dimostrare per induzione.
Vi propongo la mia dimostrazione, attendendo commenti.
caso base: se $n=1$ l'insieme è $X={1}$, con un solo elemento. In quanto modi posso mettere questo unico elemento nei tre insiemi. Vediamo ( nel seguito "0" indica l'insieme vuoto, e una colonna indica una terna )
$A$ 1 0 0 1 0 1 1
$B$ 0 1 0 1 1 0 1
$C$ 0 0 1 0 1 1 1
Per $A$ ho 2 scelte ($emptyset$ e ${1}$), per $B$ e $C$ lo stesso, per un totale di $2^3$ scelte, ma da queste devo togliere la terna $(emptyset,emptyset,emptyset)$, dato che l'unione deve fare $X$. Ho quindi $7$ scelte, e il caso base è dimostrato.
Suppongo ora che le terne del tipo richiesto, con $X_n={1,...,n}$, siano $7^n$, e vediamo se questo mi implica che anche le terne di insiemi la cui unione copre $X_(n+1)={1,...,n+1}$ siano $7^(n+1)$
Prese le $7^n$ terne che "coprono" $X_n$, devo aggiungere in qualche modo l'elemento $n+1$.
La situazione è adesso la stessa del caso base, in quanto se $u=(A',B',C')$ è una terna di quelle contate prima (di quelle che coprono $X_n$), una terna $w$ che copre $X_(n+1)$ sarà del tipo $w=(A'uuA'',B'uuB'',C'uuC'')$, dove $A''$, $B''$, $C''$ sono insiemi che possono contenere o no l'n+1-esimo elemento, cioè $A''$ è uguale a ${n+1}$ o a $emptyset$, e cosi gli altri 2.
Il numero di terne $w$ sarà quindi uguale al numero di terne del tipo $u$ per il numero di modi di scegliere $A''$, $B''$, $C''$. Ognuno di questi 3 insiemi può essere scelto in $2$ modi, ottenendo $8$ scelte, da cui però va ancora tolto il caso $A''=B''=C''=emptyset$, poichè sennò non si coprirebbe più l'intero insieme $X_(n+1)$. Di conseguenza le scelte per la terne di tipo $w$ sono $7^n*7=7^(n+1)$, e la per il principio di induzione la tesi è dimostrata per ogni $n$.
Che ne dite, va bene?
EDIT: A ben pensarci, forse è più semplice del previsto, anche senza induzione. Nell'esercizio precedente, avevo che per l'elemento $1$ avevo 3 scelte ( in A,B,o C), per il $2$ uguale,e così via fino all'elemento $n$, per un totale di $3^n$ scelte. Stavolta posso ragionare così: ogni elemento posso mandarlo in $7$ posti (in A, in B, in C, in A e B, A e C, B e C, A e B e C). Quindi ho $7^n$ modi. Regge quest'ultimo ragionamento?
"alvinlee88":
EDIT: A ben pensarci, forse è più semplice del previsto, anche senza induzione. Nell'esercizio precedente, avevo che per l'elemento $1$ avevo 3 scelte ( in A,B,o C), per il $2$ uguale,e così via fino all'elemento $n$, per un totale di $3^n$ scelte. Stavolta posso ragionare così: ogni elemento posso mandarlo in $7$ posti (in A, in B, in C, in A e B, A e C, B e C, A e B e C). Quindi ho $7^n$ modi. Regge quest'ultimo ragionamento?
Yes
E, inutile dirlo, $7^n$ volte meglio dell'induzione 
In effetti la seconda idea mi è venuta a fare la doccia, ed è sensibilmente più semplice.
Ma la dimostrazione per induzione (per quanto inutile e lunga) in cosa è sbagliata?
Ma la dimostrazione per induzione (per quanto inutile e lunga) in cosa è sbagliata?
"alvinlee88":
Ma la dimostrazione per induzione (per quanto inutile e lunga) in cosa è sbagliata?
E' giusta; non e' altro che la versione per induzione della seconda. A dirla tutta, se si dovesse formalizzare la prova in un linguaggio comprensibile ad un robot, si dovrebbe usare la tua prima dimostrazione
Per noi umani, direi, è sufficiente la seconda
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo