Relazioni d'equivalenza su insieme.
Ciao,
Devo risolvere questo esercizio e non sò se ci sia un metodo più sbrigativo di quello che uso io...
L'esercizio è il seguente:
Determinare il numero delle relazioni d'equivalenza su un insieme composto da sette elementi con la proprietà che una classe di equivalenza abbia 4 elementi.
Allora:
{1,2,3,4,5,6,7}
Una classe deve contenere 4 elementi
${{1,2,3,4}{5,6,7}}$ può essere una partizione a cui è associata una relazione d'equivalenza che è proprio quella in cui le classi d'equivalenza sono quelle definite.
${{1}{2,3,4,5}{6,7}}$ potrebbe esserne un altra
${{1,2}{3,4,5,6}{7}}$ un altra ancora..
Ma se vado avanti così non finisco più o meglio è molto lunga, specialmente se posso cambiare l'ordine degli elementi nell'insieme (si può vero?)
c'è un modo per determinare quante relazioni d'equivalenza possono essere create su un dato insieme?
Grazie mille
Devo risolvere questo esercizio e non sò se ci sia un metodo più sbrigativo di quello che uso io...
L'esercizio è il seguente:
Determinare il numero delle relazioni d'equivalenza su un insieme composto da sette elementi con la proprietà che una classe di equivalenza abbia 4 elementi.
Allora:
{1,2,3,4,5,6,7}
Una classe deve contenere 4 elementi
${{1,2,3,4}{5,6,7}}$ può essere una partizione a cui è associata una relazione d'equivalenza che è proprio quella in cui le classi d'equivalenza sono quelle definite.
${{1}{2,3,4,5}{6,7}}$ potrebbe esserne un altra
${{1,2}{3,4,5,6}{7}}$ un altra ancora..
Ma se vado avanti così non finisco più o meglio è molto lunga, specialmente se posso cambiare l'ordine degli elementi nell'insieme (si può vero?)
c'è un modo per determinare quante relazioni d'equivalenza possono essere create su un dato insieme?
Grazie mille
Risposte
Secondo me non c'è bisogno che determini nome e cognome delle classi di equivalenza. Basta che conti le possibilità.
Devi scegliere una classe da 4 elementi: in quanti modi diversi puoi farlo?
Una volta scelta la classe da 4, devi suddividere i restanti 3 elementi: in quanti modi diversi puoi farlo?
Devi scegliere una classe da 4 elementi: in quanti modi diversi puoi farlo?
Una volta scelta la classe da 4, devi suddividere i restanti 3 elementi: in quanti modi diversi puoi farlo?
non erano, con $N!$ con $N=#A$
"dissonance":
Secondo me non c'è bisogno che determini nome e cognome delle classi di equivalenza. Basta che conti le possibilità.
Devi scegliere una classe da 4 elementi: in quanti modi diversi puoi farlo?
Una volta scelta la classe da 4, devi suddividere i restanti 3 elementi: in quanti modi diversi puoi farlo?
Non è come stavo facendo io? :S o forse non ho ben capito.
La classe da 4 elementi posso avere:
${{1,2,3,4} 5,6,7} o {{1{2,3,4,5}6,7} o {1,2{3,4,5,6}7} o {1,2,3{4,5,6,7}}$ ma anche ${{1,4,5,7}2,3,5}$ no? e per ognuna di esse ho varie possibilità di combinare i 3 elementi restanti.. Stò sbagliando?
non erano, con N! con N=#A
eh?
Grazie ancora a tutti per le risposte.
$N! = (n)(n-1)(n-2)...(n-(n-1))$(attenzione, $0! = 1$) è il fattoriale e $#A$ è la cardinalità dell'insieme
scritte così, no.
potevano andare quelle di prima, ti è stato solo fatto osservare che non puoi pretendere di elencarle tutte.
se le vuoi elencare "per tipologia", puoi considerare la prima che hai scritto nel primo messaggio ed una delle due successive, a cui però va aggiunta un'altra tipologia: quella con 4 classi di cui una di 4 elementi e 3 di 3 elementi.
puoi fare in due modi:
1) come ti ha suggerito dissonance, moltiplicando il numero di modi di scegliere 4 elementi per il numero delle partizioni che puoi fare con i rimanenti 3 elementi: viene un coefficiente binomiale per 5...
2) puoi partire dalle tre tipologie ed utilizzare i coefficienti multinomiali: li conosci?
io ho verificato che il risultato dei due calcoli è lo stesso.
prova a scrivere qualcosa. ora devo andare. più tardi penso di ricollegarmi. ciao.
potevano andare quelle di prima, ti è stato solo fatto osservare che non puoi pretendere di elencarle tutte.
se le vuoi elencare "per tipologia", puoi considerare la prima che hai scritto nel primo messaggio ed una delle due successive, a cui però va aggiunta un'altra tipologia: quella con 4 classi di cui una di 4 elementi e 3 di 3 elementi.
puoi fare in due modi:
1) come ti ha suggerito dissonance, moltiplicando il numero di modi di scegliere 4 elementi per il numero delle partizioni che puoi fare con i rimanenti 3 elementi: viene un coefficiente binomiale per 5...
2) puoi partire dalle tre tipologie ed utilizzare i coefficienti multinomiali: li conosci?
io ho verificato che il risultato dei due calcoli è lo stesso.
prova a scrivere qualcosa. ora devo andare. più tardi penso di ricollegarmi. ciao.
"Luc@s":
$N! = (n)(n-1)(n-2)...(n-(n-1))$(attenzione, $0! = 1$) è il fattoriale e $#A$ è la cardinalità dell'insieme
Si, questo lo sapevo fiu ehehe, ma come va applicato al mio problema, cioè il numero delle relazioni d'equivalenza applicabili all'insieme è il fattoriale con N = alla cardinalità dell'insieme?
scritte così, no.
potevano andare quelle di prima, ti è stato solo fatto osservare che non puoi pretendere di elencarle tutte.
yessaboy.
se le vuoi elencare "per tipologia", puoi considerare la prima che hai scritto nel primo messaggio ed una delle due successive, a cui però va aggiunta un'altra tipologia: quella con 4 classi di cui una di 4 elementi e 3 di 3 elementi.
Non è che mi sia fondamentale elencarle, era solo un metodo per me per trovare quante relazioni c'erano. Sperando che ci fossero metodi più veloci.
Ma si devono considerare anche partizioni in cui gli elementi non sono nell'ordine in cui compaiono nell'insieme?
${{1,2,3,4}{5,6,7}}}$
${{1}{2,3,4,5}{6,7}}$
${{1,2}{3,4,5,6}{7}}$
${{1,2,3}{4,5,6,7}}$
questi sono le suddivisioni per 4, poi per ognuna delle tre rimanenti posso averle o singole oppure due assieme e uno singolo, nonchè tutti e tre assieme.. quindi $4 x 3$ sarebbe? :m:
2) puoi partire dalle tre tipologie ed utilizzare i coefficienti multinomiali: li conosci?
Uhm no...
"whiterabbit":
Ma si devono considerare anche partizioni in cui gli elementi non sono nell'ordine in cui compaiono nell'insieme?
Secondo te ${a, b, c}$ è diverso da ${b,a,c}$ o da ${c,b,a}$? Se la risposta è sì, allora devi tenere conto dell'ordine. Altrimenti no.
No, rappresentano lo stesso insieme.. Però ciò che volevo dire io è che potrei prendere anche:
${{1,3,5,7}{2,4,6}}$
e quindi le possibilità sarebbero maggiori. No?
${{1,3,5,7}{2,4,6}}$
e quindi le possibilità sarebbero maggiori. No?
E certo. ${{1,3,5,7},{2,4,6}}$ mica è la stessa partizione di ${{1,2,3,4},{5,6,7}}$.
Quindi diamo per assodato che con i tre elementi rimanenti posso fare 4 composizioni giusto, ${{a}{b}{c}}$ ; ${{a,b}{c}}$ ; ${{a}{b,c}}$ ; ${{a,c}{b}}$ non mi resta che trovare quante composizioni posso fare con la classe di 4 elementi e moltiplicarle per 4..
Penso che hai capito ma ti sei espresso male. Io direi: una volta scelta la classe da 4 elementi, posso partizionare i restanti 3 in 4 modi diversi. Quindi per ogni scelta della classe da 4 posso avere 4 relazioni. Restano da contare le scelte possibili per la classe da 4.
Esatto, quello che volevo dire io.. 
Ma ora contare le scelte possibili per la classe di 4 su 7 elementi è ardua.. Cioè son tante le possibilità...
Metodi per permettermi di non saltare qualche scelta?
Ma ora contare le scelte possibili per la classe di 4 su 7 elementi è ardua.. Cioè son tante le possibilità...
Metodi per permettermi di non saltare qualche scelta?
Non è così arduo... E poi è un'operazione molto comune. Tanto che c'è un numero fatto apposta. Se mi dici che non sai come si chiama, non ci credo. E' che non ti sta venendo in mente.
per 3 tipologie intendevo:
1) ${{1,2,3,4},{5,6,7}}$
2) ${{1,2,3,4},{5,6},{7}}$
3) ${{1,2,3,4},{5},{6},{7}}$
è chiaro?
seguendo il procedimento di dissonance, lasciando {1,2,3,4} (poi però moltiplichiamo per il coefficiente binomiale $((7),(4))$), andiamo a vedere come possono essere collocati gli altre tre numeri 5,6,7:
{5,6,7}
{5,6}{7}, {5,7}{6}, {6,7}{5}
{5}{6}{7}
in 5 modi.... dunque?
altro procedimento che ti porta allo stesso risultato:
tipologia 1: $(7!)/(4!*3!)$
tipologia 2: $(7!)/(4!*2!*1!)$
tipologia 3: $(7!)/(4!*1!*1!*1!*3!)$
totale: $(7!)/(4!*3!)+(7!)/(4!*2)+(7!)/(4!*3!)=(7!)/(4!*3!)*(1+3+1)=(5*7!)/(4!*3!)=5*((7),(4))$
spero di aver chiarito qualche dubbio. ciao.
1) ${{1,2,3,4},{5,6,7}}$
2) ${{1,2,3,4},{5,6},{7}}$
3) ${{1,2,3,4},{5},{6},{7}}$
è chiaro?
seguendo il procedimento di dissonance, lasciando {1,2,3,4} (poi però moltiplichiamo per il coefficiente binomiale $((7),(4))$), andiamo a vedere come possono essere collocati gli altre tre numeri 5,6,7:
{5,6,7}
{5,6}{7}, {5,7}{6}, {6,7}{5}
{5}{6}{7}
in 5 modi.... dunque?
altro procedimento che ti porta allo stesso risultato:
tipologia 1: $(7!)/(4!*3!)$
tipologia 2: $(7!)/(4!*2!*1!)$
tipologia 3: $(7!)/(4!*1!*1!*1!*3!)$
totale: $(7!)/(4!*3!)+(7!)/(4!*2)+(7!)/(4!*3!)=(7!)/(4!*3!)*(1+3+1)=(5*7!)/(4!*3!)=5*((7),(4))$
spero di aver chiarito qualche dubbio. ciao.
Quindi ci sarebbero 175 possibili combinazioni?
uhm...
2) se l'esercizio fosse così:
{1,2,3,4,5,6,7} ogni classe contiene al più 3 elementi e 1 ~ 2 e 6 ~ 7
Come lo risolviamo?
Come prima direte voi.. e quindi avrei {{1,2}{6,7}{3,4,5}} gli ultimi 3 elementi hanno 5 possibilità come abbiamo visto prima.. però dopo posso mettere in classe anche {{1,2,3}}? o il fatto che 1 ~ 2 non ammette che ci siano anche altri elementi?
Grazie mille a tutti
Non è così arduo... E poi è un'operazione molto comune. Tanto che c'è un numero fatto apposta. Se mi dici che non sai come si chiama, non ci credo. E' che non ti sta venendo in mente.
uhm...
2) se l'esercizio fosse così:
{1,2,3,4,5,6,7} ogni classe contiene al più 3 elementi e 1 ~ 2 e 6 ~ 7
Come lo risolviamo?
Come prima direte voi.. e quindi avrei {{1,2}{6,7}{3,4,5}} gli ultimi 3 elementi hanno 5 possibilità come abbiamo visto prima.. però dopo posso mettere in classe anche {{1,2,3}}? o il fatto che 1 ~ 2 non ammette che ci siano anche altri elementi?
Grazie mille a tutti
ti dò un suggerimento: conosci il teorema del binomio di Newton? Sicuramente sì: in un anello commutativo (per esempio nei numeri reali),
$(a+b)^n=sum_{i=0}^n((n),(i))a^ib^(n-i)$.
Ti sei mai chiesto da dove esce quel coefficiente binomiale? Ti vengo incontro:
$(a+b)^n=(a+b)(a+b)...(a+b)$ n volte. Se sviluppi, ottieni la somma di tutte le possibili combinazioni di prodotti di $a$ e $b$ presi in tutto $n$ volte: cose come $aaba...b, bbab...a$ dove prendi un certo numero, diciamo $i$ di $a$ e moltiplichi $n-i$ fattori $b$. Quindi (prop. commutativa) è una somma di oggetti tipo $a^ib^(n-i)$. Ma non ogni $a^ib^(n-i)$ può essere ottenuto in un solo modo.
Ad esempio, $(a+b)^2=(a+b)(a+b)=a*a+a*b+b*a+b*b=aa+2ab+b b$, perché puoi ottenere il termine misto in 2 modi diversi. E se elevassimo al cubo, avrsti $(a+b)^3=(a+b)(a+b)(a+b)=a^3+3a^2b+3ab^2+b^3$ perché puoi ottenere i termini misti $a^2b, b^2a$ come $aab, aba, baa; b ba, bab, ab b$ ovvero in 3 modi diversi l'uno.
Osservazione importante: in ognuno degli addendi della sommatoria, una volta fissati i posti che dovranno occupare le $a$, i posti restanti vanno riempiti di $b$ e perciò sono già determinati. Quindi ogni $a^ib^(n-i)$ compare nella sommatoria esattamente tante volte quante le possibili combinazioni di i oggetti estratti tra n oggetti.
______________________________________________________________________________________________
Che cosa sto cercando di dire da mezz'ora? Che il teorema di Newton è solo una applicazione di un teorema più importante:
dato un insieme di $n$ oggetti, è possibile sceglierne $i$ (combinare $i$ oggetti scelti tra $n$) esattamente in $((n),(i))$ modi diversi.
Che c'entra questo col tuo problema? Molto, visto che, in sostanza, questo si riduce a contare varie combinazioni di elementi di un insieme finito.
Se non si dovesse capire quello che voglio dire (il che è molto probabile) guarda qui: http://it.wikipedia.org/wiki/Combinazio ... i_semplici.
$(a+b)^n=sum_{i=0}^n((n),(i))a^ib^(n-i)$.
Ti sei mai chiesto da dove esce quel coefficiente binomiale? Ti vengo incontro:
$(a+b)^n=(a+b)(a+b)...(a+b)$ n volte. Se sviluppi, ottieni la somma di tutte le possibili combinazioni di prodotti di $a$ e $b$ presi in tutto $n$ volte: cose come $aaba...b, bbab...a$ dove prendi un certo numero, diciamo $i$ di $a$ e moltiplichi $n-i$ fattori $b$. Quindi (prop. commutativa) è una somma di oggetti tipo $a^ib^(n-i)$. Ma non ogni $a^ib^(n-i)$ può essere ottenuto in un solo modo.
Ad esempio, $(a+b)^2=(a+b)(a+b)=a*a+a*b+b*a+b*b=aa+2ab+b b$, perché puoi ottenere il termine misto in 2 modi diversi. E se elevassimo al cubo, avrsti $(a+b)^3=(a+b)(a+b)(a+b)=a^3+3a^2b+3ab^2+b^3$ perché puoi ottenere i termini misti $a^2b, b^2a$ come $aab, aba, baa; b ba, bab, ab b$ ovvero in 3 modi diversi l'uno.
Osservazione importante: in ognuno degli addendi della sommatoria, una volta fissati i posti che dovranno occupare le $a$, i posti restanti vanno riempiti di $b$ e perciò sono già determinati. Quindi ogni $a^ib^(n-i)$ compare nella sommatoria esattamente tante volte quante le possibili combinazioni di i oggetti estratti tra n oggetti.
______________________________________________________________________________________________
Che cosa sto cercando di dire da mezz'ora? Che il teorema di Newton è solo una applicazione di un teorema più importante:
dato un insieme di $n$ oggetti, è possibile sceglierne $i$ (combinare $i$ oggetti scelti tra $n$) esattamente in $((n),(i))$ modi diversi.
Che c'entra questo col tuo problema? Molto, visto che, in sostanza, questo si riduce a contare varie combinazioni di elementi di un insieme finito.
Se non si dovesse capire quello che voglio dire (il che è molto probabile) guarda qui: http://it.wikipedia.org/wiki/Combinazio ... i_semplici.
il numero di combinazioni, che poi non è altro che il coefficiente binomiale (come ti ha ampiamente illustrato dissonance),
$((n),(k))$ ti dice esattamente quanti sono i sottoinsiemi di k elementi di un insieme di n elementi, ed ha come formula $((n),(k))=(n!)/(k!*(n-k)!)$.
nel tuo ultimo esempio, inoltre, secondo me, puoi anche mettere {3,4,5} nello stesso sottoinsieme o separati o in uno degli altri due... in tutti i modi, se non specificato diversamente. ciao.
P.S. secondo me sono 23 (=5+6*3). prova.
$((n),(k))$ ti dice esattamente quanti sono i sottoinsiemi di k elementi di un insieme di n elementi, ed ha come formula $((n),(k))=(n!)/(k!*(n-k)!)$.
nel tuo ultimo esempio, inoltre, secondo me, puoi anche mettere {3,4,5} nello stesso sottoinsieme o separati o in uno degli altri due... in tutti i modi, se non specificato diversamente. ciao.
P.S. secondo me sono 23 (=5+6*3). prova.
Ok, per il coefficiente binomiale ci siamo..
Se nell'esercizio viene detto: "al più tre elementi" vuol dire che possono essercene anche due o uno all'interno. Quindi bisogna fare il calcolo binomiale con 2, vedere quante possibilità ci sono e con i 5 restanti termini vedere quante combinazioni ci sono. E poi idem con tre.. Diventa mostruosa la cosa
Ripetendo l'esercizio di prima:
{1,2,3,4,5,6,7}
Si determini il numero delle relazioni di equivalenza ~ sull'insieme {1,2,3,4,5,6,7} soddisfacenti alle seguenti condizioni: ogni casse d'equivalenza contiente al più tre elementi, 1~2 e 6~7.
Come procediamo? 1~2 e 6~7 sono fissi? allora sarebbe più facile perchè avrei solo 3 elementi da gestire.. {1,2}{3,4,5}{6,7} e abbiamo già visto che i tre elementi hanno 5 combinazioni.. Ma se 1~2 e 6~7 possono anche essere {1,2,3} e {5,6,7} allora diventa impossibile da fare no? perchè devo considerare che 1~2 devono stare sempre nello stesso {a,b} magari con altri elementi ma non possono essere {1,3} essendo 1~2 e 1~2 se [1] = [2] e quindi il calcolo binomiale non c'aiuta visto che prenderebbe in considerazione anche le possibilità che 1~2 non siano assieme..
Se nell'esercizio viene detto: "al più tre elementi" vuol dire che possono essercene anche due o uno all'interno. Quindi bisogna fare il calcolo binomiale con 2, vedere quante possibilità ci sono e con i 5 restanti termini vedere quante combinazioni ci sono. E poi idem con tre.. Diventa mostruosa la cosa
Ripetendo l'esercizio di prima:
{1,2,3,4,5,6,7}
Si determini il numero delle relazioni di equivalenza ~ sull'insieme {1,2,3,4,5,6,7} soddisfacenti alle seguenti condizioni: ogni casse d'equivalenza contiente al più tre elementi, 1~2 e 6~7.
Come procediamo? 1~2 e 6~7 sono fissi? allora sarebbe più facile perchè avrei solo 3 elementi da gestire.. {1,2}{3,4,5}{6,7} e abbiamo già visto che i tre elementi hanno 5 combinazioni.. Ma se 1~2 e 6~7 possono anche essere {1,2,3} e {5,6,7} allora diventa impossibile da fare no? perchè devo considerare che 1~2 devono stare sempre nello stesso {a,b} magari con altri elementi ma non possono essere {1,3} essendo 1~2 e 1~2 se [1] = [2] e quindi il calcolo binomiale non c'aiuta visto che prenderebbe in considerazione anche le possibilità che 1~2 non siano assieme..
1, 2 insieme
6, 7 insieme
non è possibile 1,2,6,7 perché max 3 elementi
3,4,5 liberi (5 casi se non insieme con gli altri 4 elementi)
ma solo uno può essere abbinato ad una delle coppie precedenti
abbiamo tre nuovi casi:
1,2 soli ma 6,7 con un altro elemento (3 sottoinsiemi con 6,7 + due elementi rimasti liberi: 3*2=6 possibilità)
analogamente con 1,2 con un altro elemento ma 6,7 soli: altre 6 possibilità
se 1,2 con un altro elemento ed anche 6,7 con un altro elemento + un elemento da solo: 3*2*1=6 possibilità... [scelgo l'elemento da abbinare ad 1,2 in tre modi, l'elemento da abbinare a 6,7 in due modi, rimane un elemento da lasciare solo]
quindi in tutto 5+6+6+6=23 casi
è chiaro? ciao.
6, 7 insieme
non è possibile 1,2,6,7 perché max 3 elementi
3,4,5 liberi (5 casi se non insieme con gli altri 4 elementi)
ma solo uno può essere abbinato ad una delle coppie precedenti
abbiamo tre nuovi casi:
1,2 soli ma 6,7 con un altro elemento (3 sottoinsiemi con 6,7 + due elementi rimasti liberi: 3*2=6 possibilità)
analogamente con 1,2 con un altro elemento ma 6,7 soli: altre 6 possibilità
se 1,2 con un altro elemento ed anche 6,7 con un altro elemento + un elemento da solo: 3*2*1=6 possibilità... [scelgo l'elemento da abbinare ad 1,2 in tre modi, l'elemento da abbinare a 6,7 in due modi, rimane un elemento da lasciare solo]
quindi in tutto 5+6+6+6=23 casi
è chiaro? ciao.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo