Cap. 2 - IL C.C. IN ASTRATTO E IN FORMULE
INDICE
2.3 - Il coefficiente binomiale
2.4 - Disposizioni con ripetizione
2.6 - Permutazioni di n oggetti non tutti diversi; permutazioni cicliche
Supponiamo di avere n oggetti distinti
(ad es: n palline numerate progressivamente da 1 a n, oppure n lettere dell'alfabeto, ... ).
Sia ora k un intero, k ≤ n.
|
Le k-uple ORDINATE che si possono costruire utilizzando (senza ripetizione) k fra gli n oggetti dati sono anche dette "le DISPOSIZIONI degli n oggetti dati, presi a k a k" o anche "le disposizioni di classe k, di quegli n oggetti".
Il numero di tali k-uple ordinate ( = il numero delle
disposizioni di n oggetti, presi a k a k ), si indica con e risulta, utilizzando quello che abbiamo chiamato il Primo Principio Generale del Calcolo Combinatorio,
|
q Esempio 1: Con 10 oggetti distinti, quante quaterne ordinate posso costruire?
Risposta:
q Esempio 2: Se ho 10 ragazzi, in quanti modi posso scegliere: un portiere, un arbitro e un raccattapalle?
Risposta:
|
Le k-uple NON ORDINATE che si possono costruire utilizzando (senza ripetizione) k fra n gli oggetti dati sono anche dette "le COMBINAZIONI degli n oggetti dati, presi a k a k" o anche "le combinazioni di classe k, di quegli n oggetti". Il numero di tali k-uple NON ORDINATE ( = il numero delle combinazioni di n oggetti, presi a k a k ) si indica con Cn,k e risulta, utilizzando il Terzo Principio Generale,
(Osservazione: l’ultimo passaggio è stato ottenuto moltiplicando sia sopra che sotto per (n-k)! ; tale passaggio è possibile anche per k=n, perchè, per convenzione, si pone 0 ! =1) |
q Esempio 3: Con 10 oggetti distinti, quante quaterne non ordinate posso costruire?
Risposta:
|
IDEA-GUIDA Disposizioni: c’entra l’ordine Combinazioni: non c’entra l’ordine
|
|
2.3 Il coefficiente binomiale
|
I numeri
vengono anche detti
(per un motivo che chiariremo più avanti) “coefficienti binomiali”, e si
suole indicarli col simbolo specifico
o anche
|
|
IDEA-GUIDA
SUL COEFFICIENTE BINOMIALE: Il
coefficiente binomiale "dati n
oggetti, in quanti modi ne posso scegliere k?" |
|
Ricordiamo
che stiamo sempre supponendo k≤n.
In
particolare, si ha
|
|
Ricordando,
poi, la convenzione 0 ! = 1, possiamo scrivere anche
|
|
q
Esempio 4:
- Ho un
insieme di 7 oggetti distinti. In quanti modi posso sceglierne 3?
Risposta:
- Ho un
insieme di 7 oggetti distinti. In quanti modi posso sceglierne 2?
Risposta:
·
Ho un insieme di 7 oggetti distinti. In quanti
modi posso sceglierne 1?
Risposta:
(ovviamente....)
- Ho un
insieme di 7 oggetti distinti. In quanti modi posso sceglierne 6?
Risposta:
(anche questo risultato d’altronde è ben ovvio!
Sceglierne 6 su 7 equivale a sceglierne 1 (fra quei 7)
da escludere; e ciò si può fare in 7 modi)
q
Esempio 5: Con i 90 numeri del lotto, quanti
terni posso costruire?
Risposta:
q
Esempio 6: Con 5 numeri fissati, quanti terni
posso costruire?
Risposta:
PROPRIETA'
DEI COEFFICIENTI BINOMIALI
|
La proprietà più notevole è la seguente:
|
L’identità
in questione è facile da dimostrare col calcolo, comunque la sua verità è
evidente anche col seguente ragionamento:
è il numero di modi con cui è possibile,
dati n oggetti, sceglierne k;
ma
sceglierne k equivale a scegliere quegli n-k che si vogliono escludere;
e
tale ultima scelta si può effettuare in
modi.
Un'altra
proprietà importante è:
2.4 Disposizioni con ripetizione
|
Si parla di "DISPOSIZIONI CON RIPETIZIONE"
quando uno stesso oggetto, nella
k-upla ordinata, può essere ripetuto più di una volta. In questo caso,
non dev'essere necessariamente k≤n. Il numero delle disposizioni con ripetizione di n oggetti, presi
a k a k, si indica col simbolo
|
q
Esempio 7: utilizzando, con possibilità di
ripetizione, i 3 simboli A, B, C, quante stringhe di 5 lettere
posso comporre?(Per “stringa” si intende una
“sequenza di caratteri”)
Risposta:
D’3,5 = 35
q
Esempio 8: quante colonne è possibile
teoricamente giocare nel gioco del totocalcio?
Risposta:
Volendo, è un problema di disposizioni con
ripetizione.
Comunque, si ragiona meglio senza formule:
per il primo posto in alto nella colonna ho tre
possibilità: 1, X, 2;
per il secondo posto ho ancora 3 possibilità...
ecc...
Dunque:
313=1594323
IDEA-GUIDA Nel trattare questioni e problemi sul Calcolo
Combinatorio, alterna liberamente, secondo le tue preferenze e secondo ciò
che di volta in volta ritieni opportuno, l’applicazione delle formule con il
ragionamento diretto, basato sui Principi Generali appresi. |
q
Esempio 9: se si lanciano 10 monete (o anche: se
si lancia una moneta 10 volte) quanti sono gli esiti possibili?
Risposta: 210=1024
|
Le "PERMUTAZIONI DI n OGGETTI"
sono tutte le n-uple ordinate costruibili utilizzando, senza ripetizione,
quegli oggetti; il numero delle permutazioni di n
oggetti si indica col simbolo Pn
e dal Primo Principio si ha subito:
|
IDEA-GUIDA Permutazioni: modi in cui è possibile permutare
l'ordine di n oggetti |
q
Esempio 10: date 5 persone, in quanti modi si
possono mettere in coda davanti ad uno sportello?
Risposta:
P5=5!=120
2.6 - Permutazioni di n oggetti non tutti
diversi; permutazioni cicliche
|
Possiamo pure pensare alle "PERMUTAZIONI DI n OGGETTI
NON TUTTI DIVERSI". Presi n oggetti, dei quali m<n uguali fra loro, e gli altri tutti diversi l’uno dall’altro e
dai precedenti, quante n-uple ordinate distinguibili potremo costruire
utilizzando quegli n oggetti? Il numero di tali n-uple si indica con
|
Per
la dimostrazione, è sufficiente utilizzare un artificio che ci è ormai
consueto: quegli m oggetti che sono identici, pensiamoli inizialmente distinti,
poi considereremo "come se fosse una sola n-upla" tutto quel gruppo
di n-uple che, per effetto della indistinguibilità fra gli m oggetti, appaiono
identiche; ma il numero di tali n-uple è, evidentemente, m! (m fattoriale), perchè coincide col numero
di modi in cui è possibile permutare l'ordine di quegli m oggetti).
|
GENERALIZZAZIONE. Siano dati n oggetti, dei quali m uguali fra loro, r uguali
fra loro, s uguali fra loro ... (m+r+s+... = n). Quante n-uple ordinate distinguibili potremo costruire? Il numero di tali n-uple si indica col simbolo
|