Calcolo combinatorio

Materie:	Appunti
Categoria:	Matematica
Download:	342
Data:	07.03.2001
Numero di pagine:	5
Formato di file:	.doc (Microsoft Word)

“Calcolo combinatorio”
Prerequisiti: Per affrontare gli argomenti del calcolo combinatorio non sono necessari particolari prerequisiti , è, infatti , sufficiente conoscere i caratteri base della teoria degli insiemi e i concetti di logica matematica.
Definizione: Il calcolo combinatorio ha per scopo lo studio dei raggruppamenti che si possono ottenere con un determinato numero di oggetti, che si dicono anche elementi. Questi n elementi vengono designati semplicemente con i numeri naturali 1, 2, 3, …,n; oppure con un lettera contrassegnata da questi numeri come, ad esempio, a1, a2, …, an.
Applicazione: Grazie al calcolo combinatorio si possono calcolare il numero di un qualsiasi raggruppamento, di un sequenza, gli anagrammi di una parola ed ecc.. Facendo una piccola uguaglianza si avrà la percentuale che quel evento accada e quindi si avrà la sua probabilità.
Disposizione semplice di n oggetti
Definizione: Dati n elementi, si chiama “disposizione semplice” degli n elementi, presi a k a k, dove k e n, un gruppo ordinato di k degli n elementi dati.
Il numero delle disposizioni semplici di n elementi a k a k si indica con Dn,k, che si legge “numero delle disposizioni semplici di n elementi presi a k a k.”
Teorema: Il numero delle disposizioni semplici di n elementi (distinti), della classe k, è uguale al prodotto di k numeri interi, consecutivi decrescenti, dei quali il primo è n, cioè:
Dn,k = n = (n-1) (n-2) (n-3) …… (n-k+1)
Studio: Le disposizioni di 4 oggetti presi a 2 a 2 è
D4,2 = 4 = (4-1) = 4 3 = 12
E più precisamente: 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43
Se presi a 3 a 3.
D4,3 = 4 = (4-1) (4-2) = 4 3 2 = 24
Applicazioni: Quante sono le targhe che si possono ottenere con 2 coppie, distinte, di lettere delll’alfabeto italiano e 3 cifre anch’esse distinte?
Es: AG 527 FH o BC 931 CZ.
La parte letterale sono 2 disposizioni di 21 lettere prese a 2 a 2, ossia:
D21,2 = 21 = (21-1) = 21 20 = 420
La parte numerica delle 10 cifre, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, è una disposizione di 10 numeri a 3 a 3, ossia:
D10,3 = 10 = (10-1) (10-2) = 10 9 8 = 720
Il totale delle targhe sarà dato:
D21,2 2D10,3 1D21,2 =420= 720 420 = 127.008.000 targhe

In una classe di 12 alunni, quante coppie di alunni si possono formare in determinato banco?
D12,2 = 12 =11 = 132 coppie
Quant’è la percentuale che l’alunno Simone abbia alla sua destra il suo amico Federico nel determinato banco?
132 : 1 = 100 : X
X% = = 0,76%

Ci sono 0,76 possibilità, su 100, che Federico sia seduto alla destra di Simone.

Si veda l’appendice a pagina 6. Figura N 1

Disposizione con ripetizione

Definizione: Dati n elementi distinti, si dice “disposizione con ripetizione” degli n elementi a k a k, un gruppo ordinato formato con k degli n elementi, potendo uno stesso elemento figurare nel gruppo fino a k volte.
Teorema: Il numero delle disposizione con ripetizione di n elementi distinti della classe k è uguale alla potenza di base n ed esponente k, cioè:
Dr n,k = n k
Studio: Mettiamo di avere 2 interruttori collegati a 2 ingressi di una porta logica.
In quanti modi questi due interruttori si possono combinare?
Dr 2,2 = 2 2 = 4 combinazioni
Più precisamente, considerando 1 ON e 0 OFF, si avrà:
00; 01; 10; 11.

se gli interruttori fossero tre, sempre collegati alla stessa porta logica, si avrebbe:
Dr 2,3 = 2 3 = 8 combinazioni
Più precisamente: 000; 001; 010; 011; 100; 101; 110; 111.

Applicazione: Quante sono le colonne diverse che si possono ottenere nel gioco del totocalcio?
Si tratta di disporre tre simboli 1, X e 2, in una colonna su 13 caselle, quindi il numero delle colonne sarà una disposizione di 3 elementi distinti a 13 a 13.
Es. 1X22XX12X11X2 o X2XX1112X112X..
Dr 3,13 = 3 13 = 1594323 colonne
In quanti modi si possono accoppiare le facce di 2 dadi contrassegnati con i numeri da 1 a 6? (Problema risolto per la prima volta nel 1523 da N. TARTAGLIA.)
Il numero sarà una disposizione di 6 elementi distinti a due a due.
Dr 6,2 = 62 = 36 coppie
Quant’è la percentuale di poter ottenere con un lancio una coppia di 2 numeri dispari? Es. 5 e 5 o 3 e 3.
36 : 3 = 100 : X
X% = = 8,3%
Ci sono 8,3 possibilità, su 100, che con un lancio di due dadi esca una coppia di due numeri dispari.
Si veda l’appendice a pagina 6. Figura N 2
Permutazioni semplici
Definizione: Si chiama “permutazione semplici” di n elementi distinti le disposizione semplici degli n elementi presi ad n a n. Ponendo k=n. Le permutazioni di n elementi distinti sono tutti i gruppi di n elementi che si possono formare con gli elementi dati e che differiscono tra loro soltanto per l’ordine degli elementi.
Teorema: Il numero delle permutazioni semplici di n elementi distinti è uguale al prodotto di n numeri interi, consecutivi, decrescenti fino a n-(n-1) volte, dei quali il primo è n.
Pn= n! = n ∙ (n-1) ∙ (n-2) ∙ (n-3) ∙ …… ∙ [ n-(n-1) ]
Studio: La permutazione più semplice è un anagramma di una parola con tutte le lettere diverse. Quante sono gli anagrammi della parola APE?
Sarà una disposizione di 3 lettere prese a 3 a 3 ossia:
P3= 3! = 3 ∙2 ∙1 = 6 anagrammi
Più precisamente APE, AEP, PAE, PEA, EAP e EPA.
Se la parola fosse ROMA si avrebbe:
P4= 4! = 4 ∙ 3 ∙ 2 ∙ 1 = 24 anagrammi
Applicazioni: Quanti numeri di tre cifre, tra loro diversi, si possono formare con le cifre 3, 5 e 1? Es: 135 o 153
P3 = 3! = 3 ∙ 2 ∙ 1 = 6 combinazioni.
In quanti modi 7 persone si possono disporre in 7 sedie allineate?
P7 = 7! = 7 ∙6 ∙5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 5040 modi
Quant’è la percentuale di trovare almeno tre anagrammi comprensibili nella lingua italiana, supponendo che ci siano, combinando 5 lettere dell’alfabeto?
Gli anagrammi totali sono:
P5 = 5 ! = 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 120 anagrammi
La percentuale di trovare almeno tre anagrammi comprensibili sarà:
120 : 3 = 100 : X
Ci sono 2,5 possibilità su 100, o 25 possibilità su 1000, di trovare almeno tre anagrammi combinando tra di loro 5 lettere dell’alfabeto.
Si veda l’appendice a pagina 6. Figura N 2
Permutazione con ripetizione
Definizione: Si chiama “permutazione con ripetizione” di n elementi, con a elementi uguali e n - a distinti, le disposizione degli n elementi presi a n a n.
Teorema: Il numero delle permutazioni con ripetizioni di n elementi, con a elementi uguali e n – a distinti, disposti a n a n, è uguale alla permutazione degli n oggetti diviso la permutazione degli a oggetti uguali.
Pna=
In caso che oltre ad a elementi uguali ci siano b elementi uguali e n-(a+b) distinti, si avrà:
Pn (a, b) =
E così via fino alla precedente formula generale:
Pn(n1, n2, n3 …. nr) =
Studio: Gli anagrammi della parola ALA, costituita di 2 lettere uguali e una distinta, sono 3 e cioè:
ALA AAL LAA
3 anagrammi si ripetono.
Gli anagrammi distinti della parola ALA sarà:
P3(2)==3
Se le lettere fossero tutte diverse (vedi ad esempio la parola APE) si avrebbe:
P3 = 3! = 6
Il legame tra P3(2) e P3 è 2!, cioè la permutazione delle due lettere uguali.
P3(2) ·2! = P3
Scrivendo meglio, tornando così alla formula precedente si ha: P3(2)=
Applicazioni: Quanti sono gli anagrammi della parola MATEMATICA?
Analizzando la parola notiamo che M e T si ripetono 2 volte, A tre volte e E, I e C entrambi una volta.
Es: AMTTIMACAE o TATMACAEMI
Gli anagrammi saranno:
P10(3, 2, 2 )= = 151.200 anagrammi
Se non avessimo considerato le ripetizioni avremmo avuto 10! = 3.628.800 anagrammi
Appendice
Figura n 1 (7 giocatori e i 4 ruoli disponibili)
Figura n 2 (Porta logica AND a due e a tre ingressi)
Bibliografia
“Corso di matematica Volume II” Battelli
“Caso e probabilità” Johnson
“Calcolo delle probabilità” Schaum
“Mondo della matematica 4” Cedam
“Corso d’analisi 4” (Per gli istituti tecnici industriali) Ghisetti e Corvi
“Elementi d’analisi e complimenti di algebra” (Per gli istituti tecnici industriali) Ghisetti e Corvi
2