Calcolocombinatorio

1、1Una trattazione elementare esposta in modo essenziale e funzionale.Liceo Scientifico Statale G.Sulpicio Veroli (FR) A.S. 2000/2001 N. MonforteNote Bibliografiche a cura di Umberto Tenuta2Diapositiva sommariolDisposizioni semplicilDisposizioni con RipetizionelPermutazioni semplicilPermutazioni con o

2、ggetti identicilCombinazioni SemplicilCombinazioni con Ripetizione3Premessa Calcolo CombinatoriolConsideriamo un insieme di n oggetti: G=a1,a2,a3,an con n0, di natura qualunque ma perfettamente distinguibili luno dallaltro in base a qualche caratteristica, ad esempio palline di diverso colore; lette

3、re dellalfabeto; numeri diversi; ecc. .lIl “calcolo combinatorio” ha per scopo la costruzione e la misurazione del n di raggruppamenti che, secondo unassegnata definizione, si possono formare con una prefissata quantit degli n oggetti di G.Calcolo combinatorio4Disposizioni sempliciFissiamo un numero

4、 k0 che non superi n, si vogliono costruire tutti i possibili raggruppamenti distinti che si ottengono prendendo k oggetti di Gn in modo che valgano le seguenti propriet: in ciascun raggruppamento figurano k oggetti senza ripetizioni; due qualsiasi raggruppamenti sono distinti se e solo se o uno di

5、essi contiene almeno un oggetto che non figura nellaltro oppure gli oggetti di un raggruppamento sono gli stessi dellaltro raggruppamento ma diverso lordine con cui essi sono disposti. I predetti raggruppamenti si dicono disposizioni semplici di n oggetti distinti di classe k o presi a k a k. Tale n

6、umero si indica con il simbolo Dn,k e si dimostra che Dn,k=n(n-1)(n-2).(n-k+1)=)!(!knn Ad esempio si ha: D7,4=7654=840 D9,3=987=504 Calcolo combinatorioOsservazioni5In generale Dn,k uguale al prodotto di k numeri naturali, consecutivi, decrescenti a partire da n. Consideriamo per fissare le idee, li

7、nsieme G4=1,2,3,4, costruiamo le disposizioni semplici degli n=4 oggetti a k=1 a k=1; si hanno i raggruppamenti seguenti: e pertanto D4,1= 4 costruiamo le disposizioni semplici degli n=4 oggetti a k=2 a k=2; si hanno i raggruppamenti seguenti: sicch resta verificato che D4,2 = 12. per costruire le d

8、isposizioni semplici degli n=4 oggetti a k=3 a k=3 occorre aggregare ai precedenti raggruppamenti via via uno degli altri due oggetti che ancora non vi figurano:, tenendo conto delle regole di composizione dei raggruppamenti per le disposizioni semplici si ha: D4,3=432=24 generalizzando si comprende

9、 la validit della formula per il calcolo delle disposizioni semplici. 1 2 3 4 1 2 2 1 3 1 4 1 1 3 2 3 3 2 4 2 1 4 2 4 3 4 4 3 1 2 3 2 1 3 3 1 2 1 2 4 2 1 4 3 1 4 Osservazioni sulle Disposizioni Semplici6Calcolo combinatorioFissiamo un numero k0, senza alcuna limitazione superiore; si vogliono costru

10、ire tutti i possibili raggruppamenti distinti, prendendo k oggetti di Gn , in modo che valgano le seguenti propriet: in ciascun raggruppamento figurano k oggetti, potendovi uno stesso oggetto figurare, ripetuto, sino ad un massimo di k volte; due qualsiasi raggruppamenti sono distinti se e solo se o

11、 uno di essi contiene almeno un oggetto che non figura nellaltro, oppure gli oggetti sono diversamente ordinati oppure gli oggetti che figurano in uno figurano anche nellaltro ma sono ripetuti un numero diverso di volte. I predetti raggruppamenti si dicono disposizioni con ripetizione degli n oggett

12、i di Gn, a k a k ( o di classe k). Il n delle predette disposizioni con ripetizione degli n oggetti di Gn, a k a k si indica con Dn,k=nk Disposizioni con RipetizioneOsservazioni7Osservazioni sulle Disposizioni con RipetizionePer fissare le idee consideriamo linsieme G4=1,2,3,4 le disposizioni con ri

13、petizione degli n=4 oggetti a k=1 a k=1 sono: pertanto D4,1=4 le disposizioni con ripetizione degli n=4 oggetti a k=2 a k=2 si ottengono dalle (1) aggregando via via ciascuno degli oggetti di G4, anche se gi contenuti nel raggruppamento; esse sono: Possiamo osservare che per ogni disposizione con ri

14、petizione di classe uno se ne ottengono n=4 di classe 2 e pertanto D4,1=42=16 1 2 3 4 (1) 1 1 2 1 3 1 4 1 1 2 2 2 3 2 4 2 1 3 2 3 3 3 4 3 1 4 2 4 3 4 4 4 8Applicazioni - 1Calcolo combinatorioQuante parole anche prive di significato, si possono costruire con 3 lettere dellalfabeto, tutte diverse tra

15、loro?disp. Semplici n=21, k=3 R.7980In quanti modi diversi 7 persone si possono sedere su 5 poltrone allineate di un cinema? D(7,5)Quanti numeri di tre cifre, anche uguali tra loro, si possono costruire con i primi cinque numeri naturali? D(5,3)Quante colonne d diverse si possono compilare nel gioco

16、 del totocalcio? D(3,13)9Permutazioni sempliciCalcolo combinatorioLe permutazioni semplici degli oggetti di Gn sono le disposizioni semplici dei predetti n oggetti a k=n a k=n. Si deduce che due qualsiasi permutazioni semplici differiscono solo per lordine con cui sono disposti gli n oggetti distint

17、i in esse contenuti. Il loro n Dn,n ma si preferisce usare il simbolo Pn Evidentemente si ha: Pn=n(n-1)(n-2)(n-3) 321=n! “enne fattoriale”. Ad esempio, costruiamo e contiamo tutti gli anagrammi, anche privi di significato, che si possono formare con la parola “APE”. APE PAE EAP AEP PEA EPA, sono sei

18、, difatti P3=3!=321=6 10Ci proponiamo di anagrammare una parola contenente alcune lettere uguali; se prendiamo in esame la parola “ALA”, notiamo che i suoi possibili anagrammi distinti sono: ALA LAA AAL cio soltanto tre e non sei come accade se le lettere sono tutte diverse. In generale, volendo per

19、mutare n oggetti in cui ve ne siano identici tra loro, si ottiene un numero di permutazioni dato da: !)(nPPnn Nellesempio precedente avevamo n=3 ed =2 sicch gli anagrammi distinti risultavano: 312123! 2! 3)2(3P Permutazioni con oggetti identiciCalcolo combinatorio11Applicazioni - 2Calcolo combinator

20、ioEsempio: il numero di anagrammi distinti che si possono costruire con la parola “MATEMATICA” dato da: 15120! 2! 2! 3!10)2,2, 3(10Ppoich il n di lettere da permutare n=10 tra le quali la lettera “A” figura 3 volte, la lettera “M” 2 volte come la lettera “T”. Esercizio 1: Un negoziante deve eseguire

21、 5 consegne di merce acquistata da clienti abitanti ciascuno in 5 zone diverse della citt. determinare il n di modi differenti di eseguire le consegne. R. 160 Esercizio 2: Quanti numeri naturali diversi di 6 cifre si possono formare con le cifre del numero 775551. R. 60 12Combinazioni SempliciCalcol

22、o combinatorioFissiamo un numero k0, che non superi n; si vogliono costruire tutti i possibili raggruppamenti distinti che si ottengono prendendo k oggetti di Gn in modo che valgano le seguenti propriet: in ciascun raggruppamento figurano k oggetti senza ripetizioni; due raggruppamenti sono distinti

23、 se e solo se uno di essi contiene almeno un oggetto che non figura nellaltro. Segue, pertanto, che due raggruppamenti che differiscono solo per lordine con cui in essi sono disposti gli oggetti sono da ritenersi identici. I predetti raggruppamenti si dicono “Combinazioni semplici” degli n oggetti d

24、i Gn di classe k od a k a k. Il numero delle predette combinazioni semplici di n oggetti distinti di classe k si indica con il simbolo di Cn,k Si dimostra che : !,kDCknkn Questa formula giustificata dal fatto che da ogni combinazione semplice si possono ottenere, permutando in tutti i modi possibili

25、 i k oggetti che la compongono, k! disposizioni semplici. Osservazioni13Osservazioni sulle Combinazioni Semplici 1/3Consideriamo ad esempio linsieme G4=1,2,3,4,5 le combinazioni semplici degli n=4 oggetti di classe k=1 sono: 1 2 3 4 le combinazioni semplici degli n=4 oggetti di classe k=2 si ottengo

26、no dalle precedenti aggregaziondo, via via, solo quegli elementi che, in G4 seguono loggetto gi presente nel raggruppamento, ossia: 1 2 2 3 3 4 1 3 2 4 1 4 le combinazioni semplici degli n=4 oggetti di classe k=3 si ottengono da quelle di classe 2 aggregando, via via, solo quegli elementi che in G4,

27、 seguono loggetto che figura pi a destra del raggruppamento, ossia: 1 2 3 2 3 4 1 2 4 1 3 4 14Osservazioni sulle Combinazioni Semplici 2/3Nota: il numero Cn,k si india anche con kn che si legge “n su k”, denominato “coefficiente binomiale” di ordine n e di classe k. E abbastanza facile, posto per de

28、finizione 10n, dimostrare la validit delle seguenti formule: )!(!,knknCkn ; knnkn; knknkn111 Pu essere utile ricordare la “formula del binomio di Newton”: kknnknbaknba0)( 15Osservazioni sulle Combinazioni Semplici 3/3Sussistono le seguenti propriet: 1. 10n 2. 1nn 3. nn1 4. nnn1 5. knnkn 6. 0,!) 1()

29、1(kkknnnkn 7. nknknknnn, 1,11 16Combinazioni con RipetizioneFissiamo un numero k0, senza alcuna limitazione superiore; si vogliono costruire tutti i possibili raggruppamenti distinti, prendendo k oggetti di Gn, in modo che valgano le seguenti propriet: in ciascun raggruppamento figurano k oggetti di

30、 Gn, potendovi uno stesso elemento figurare ripetuto fino ad un massimo di k volte; due raggruppamenti sono distinti se e solo se o uno di essi contiene almeno un oggetto che non figura nellaltro oppure gli oggetti che figurano in uno figurano anche nellaltro ma sono ripetuti un numero diverso di volte. I predetti raggruppamenti si dicono “combinazioni con ripetizione degli n oggetti di Gn, a k a k” o di classe k. Il loro numero si indica con il simbolo Cn,k. Si dimostra che: kknCkn1, Calcolo combinatorio17Applicazioni - 3Calcolo com