Le combinazioni

Calcolo combinatorio

Start

Le combinazioni

3. Combinazioni con ripetizione

2. Coefficienti binomiali

1. Combinazioni semplici

indICE

Chiamiamo questi gruppi combinazioni semplici di 4 elementi di classe 3 e li indichiamo con C4,3

= = 4

3! 6

4*3*2 24

C4,3=

Per piantare il primo seme avremo 4 possibilità, per il secondo ne avremo 3, e infine per il terzo ne avremo 2 (4*3*2) ma se li pianto in ABC o CAB avrò sempre i semi negli stessi punti=> non dipende dall'ordineDevo dividere poi quel numero per il numero di modi che abbiamo di scambiare l'ordine (3!)

Combinazioni semplici

Abbiamo un orto con a disposizione 4 spazi per piantare dei semi, noi abbiamo 3 semi, quante sono le possibili combinazioni in cui possiamo piantarli

Per generalizzare

Una combinazione è uguale al quozionte di una disposizione e una permutazione

Pk k!

Dn,k n*(n-1)*(n-2)*...*(n-k+1)

3! P3

4*3*2 D4,3

C4,3=

Cn,k =

Se chiamiamo gli elementi del nostro insieme n (4) e chiamiamo k il numero di elementi dei sottoinsiemi scelti tra n (3):

Combinazioni semplici

Combinazioni semplici

Pk k!

Dn,k n*(n-1)*(n-2)*...*(n-k+1)

Cn,k =

con k<= n

Le combinazioni semplici di n elementi distinti di classe k (con 0<k<=n) sono tutti quei sottogruppi di n di k elementi che differiscono per almeno un elemento, ma non per l'ordine

Per esempio:

il coefficiente binomiale di due numeri naturali n e k, con 0 ≤ k ≤ n, è il numero:

COEFFICIENTI BINOMIALI

il numero delle combinazioni viene anche indicato con il simbolo che si chiama coefficiente binomiale.

00

= 1

0! 0! 0!

( )

• se k = n

• se k = 0 e n = 0

• se k = 0 e n ≠ 0

Dalla definizione e dalla proprietà del fattoriale si ottiene che:

la formula di ricorrenza si usa principalmente quando conosciamo il valore del coefficiente binomiale per un certo valore di k e dobbiamo trovare i valori delle classi sucessive (o precedenti)

nk

( )⋅

nk + 1

n - kk + 1

( )

• FORMULA DI RICORRENZA

• LEGGE DELLE CLASSI COMPLEMENTARI :

le scelte di k elementi sono in corrispondenza biunivoca con i sottoinsiemi degli n-k elementi tralasciati.

Proprietà

( )

6 6-3

6 3

( )

= 2002 ⋅ =3003

14 5

14 6

( )

14-5 5+ 1

9 6

( )⋅

= 2002, allora:

14 5

( )

= 6! = 6! = 3!(6-3)! (6-3)! [6-(6-3)]!

esempi

se sappiamo che

legge delle classi complementari

Formula di ricorrenza

Utilizzando la formula che esprime il numero delle disposizioni semplici come rapporto tra due fattoriali, abbiamo:

A questo punto possiamo giustificare la definizione delle combinazioni semplici Cn,k =

Riprendiamo il problema affrontando le combinazioni con ripetizione:Lanciamo una moneta composta da testa (T) e croce (C) e verifichiamo quante combinazioni sono possibili:Se i lanci sono 2, il numero delle possibilità rispetto alle disposizioni si riduce a 3:TT TC CC k = 2Se i lanci sono 3, il numero delle possibilità rispetto alle disposizioni si riduce a 4:TTT TTC TCC CCC k = 3Se i lanci sono 4, il numero delle possibilità rispetto alle disposizioni si riduce a 5: TTTT TTTC TTCC TCCC CCCC k = 4Chiamiamo questi raggruppamenti combinazioni con ripetizioni

Combinazioni con ripetizione:

• Ogni elemento può essere ripetuto al massimo fino a k volte.
• Non interessa l'ordine con cui gli elementi si presentano.
• E' diverso il numero di volte col quale un elemento compare.

Le combinazioni con ripetizione di n elementi distinti di classe k ( con k numero naturale non nullo) , sono tutti i gruppi di k elementi che si possono formare, nei quali:

Combinazioni con ripetizione

A cura di: Angelini Luca, Frenquellucci Lara, Marini Pietro, Nervi Chiara, Ponti Martina, Rotini Luca

Fine