Combinatoria???
Combinatoria???
Siccome ho le idee abbastanza confuse sulla combinatoria non c'è qualcuno (di buona volontà) che impartirebbe una lezioncina partendo proprio dalle basi
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley
Aldous Huxley
Più d'uno probabilmente riderà quando vedrà che ho risposto io, ma c'è sempre una prima volta, anche con la combinatoria.
Innanzitutto ti avviso che la combinatoria non ha una vera e propria teoria ... ci sono alcuni fatti che è bene sapere, due o tre argomenti (permutazioni, grafi, probabilità) che possono essere trattati in maniera teorica e sui quali si possono dimostrare teoremi e dare risultati generali, ma la maggior parte dei problemi di combinatoria si fa (almeno così penso) grazie al ragionamento (cosa che mi fa sentire un idiota ogni volta che non riesco a risolvere un problema di combinatoria) e ad alcune tecniche "standard" che si possono applicare in tanti problemi.
Detto ciò ... un problema tipico della combinatoria è il conteggio. Provo ad elencarti alcuni conteggi classici :
Permutazioni
Se hai n oggetti distinti da ordinare, hai $ n! $ ordinamenti possibili, ovvero permutazioni degli n oggetti.
Anagrammi
Date n lettere tutte distinte, ovviamente vi sono $ n! $ anagrammi possibili. Se c'è una lettera doppia, gli anagrammi che si ottengono l'uno dall'altro semplicemente scambiando di posto le lettere uguali sono indistinguibili, quindi abbiamo $ n!/2 $ anagrammi. Se c'è una lettere ripetuta m volte, tutti gli anagrammi ottenuti permutando tra di loro queste m lettere uguali saranno indistinguibili, quindi abbiamo $ n!/m! $ anagrammi.
In generale, date n lettere, di cui k compaiono più di una volta e precisamente la prima compare $ m_1 $ volte, la seconda $ m_2 $ ... la k-esima $ m_k $ volte, potremo ottenere $ \displaystyle{\frac{n!}{m_1!m_2!\ldots m_k!}} $ anagrammi distinti.
Disposizioni
Dobbiamo scegliere k oggetti tra n, ordinatamente (ad esempio, abbiamo n ragazzi ad una corsa e ci chiediamo in quanti modi è possibile formare il podio, ovvero scegliere primo, secondo e terzo); lo possiamo fare in $ \displaystyle{\frac{n!}{(n-k)!}} $
Disposizioni con ripetizione
Dati n simboli, quante stringhe di lunghezza k possiamo formare con essi, potendo ripetere nella stringa ogni simbolo anche per k volte ? Possiamo fare $ n^k $ stringhe.
Combinazioni
Dati n oggetti, in quanti modi ne possiamo scegliere k, a prescindere dall'ordine in cui li scegliamo? Se consideriamo l'ordine, possiamo farlo in $ \frac{n!}{(n-k)!} $; ora, k oggetti possono essere ordinati in $ k! $ modi e noi vogliamo identificare tutti questi diversi ordinamenti, contandoli come una sola scelta, quindi, senza curarsi del loro ordine, possiamo scegliere k oggetti tra n in $ \displaystyle{\frac{n!}{k!(n-k)!}} $. Questo numero si indica con $ {n\choose k} $ e si chiama coefficiente binomiale. Osserviamo che scegliere i k oggetti da prendere o gli n-k oggetti da non prendere sono la stessa cosa e quindi $ {n\choose k}={n\choose n-k} $
Divagazione sui coefficienti binomiali
Esempio tipico di utilizzo dei coefficienti binomiali è lo sviluppo del binomio :
$ \displaystyle{(a+b)^n=\sum_{k=0}^n c_{k,n}a^kb^{n-k}} $
Come sono fatti i coefficienti $ c_{k,n} $?
Beh, vediamo, per fare (a+b)^n, noi facciamo (a+b)(a+b)...(a+b) n volte; questo prodotto a sua volta lo eseguiamo scegliendo da ogni parentesi la a o la b e moltiplicando; in quanti modi possiamo ottenere il termine $ a^kb^{n-k} $ ? Dobbiamo scegliere da k parentesi la a, quindi dobbiamo scegliere, nell'insieme delle n parentesi, un sottoinsieme di k parentesi da cui scegliere la a, mentre dalle altre n-k sceglieremo la b. In quanti modi possiamo scegliere k oggetti tra n, senza curarci dell'ordine (infatti la moltiplicazione è commutativa)? In $ {n\choose k} $ modi e dunque $ c_{k,n}={n\choose k} $.
Ovvero, $ (a+b)^n=\sum_{k=0}^n {n\choose k}a^kb^{n-k} $.
Da questo è facile ricavare (provaci) alcune identità utili, come
$ \displaystyle{\sum_{k=0}^n {n\choose k}=2^n\quad \sum_{k=0}^n(-1)^k {n\choose k}=0} $
Penso che saprai cos'è il triangolo di Tartaglia o di Pascal e che quindi avrai notato che i coeff binomiali sono proprio i numeri che vi compaiono. Questo significa che per i coefficienti binomiali vale la relazione $ {n \choose k}={n-1\choose k-1}+{n-1\choose k} $ con la convenzione che $ {n\choose k}=0 $ se k>n o k<0.
Questa relazione (che si può dimostrare facendo i conti con i fattoriali) ha anche un'affascinante interpretazione combinatorica :
vogliamo contare i modi di scegliere k oggetti tra n, a meno dell'ordine e lo facciamo come segue; scegliamo un oggetto particolare X e dividiamo in due tipi i sottoinsiemi di k elementi, a seconda che non contengano o che contengano X. Quanti sono quelli che lo contengono? Essi sono fatti da X e da k-1 elementi scelti tra gli altri n-1 e, per ogni scelta di k-1 tra gli n-1 (gli n a cui togliamo X), aggiungendo a questi X abbiamo appunto un sottoinsieme di k el. contenente X. Quindi il numero di questi sottoinsiemi equivale ai modi di scegliere k-1 elementi in un insieme di n-1, ovvero $ {n-1\choose k-1} $.
Ora invece, gli insiemi che non contengono X sono fatti scegliendo k elementi tra gli n-1 restanti e sono tutti e soli i sottoinsiemi fatti così, quindi sono $ {n-1\choose k} $.
Ma allora il numero totale di scelte di k elementi tra n è $ {n-1\choose k-1}+{n-1\choose k} $ e la nostra relazione è dimostrata.
Double counting
Questa è una delle tecniche più importanti dei conteggi in combinatoria... non è un teorema o una formula, ma un modo di procedere : devi trovare un parametro in base al quale definisci una certa proprietà e conti quanti sono gli oggetti con quella proprietà in due o più modi, che ovviamente dovranno dare tutti lo stesso risultato; uguagliando i risultati, ottieni di solito un'equazione che ti da il valore del parametro che cercavi.
Ad esempio : siamo ad una festa e ovviamente vi sono tante strette di mano (non necessariamente ognuno stringe la mano a tutti gli altri, solo ad alcuni o anche a nessuno); dimostra che le persone che hanno fatto un numero dispari di strette di mano sono in numero pari.
Ora, contiamo le mani in due modi :
1) se vi sono state q strette di mano, sono state strette 2q mani ( una stretta di mani ne prevede due ...)
2) se abbiamo n persone, numerate da 1 a n, sia $ k_i $ il numero di persone a cui la persona i-esima ha stretto la mano, allora egli avrà partecipato al numero totale di mani con esattamente $ k_i $; dunque il numero totale di mani è anche $ \sum k_i $
Ora, $ \sum k_i=2q $, ma quindi tra gli addendi $ k_i $ i dispari devono essere in numero pari, altrimenti anche la somma è dispari; quindi le persone che hanno fatto un num dispari di strette di mano sono in numero pari.
Vi sono moltissimi altri esempi, ma io non sono tanto pratico di queste cose.
Principio di Inclusione-Esclusione
Dati due insiemi A,B si ha
$ |A\cup B|=|A|+|B|-|A\cap B| $
dove |X| è la cardinalità di X. Con tre insiemi A,B,C si avrà
$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|- $$ |A\cap C|-|C\cap B|+|A\cap B\cap C| $
Per n è brutta da scrivere ma il ragionamento è sempre quello : si sommano le cardinalità degli insiemi, si tolgono quelle delle intersezioni a due a due, si aggiungono quelle delle int. a 3 a 3, si tolgono quelle delle int. a 4 a 4 e così via a segni alterni.
Classico esempio : in una classe di 30 ragazzi ognuno fa almeno uno sport e in particolare 17 giocano a calcio, 18 giocano a pallavolo, 12 giocano a basket, 5 fanno tutti e tre gli sport. Quanti sono i ragazzi che fanno almeno 2 sport?
Beh, applichiamo l'I-E : 30=17+18+12-a-b-c+5 ... a noi interessa a+b+c, che è
a+b+c=17+18+12+5-30=22
Oppure : Quanti sono i numeri naturali positivi minori stretti di 2005 multipli di 5 o di 3 o di entrambi?
I multipli di 5 minori di 2005 sono 2005/5-1=400; i multipli di 3 minori di 2005 sono [2005/3]=668; i multipli di 3 e di 5 (ovvero di 15) minori di 2005 sono [2005/15]=[401/3]=133. Quindi vi sono 400+668-133=935 numeri come richiesto.
Altri conteggi non me ne vengono in mente...non so se questo era parte di quel che volevi ... se mai avrò tempo (e molta voglia) posterò altra roba, su qualcosa d'altro come probabilità, permutazioni, grafi o invarianti, per quanto di queste robette io non ne sappia tantissimo.
Ora spero di non aver scritto stronzate e che qualche combinatorico serio risponda per bene sugli altri argomenti.
Innanzitutto ti avviso che la combinatoria non ha una vera e propria teoria ... ci sono alcuni fatti che è bene sapere, due o tre argomenti (permutazioni, grafi, probabilità) che possono essere trattati in maniera teorica e sui quali si possono dimostrare teoremi e dare risultati generali, ma la maggior parte dei problemi di combinatoria si fa (almeno così penso) grazie al ragionamento (cosa che mi fa sentire un idiota ogni volta che non riesco a risolvere un problema di combinatoria) e ad alcune tecniche "standard" che si possono applicare in tanti problemi.
Detto ciò ... un problema tipico della combinatoria è il conteggio. Provo ad elencarti alcuni conteggi classici :
Permutazioni
Se hai n oggetti distinti da ordinare, hai $ n! $ ordinamenti possibili, ovvero permutazioni degli n oggetti.
Anagrammi
Date n lettere tutte distinte, ovviamente vi sono $ n! $ anagrammi possibili. Se c'è una lettera doppia, gli anagrammi che si ottengono l'uno dall'altro semplicemente scambiando di posto le lettere uguali sono indistinguibili, quindi abbiamo $ n!/2 $ anagrammi. Se c'è una lettere ripetuta m volte, tutti gli anagrammi ottenuti permutando tra di loro queste m lettere uguali saranno indistinguibili, quindi abbiamo $ n!/m! $ anagrammi.
In generale, date n lettere, di cui k compaiono più di una volta e precisamente la prima compare $ m_1 $ volte, la seconda $ m_2 $ ... la k-esima $ m_k $ volte, potremo ottenere $ \displaystyle{\frac{n!}{m_1!m_2!\ldots m_k!}} $ anagrammi distinti.
Disposizioni
Dobbiamo scegliere k oggetti tra n, ordinatamente (ad esempio, abbiamo n ragazzi ad una corsa e ci chiediamo in quanti modi è possibile formare il podio, ovvero scegliere primo, secondo e terzo); lo possiamo fare in $ \displaystyle{\frac{n!}{(n-k)!}} $
Disposizioni con ripetizione
Dati n simboli, quante stringhe di lunghezza k possiamo formare con essi, potendo ripetere nella stringa ogni simbolo anche per k volte ? Possiamo fare $ n^k $ stringhe.
Combinazioni
Dati n oggetti, in quanti modi ne possiamo scegliere k, a prescindere dall'ordine in cui li scegliamo? Se consideriamo l'ordine, possiamo farlo in $ \frac{n!}{(n-k)!} $; ora, k oggetti possono essere ordinati in $ k! $ modi e noi vogliamo identificare tutti questi diversi ordinamenti, contandoli come una sola scelta, quindi, senza curarsi del loro ordine, possiamo scegliere k oggetti tra n in $ \displaystyle{\frac{n!}{k!(n-k)!}} $. Questo numero si indica con $ {n\choose k} $ e si chiama coefficiente binomiale. Osserviamo che scegliere i k oggetti da prendere o gli n-k oggetti da non prendere sono la stessa cosa e quindi $ {n\choose k}={n\choose n-k} $
Divagazione sui coefficienti binomiali
Esempio tipico di utilizzo dei coefficienti binomiali è lo sviluppo del binomio :
$ \displaystyle{(a+b)^n=\sum_{k=0}^n c_{k,n}a^kb^{n-k}} $
Come sono fatti i coefficienti $ c_{k,n} $?
Beh, vediamo, per fare (a+b)^n, noi facciamo (a+b)(a+b)...(a+b) n volte; questo prodotto a sua volta lo eseguiamo scegliendo da ogni parentesi la a o la b e moltiplicando; in quanti modi possiamo ottenere il termine $ a^kb^{n-k} $ ? Dobbiamo scegliere da k parentesi la a, quindi dobbiamo scegliere, nell'insieme delle n parentesi, un sottoinsieme di k parentesi da cui scegliere la a, mentre dalle altre n-k sceglieremo la b. In quanti modi possiamo scegliere k oggetti tra n, senza curarci dell'ordine (infatti la moltiplicazione è commutativa)? In $ {n\choose k} $ modi e dunque $ c_{k,n}={n\choose k} $.
Ovvero, $ (a+b)^n=\sum_{k=0}^n {n\choose k}a^kb^{n-k} $.
Da questo è facile ricavare (provaci) alcune identità utili, come
$ \displaystyle{\sum_{k=0}^n {n\choose k}=2^n\quad \sum_{k=0}^n(-1)^k {n\choose k}=0} $
Penso che saprai cos'è il triangolo di Tartaglia o di Pascal e che quindi avrai notato che i coeff binomiali sono proprio i numeri che vi compaiono. Questo significa che per i coefficienti binomiali vale la relazione $ {n \choose k}={n-1\choose k-1}+{n-1\choose k} $ con la convenzione che $ {n\choose k}=0 $ se k>n o k<0.
Questa relazione (che si può dimostrare facendo i conti con i fattoriali) ha anche un'affascinante interpretazione combinatorica :
vogliamo contare i modi di scegliere k oggetti tra n, a meno dell'ordine e lo facciamo come segue; scegliamo un oggetto particolare X e dividiamo in due tipi i sottoinsiemi di k elementi, a seconda che non contengano o che contengano X. Quanti sono quelli che lo contengono? Essi sono fatti da X e da k-1 elementi scelti tra gli altri n-1 e, per ogni scelta di k-1 tra gli n-1 (gli n a cui togliamo X), aggiungendo a questi X abbiamo appunto un sottoinsieme di k el. contenente X. Quindi il numero di questi sottoinsiemi equivale ai modi di scegliere k-1 elementi in un insieme di n-1, ovvero $ {n-1\choose k-1} $.
Ora invece, gli insiemi che non contengono X sono fatti scegliendo k elementi tra gli n-1 restanti e sono tutti e soli i sottoinsiemi fatti così, quindi sono $ {n-1\choose k} $.
Ma allora il numero totale di scelte di k elementi tra n è $ {n-1\choose k-1}+{n-1\choose k} $ e la nostra relazione è dimostrata.
Double counting
Questa è una delle tecniche più importanti dei conteggi in combinatoria... non è un teorema o una formula, ma un modo di procedere : devi trovare un parametro in base al quale definisci una certa proprietà e conti quanti sono gli oggetti con quella proprietà in due o più modi, che ovviamente dovranno dare tutti lo stesso risultato; uguagliando i risultati, ottieni di solito un'equazione che ti da il valore del parametro che cercavi.
Ad esempio : siamo ad una festa e ovviamente vi sono tante strette di mano (non necessariamente ognuno stringe la mano a tutti gli altri, solo ad alcuni o anche a nessuno); dimostra che le persone che hanno fatto un numero dispari di strette di mano sono in numero pari.
Ora, contiamo le mani in due modi :
1) se vi sono state q strette di mano, sono state strette 2q mani ( una stretta di mani ne prevede due ...)
2) se abbiamo n persone, numerate da 1 a n, sia $ k_i $ il numero di persone a cui la persona i-esima ha stretto la mano, allora egli avrà partecipato al numero totale di mani con esattamente $ k_i $; dunque il numero totale di mani è anche $ \sum k_i $
Ora, $ \sum k_i=2q $, ma quindi tra gli addendi $ k_i $ i dispari devono essere in numero pari, altrimenti anche la somma è dispari; quindi le persone che hanno fatto un num dispari di strette di mano sono in numero pari.
Vi sono moltissimi altri esempi, ma io non sono tanto pratico di queste cose.
Principio di Inclusione-Esclusione
Dati due insiemi A,B si ha
$ |A\cup B|=|A|+|B|-|A\cap B| $
dove |X| è la cardinalità di X. Con tre insiemi A,B,C si avrà
$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|- $$ |A\cap C|-|C\cap B|+|A\cap B\cap C| $
Per n è brutta da scrivere ma il ragionamento è sempre quello : si sommano le cardinalità degli insiemi, si tolgono quelle delle intersezioni a due a due, si aggiungono quelle delle int. a 3 a 3, si tolgono quelle delle int. a 4 a 4 e così via a segni alterni.
Classico esempio : in una classe di 30 ragazzi ognuno fa almeno uno sport e in particolare 17 giocano a calcio, 18 giocano a pallavolo, 12 giocano a basket, 5 fanno tutti e tre gli sport. Quanti sono i ragazzi che fanno almeno 2 sport?
Beh, applichiamo l'I-E : 30=17+18+12-a-b-c+5 ... a noi interessa a+b+c, che è
a+b+c=17+18+12+5-30=22
Oppure : Quanti sono i numeri naturali positivi minori stretti di 2005 multipli di 5 o di 3 o di entrambi?
I multipli di 5 minori di 2005 sono 2005/5-1=400; i multipli di 3 minori di 2005 sono [2005/3]=668; i multipli di 3 e di 5 (ovvero di 15) minori di 2005 sono [2005/15]=[401/3]=133. Quindi vi sono 400+668-133=935 numeri come richiesto.
Altri conteggi non me ne vengono in mente...non so se questo era parte di quel che volevi ... se mai avrò tempo (e molta voglia) posterò altra roba, su qualcosa d'altro come probabilità, permutazioni, grafi o invarianti, per quanto di queste robette io non ne sappia tantissimo.
Ora spero di non aver scritto stronzate e che qualche combinatorico serio risponda per bene sugli altri argomenti.
Ultima modifica di EvaristeG il 21 set 2005, 18:03, modificato 1 volta in totale.
Per prima cosa volevo ringraziarti perchè i tuoi consigli hanno chiarito molte cose, anche se spero di riceverne altri 
Poi volevo chiederti come mai non si legge quella formula e che cos'è la cardinalità
Poi volevo chiederti come mai non si legge quella formula e che cos'è la cardinalità
EvaristeG ha scritto: Principio di Inclusione-Esclusione
Dati due insiemi A,B si ha
$ |A\cup B|=|A|+|B|-|A\cap B| $
dove |X| è la cardinalità di X. Con tre insiemi A,B,C si avrà
$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|C\cap B|+|A\cap B\cap C| $
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley
Aldous Huxley
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
Grazie, fin qua ci sono. Ora però avrei una domandina:
ho n palline di k colori diversi come se indico con $ p_1 $ il numero di palline del primo colore, $ p_2 $ quelle del secondo colore e così via fino$ p_k $ il numero di palline del k-esimo colore e naturalmente $ p_1+p_2+p_3+...+p_k=n $ (non sono sicuro ma penso si possa scrivere anche così, intanto imparo un po' ad usare latex
$ \displaystyle \sum_{i=1}^{k}{p_i}=n $).
Quanti possibili modi ho disporre le palline?
ho n palline di k colori diversi come se indico con $ p_1 $ il numero di palline del primo colore, $ p_2 $ quelle del secondo colore e così via fino$ p_k $ il numero di palline del k-esimo colore e naturalmente $ p_1+p_2+p_3+...+p_k=n $ (non sono sicuro ma penso si possa scrivere anche così, intanto imparo un po' ad usare latex
$ \displaystyle \sum_{i=1}^{k}{p_i}=n $).
Quanti possibili modi ho disporre le palline?
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley
Aldous Huxley
Hai $ p_1! $ modi di disporre le $ p_1 $ palline, hai $ p_2! $ modi di disporre le $ p_2 $ palline etc... quindi se il modo di permutare $ n $ oggetti è $ n! $ noi dobbiamo togliergli il modo di permutare le $ p_1,p_2,\ldots,p_k $ palline e ciò si fa attraverso le cosiddette permutazioni con ripetizioni che in formule viene tradotto come $ \displaystyle\frac{n!}{p_1!\cdot p_2! \cdots p_k!} $
Una delle cose "odiose" dei problemi di combinatoria è il fatto che si deve riuscire a leggere il problema attraverso l'ambientazione che l'autore del problema ha dato.
La situazione che hai descritto tu è la stessa che ho posto io nel calcolar in quanti modi si può anagrammare una parola in cui ci sono una lettera che si ripete $ p_1 $ volte, una che si ripete $ p_2 $ etc etc. Quindi la formula, come ha detto bene febiz, è la stessa che io ho scritto sopra alla voce "Anagrammi".
La situazione che hai descritto tu è la stessa che ho posto io nel calcolar in quanti modi si può anagrammare una parola in cui ci sono una lettera che si ripete $ p_1 $ volte, una che si ripete $ p_2 $ etc etc. Quindi la formula, come ha detto bene febiz, è la stessa che io ho scritto sopra alla voce "Anagrammi".