Inizio
Clicca per iniziare
Entra nel mondo del calcolo combinatorio
Calcolo Combinatori
Calcolo
combinatorio
Home
home
HOME
PRESENTAZIONE
RAGRUPPAMENTI FRA GLI ELEMENTI DI DUE O
PIU’ INSIEMI
DISPOSIZIONI
PERMUTAZIONI
COMBINAZIONI
PROPRIETA’ DEI COEFFICIENTI BINOMIALI
Credits
PRESENTAZIONE
presentazione
Il calcolo combinatorio ha come oggetto il calcolo dei
modelli con i quali possono essere associati gli elementi
di due o più insiemi o di uno stesso insieme.
Nelle applicazioni può sorgere il problema di conoscere
in quanti modi si può presentare un fenomeno.
Il problema di conoscere le risposte alle domande può
sembrare banale e in effetti lo è se il numero degli
elementi è piccolo, ma quando il numero degli elementi
è elevato la difficoltà consiste proprio nel formare tutti i
raggruppamenti senza tralasciarne alcuno e senza
cadere in ripetizioni.
Home
Avanti
Il calcolo combinatorio riveste notevole importanza
nella matematica del <<discreto>>, dove il
termine <<discreto>> contrapposto a
<<continuo>> sta a indicare che gli elementi sono
separati e i valori appartengono a N.
I raggruppamenti possono essere fatti in vari modi.
E' bene sottolineare che prima di applicare ai casi
concreti le formule che otterremo, si dovranno
esaminare attentamente i dati e gli scopi che ci si
prefiggono.
Poiché la matematica offre <<modelli>> che
cercano di interpretare i fatti reali, occorre capire a
quale modello bisogna riferirsi per le varie
applicazioni.
Home
Indietro
Raggruppamenti fra + insiemi
RAGRUPPAMENTI FRA GLI
ELEMENTI DI DUE O PIU' INSIEMI
La moltiplicazione costituisce un primo esempio di calcolo
combinatoro.
Il problema di formare sigle è una questione di attualita:
è il problema della codificazione, ossia della
individuazione di elementi di qualunque tipo mediante
sigle numeriche o alfanumeriche.
Home
Sia dato l’insieme: A={a,b,c,d}. Tutte le sigle di due
elementi che si possono formare con gli elementi di A
sono le seguenti:
aa
ab
ac
ad
ba
bb
bc
bd
ca
cb
cc
cd
da
db
dc
dd
Questi raggruppamenti vengono detti disposizione con
ripetizione di 4 elementi di classe 2 e sono in numero di
4*4=42=16
Home
Avanti
Indietro
DISPOSIZIONI
Disposizioni
I diagrammi ad albero sono particolari rappresentazioni
grafiche che permettono di costruire le disposizioni
semplici o con ripetizioni e di contarle facilmente.
In generale:
Dato un insieme A di n elementi, si definiscono
disposizioni di classe k i raggruppamenti di k elementi
scelti fra gli n dell'insieme A tali che ogni
raggruppamento differisca dagli altri :
o per la natura degli elementi
o per l'ordine degli elementi.
Home
Avanti
Le disposizioni si dicono:
a) Semplici, se ogni raggruppamento contiene
elementi distinti fra loro; il loro numero si indica con
Dn,c;
b) Con ripetizione, se nei raggruppamenti gli elementi
di A possono comparire più di una
volta; il loro
numero si indica con D'n,k.
Per k qualsiasi si ha quindi: D'n,k = nk
Perciò:
il numero delle disposizioni con ripetizione di n
elementi di classe k è nk.
Per k qualsiasi, purché k  n, si ha:
Dn,k=n(n-1)(n-2)...[n-(k-1)]
Home
Avanti
Indietro
Perciò:
il numero delle disposizioni semplici di n elementi di
classe k è uguale al prodotto di k fattori interi consecutivi
decrescenti a partire da n.
Osservazioni :
La condizione k n per le disposizioni semplici è imposta
dal fatto che si possono fare dei raggruppamenti formati
con elementi tutti diversi solo se, al massimo, si
prendono tutti gli elementi dell' insieme.
Tale limitazione non esiste, ovviamente, per le
disposizioni con ripetizione perché, in questo caso, gli
elementi possono essere ripetuti quante volte si vuole.
In generale, se l'insieme A contiene k elementi, e
l'insieme B contiene n elementi (con k n),il numero delle
funzioni iniettive da A in B è uguale al numero delle
disposizioni semplici di n elementi di classe k, cioè:
Dn,k=n(n-1)(n-2)...(n-k+1).
Home
Indietro
PERMUTAZIONI
Dato un insieme A di n elementi, si definiscono
permutazioni di n elementi (diversi fra loro) i
raggruppamenti formati dagli n elementi presi in un ordine
Permutazioni
qualsiasi.
Una permutazione differisce da un'altra solo per l'ordine
degli elementi.
Le permutazioni coincidono con le disposizioni semplici di
classe n, quindi il calcolo del numero delle permutazioni è
uguale al calcolo del numero delle disposizioni semplici di n
elementi di classe n, cioè:
Pn=Dn,n=n(n-1)(n-2)...[n-(n-2)]*[n-(n-1)]=n(n-1)(n-2)…2*1
Il numero delle permutazioni di n elementi è allora: Pn=n!
Home
Avanti
Osserviamo che n! è funzione di n e cresce rapidamente al
crescere di n.
Osservazione: Le permutazioni di n elementi si possono
collegare alle funzioni biettive fra due insiemi A e B di n
elementi (ricordando che una funzione è detta biettiva
se ogni elemento di B è corrispondente di uno e un solo
elemento di A).
Home
Indietro
COMBINAZIONI
Combinazioni
Dato un insime A di n elementi, si definiscono
combinazioni semplici degli n elementi di classe k
(con k  n) i raggruppamenti di k elementi, scelti fra
gli n dell'insieme A, tali che ogni raggruppamento
differisca dagli altri per la natura degli elementi
(senza considerare l'ordine degli elementi).
Per determinare il numero delle combinazini di n
elementi di classe k ricaviamo una formula che
esprime un legame fra il numero delle combinazioni
e quello dello disposizioni di n elementi a k.
Home
Avanti
Le disposizioni di n elementi di classe k si ottengono dalle
combinazioni di n elementi di classe k, permutando fra
loro i k elementi che costituiscono ciascun
raggruppamento.
Indicato con Cn,k il numero delle combinazioni semplici di
n elementi di classe k, si ha:
Cn,k * Pk = Dn,k
cioè: Cn,k=Dn,k/Pk=n(n-1)(n-2)...[n-(k-1)]/k!
Il simbolo (n k) è detto coefficiente binomiale per il suo
uso nello sviluppo delle potenze del binomio.
Osservazione importante: In molti tesi stranieri
(particolarmente in testi anglosassoni) non si introduce il
termine <<disposizioni>>, ma si usa la locuzione
<<permutazione di n elementi di classe k>> e invece di
Dn,k, si scrive nPk; le combinazioni sono indicate con nCk,
anzichè con Cn,k.
Home
Indietro
PROPRIETA' DEI
COEFFICIENTI BINOMIALI
Proprietà coef binomiali
Il numero delle combinazioni di n elementi di
classe k è eguale al numero delle combinazioni
degli n elementi di classe(n-k).

n
k
Dn , k
n!


k!
k!( n  k )!
Home
Credits
Home