Relazioni d'equivalenza su insieme.

[whiterabbit]

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..

[dissonance]

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.

[whiterabbit]

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?

[dissonance]

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.

[adaBTTLS]

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.

[whiterabbit]

Quindi ci sarebbero 175 possibili combinazioni?

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

[dissonance]

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.

[adaBTTLS]

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.

[whiterabbit]

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..

[adaBTTLS]

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.