Il calcolo combinatorio

Materie:	Appunti
Categoria:	Matematica
Voto:	1.7 (3)
Download:	198
Data:	31.01.2001
Numero di pagine:	4
Formato di file:	.doc (Microsoft Word)

CALCOLO COMBINATORIO
DISPOSIZIONI SEMPLICI
DEFINIZIONE: Dati n elementi distinti, si chiama «disposizione semplice» degli elementi presi a k a k (con kn), un gruppo ordinato di k degli elementi dati.
Due gruppi definiti in questo modo sono tra loro differenti se:
- sono diversi gli elementi
- è diverso l’ordine degli elementi (infatti per definizione si considerano gruppi ordinati)
Il numero di disposizioni semplici di n elementi presi a k a k, Dn,k, è:
Infatti se consideriamo n elementi e k posti allineati risulta che la prima posizione può essere occupata da n elementi, la seconda da n-1, perché l’elemento della prima posizione non può essere ripetuto, la terza n-2 e così fino a k, il numero delle posizioni.
ESEMPIO: quanti sono i numeri di tre cifre tutte diverse tra loro?
In questo caso e quindi , ma in questo modo si considerano anche quelle disposizioni che contengono 0 come cifra iniziale, il che non ha senso. Quindi poiché la prima posizione non può essere occupata da uno degli elementi, allora il numero di disposizioni è dato da: .
In definitiva: essendo allora .
DISPOSIZIONI CON RIPETIZIONE
DEFINIZIONE: Dati n elementi distinti, si dice «disposizione con ripetizione» una disposizione degli n elementi presi a k a k (con ) in cui uno stesso elemento può comparire sino a k volte.
Due gruppi differiscono se:
- contengono elementi diversi ( e s’intende anche un numero diverso di stessi elementi)
- gli elementi compaiono in ordine differente
Poiché ogni posizione può essere occupata da tutti gli elementi, e non da quelli che non hanno ancora occupato le precedenti (dato che possono ripetersi sino a k volte), risulta che il numero di disposizioni con ripetizione (fino a k volte), cioè:
ESEMPIO: Determinare in quanti modi possono accoppiarsi le facce di due dadi numerate da 1 a 6 (TARTAGLIA).
Ogni faccia del primo dado può essere accoppiata con tutte quelle dell’altro, cioè per ognuna il numero di accoppiamenti possibili con ripetizione è pari a 6, quindi in totale 36, cioè:
PERMUTAZIONI SEMPLICI
DEFINIZIONE: Dati n elementi distinti, si chiamano «permutazioni semplici» tutte le disposizioni semplici di n elementi presi a n a n.
Essendo n il numero di elementi per gruppo e dato che ogni posizione può essere occupata da tutti gli elementi che non hanno già occupato una delle precedenti risulta che il numero delle permutazioni semplici è:
ESEMPIO: Quante sono le combinazioni ottenibili dalla permutazione delle tre lettere a,b,c ?
La prima posizione può essere occupata da tre lettere, la seconda da due, la terza dall’unica rimanente, cioè: .
COMBINAZIONI SEMPLICI
DEFINIZIONE: Dati n elementi distinti, si dice «combinazione semplice» degli n elementi presi a k a k qualunque gruppo contenente k degli n elementi dati.
In base a questa definizione gruppi che contengono gli stessi elementi risultano uguali tra loro qualsiasi sia l’ordine in cui compaiano in esso.Quindi il numero delle combinazioni semplici è dato dal numero delle disposizioni semplici di n elementi presi a k a k diviso per il numero delle permutazioni possibili per il gruppo di k elementi. Quest’ultimo infatti esprime il numero di gruppi indifferenti tra loro in base alla definizione di combinazione semplice.
Poiché allora:
si indica anche come e si legge «n su k»:
n è detto anche ordine e k classe.
ESEMPIO: Quante cartelle occorre giocare al gioco del lotto per avere la certezza di vincere un terno?
La risposta è il numero delle combinazioni semplici di 90 elementi presi a 3 a 3 perché sono vincitori tutti i gruppi contenenti 3 dei numeri estratti in qualsiasi ordine.
COEFFICIENTI BINOMIALI
Il simbolo si chiama coefficiente binomiale per il ruolo che ha nelle formule del binomio di Newton.
ALCUNE PROPRIETÀ
1) Il numero di combinazioni semplici di n elementi presi a k a k è uguale al numero di combinazioni di n elementi della classe :

Infatti e per risulta .
Questa proprietà è particolarmente utile per perché facilita i calcoli.
2) Formula di STIFEL.
Questa formula risulta utile per comprendere alcuni aspetti dei coefficienti binomiali di Newton. Per risulta:
3) Proprietà di ricorrenza
Anche questa è utile nel caso del binomio di Newton-Tartaglia:
FORMULA DEL BINOMIO DI NEWTON
La formula permette di conoscere lo svolgimento della potenza con n intero positivo.
Per definizione risulta: per n volte.
Per calcolare questo prodotto per prima cosa occorre prendere un termine per ciascun binomio fattore e moltiplicarli tra di essi. Il generico risultato di questa operazione è il seguente:
Se in questo prodotto il fattore b compare k volte allora il fattore a comparirà volte e il tutto potrà essere espresso come:
Per calcolare il risultato totale è necessario sommare i risultati di tutti i possibili prodotti come questo, ovvero per tutti i valori di k. Per un determinato k il numero dei fattori in cui b compare k volte è uguale al numero di combinazioni semplici di n elementi presi a k a k 1, cioè .
Oppure:
I coefficienti sono detti coefficienti binomiali.
IL TRIANGOLO DI TARTAGLIA
Il triangolo di Tartaglia è costituito da una successione di numeri dei quali il primo è l’ultimo di ogni riga è 1, e ciascun’altro è uguale alla somma dei due numeri immediatamente adiacenti nella riga precedente.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
………….
Si dimostra come i numeri contenuti nella n-esima riga (con ) coincidono con i coefficienti binomiali dello svolgimento di .
Infatti, se è il grado di un dato binomio e k la sua posizione, in base alla formula di STIFEL risulta:
cioè, il coefficiente di posizione k di un binomio di grado è uguale alla somma dei coefficienti di posizione e della stessa posizione del binomio di grado n. Se n è la riga (per la prima) e k la posizione vale il triangolo di Tartaglia.
1 Infatti il numero di combinazioni semplici in un insieme di n elementi distinti1 è il numero di possibili gruppi composti ognuno di k elementi indipendentemente dal fatto che si ripetano. Poiché, però, gli elementi devono essere distinti sembra errato calcolare il numero di combinazioni semplici per insiemi come quelli in questione i quali sono composti solo da due elementi, a e b. Occorre però tenere presente che il numero di combinazioni semplici esprime il numero delle possibili combinazioni delle posizioni. Per esempio. Si consideri un insieme di 4 elementi e siano le posizioni assunte da ciascun di essi. Allora il numero di possibili gruppi di 3 posizioni è dato da e sono: . Se i quattro elementi sono costituiti da tre termini b e un termine a le possibili configurazioni che la successione potrà assumere saranno: bbba; abbb; babb; bbab.
---------------
------------------------------------------------------------
---------------
------------------------------------------------------------