Combinatoria???

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
Iron_Man
Messaggi: 139
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Combinatoria???

Messaggio da Iron_Man » 19 set 2005, 14:43

Siccome ho le idee abbastanza confuse sulla combinatoria non c'è qualcuno (di buona volontà) che impartirebbe una lezioncina partendo proprio dalle basi :roll:
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley

EvaristeG
Site Admin
Messaggi: 4779
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 19 set 2005, 17:46

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.
Ultima modifica di EvaristeG il 21 set 2005, 18:03, modificato 1 volta in totale.

Avatar utente
Iron_Man
Messaggi: 139
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Messaggio da Iron_Man » 21 set 2005, 15:05

Per prima cosa volevo ringraziarti perchè i tuoi consigli hanno chiarito molte cose, anche se spero di riceverne altri :wink:
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

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 21 set 2005, 18:00

La cardinalità di un insieme finito è semplicemente il numero degli elementi.
Se l'insieme si chiama A la sua cardinalità si indica con |A|
Wir müssen wissen. Wir werden wissen.

EvaristeG
Site Admin
Messaggi: 4779
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 21 set 2005, 18:02

Uhm ... a me si legge ... cmq, modifico e spezzo il tex (il più delle volte è la lunghezza delle formule a non farle visualizzare).

Avatar utente
Iron_Man
Messaggi: 139
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Messaggio da Iron_Man » 23 set 2005, 14:50

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 :lol:
$ \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

febiz2004
Messaggi: 80
Iscritto il: 01 gen 1970, 01:00

Messaggio da febiz2004 » 23 set 2005, 19:12

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!} $

EvaristeG
Site Admin
Messaggi: 4779
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 23 set 2005, 20:54

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

Avatar utente
Iron_Man
Messaggi: 139
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Messaggio da Iron_Man » 23 set 2005, 22:04

Eh sì è vero, è solo che vedevo il problema sotto un'altra ottica. Comunque spero di farci presto l'occhio; magari ricevendo ancora qualche consiglio :roll: :roll:
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley

Rispondi