Prime nozioni di calcolo combinatorio ♦ la regola del prodotto ♦

Prime nozioni di calcolo combinatorio ♦ la regola del prodotto ♦

♦ disposizioni semplici e con ripetizione ♦ ♦ permutazioni ♦

♦ combinazioni semplici

♦ Il triangolo di Pascal

♦ Il binomio di Newton

Rosalba Barattero

ESERCITAZIONE N.6 4 novembre 2008

ESERCIZIO 1.

Primo principio elementare per contare

a) Le sedie di un teatro sono etichettate con una lettera minuscola seguita da un numero da 1 a 100.

Quale è il max. numero di sedie che possono essere etichettate in modo diverso tra loro ?

b) Dispondendo di 4 tipi di panini, 3 tipi di affettati e 2 tipi di salse,in quanti modi diversi si può dare un sandwich?

c) Quante sono le possibili stringhe di bit di lunghezza 7 ? a) Se supponiamo che le lettere siano 26 e i numeri 100, si tratta di contare le coppie ordinate (♦ ♣)

con ♦=una delle 26 lettere, ♣= uno dei numeri 1,2,3,…,100 Fissata la lettera a ci sono 100 scelte per il numero, fissata la lettera b ci sono 100 scelte per il numero, etc.

Quindi in totale 26⋅100 =2.600 modi differenti di etichettare una sedia ⇒ 2.600 è il max. n. di sedie etichettate in modo diverso.

b) Si può anche visualizzare con un diagramma ad albero:

⇒ 24 ″foglie″ (= 4⋅3⋅2 )

c) Ciascuno dei sette bits può essere scelto in due modi di- versi, poichè ogni bit è 0 o 1.

Contiamo le stringhe di lunghezza 7 ♦,♦, …,♦ dove

♦=0, 1. Per il I° posto abbiamo 2 scelte, per il II° posto abbiamo 2 scelte, … Totale : 2 ⁷ stringhe

Questa che abbiamo applicato è l’estensione della

R EGOLA D EL P RODOTTO Se una procedura può essere suddi- visa in due compiti e se ci sono m modi per fare il primo compito ed n modi per fare il secondo compito dopo che il primo è stato svolto, al- lora ci sono m⋅n modi di fare la procedura.

La regola si estende induttivamente al caso di una procedura suddivisa in più di 2 compiti.

Matematicamente la regola del prodotto esprime la P ROPRIETÀ Se A 1 , A 2 ,… ,A r sono insiemi finiti, il numero degli elementi del prodotto cartesiano

A 1 x A 2 … x A r degli insiemi A i (i=1,2,…,r) è il prodotto m ₁ ⋅ m 2 ⋅ ⋅⋅⋅ m r del numero degli elementi di ciascun insieme.

N OTAZIONE : il numero di elementi di un insieme fini- to A lo denotiamo |A| e lo chiamiamo

ESERCIZIO 2.

Contiamo le funzioni

Quante sono le funzioni f: A→B , se A ha k elementi e B ha n elementi ?

Per esemplificare sia A ={1,2,3}, B={1,2,3,4}.

f: {1,2,3}→ {1,2,3,4} è una funzione quando ad ogni ele- mento del dominio fa corrispondere uno ed un solo ele- mento del codominio.

Ad esempio:

1 → 3 2 → 2 3 → 3 4

Dunque le funzioni f da A in B sono n ^k , con n= |B|, k =|A| . Si chiamano disposizioni con ripetizione di n oggetti di classe k.

Ancora un esempio: Il n° delle possibili colonne al totocalcio è 3

(stringhe ♦,♦, …,♦ di lunghezza 13, dove ♦= 1,X,2).

f è individuata dalla terna ordinata (f(1),f(2),f(3)) , in questo caso (3,2,3) ( Da notare che gli elementi possono anche essere ripetuti). Quante sono queste terne?

Per f(1) abbiamo 4 scelte, idem per f(2), f(3). Quindi per la regola del prodotto ab- biamo in totale 4⋅4⋅4 = 4 ³ = 64 scelte.

Quindi ci sono 64 funzioni.

f

ESERCIZIO 3.

Contiamo le funzioni iniettive

Quante sono le funzioni iniettive f: A→B , se A ha k ele- menti e B ha n elementi ?

Funzione iniettiva: funzione che manda elementi distinti in elementi distinti. Ad es. sia f: {1,2,3}→ {1,2,3,4}, f è indi- viduata da una terna ordinata (•,∗,♦) di elementi distinti del codominio (se ad esempio: 1 →3, 2 →4, 3 →1 allora f è individuata dalla terna ordinata (3,4,1) ).

Quante sono le possibili terne (f(1),f(2),f(3)) ?

Ci sono 4 scelte per il I ^° elemento f(1) che, una volta fissato, consente 3 scelte per il II ^° , e così … 2 scelte per il III ^° ( per l’iniettività! ).

In totale le terne sono : 4⋅3⋅2= 24. Quindi 24 funzioni iniettive f: {1,2,3}→ {1,2,3,4}.

Attenzione! Occorre supporre che sia k≤n altrimenti non esi- stono funzioni iniettive !!

Le funzioni iniettive f:A→B , se |A|=k, |B|=n si chiamano disposizioni (semplici) di n oggetti di classe k , con k ≤ n e il loro n° è : D _n,k = n⋅(n-1)⋅(n-2)⋅ ⋅ ⋅(n-(k-1)) (k fattori de- crescenti consecutivi).

ESERCIZIO 4.

Contiamo le funzioni bigettive

In quanti modi n studenti possono sedersi su n sedie ? Supposto che su ogni sedia stia seduto un solo studente ☺ e se immaginiamo che le sedie siano numerate da 1 ad n, si tratta di assegnare ad ogni numero una persona.

1→p 1

2→p 2

…

n→p n

Le funzioni in questione si possono realizzare facendo al- zare gli studenti e facendoli risedere ogni volta su una se- dia diversa.

Le funzioni bigettive di chiamano infatti permutazioni e il loro n° è :

P _n = n (n-1)(n-2) ⋅ ⋅ ⋅ ⋅ 1 ( n fattori ) = n !

Le permutazioni sono un caso particolare delle disposi- zioni, quando k=n ( v. es. prec. ).

La funzione risulta iniettiva, ma anche surgettiva, ossia stabilisce una corrispondenza biunivoca tra gli insiemi {1,2,…,n} e {p 1 , p ₂ ,…, p _n }, essendo le persone esattamente tante quante le sedie.

Da notare che nel caso f:A→A con A insieme finiti si ha

f IN ⇔ f SU ⇔ f BIG.

ESERCIZIO 5.

Rappresentazione di sottoinsiemi con il computer

Sia U={1,2,3,4,5,6,7,8,9,10}. rappresentare con una strin- ga di bit di lunghezza 10

a) il sottoinsieme A di U , costituito dai dispari

b) il sottoinsieme B di U costituito dagli elementi ≤ 4 c) il sottoinsieme C di U costituito dagli elementi >8 a) A : 10 1010 1010

b) B : 11 1100 0000 c) C : 00 0000 0011

Le stringhe sono costruite così : (*)

1 se il corrispondente elemento appartiene al sottoinsieme 0 se il corrispondente elemento non appartiene al sottoinsieme Quindi dato in generale un insieme finito con un numero n di elementi supportato dalla memoria del computer, si scrivono gli elementi dell’insieme in un ordine qualsiasi e poi si rappre- sentano i sottoinsiemi con stringhe di lunghezza n, con la pro- prietà (*)

Con questa rappresentazione risulta facile determinare l’unione, l’intersezione dei sottoinsiemi etc.

Ad es. date le stringhe 10 1111 1001 e 00 0001 0100 la stringa che rappresenta l’unione dei due sott. ^mi è:

10 1111 1101 ( perché a∈Z∪W ⇔a appartiene ad almeno

ESERCIZIO 6.

Contare i sottoinsiemi di un insieme finito

Usare la regola del prodotto e l’esercizio 5 per provare che il numero di sottoinsiemi di un insieme finito A è 2 ^|A| . Supponiamo che sia A= {a 1 , a 2 , …, a n } ( |A|=n ) :l’ordine con cui scriviamo gli elementi di A è arbitrario, non ha al- cuna influenza sulla determinazione dei sottoinsiemi di A.

Sappiamo dall’esercizio 5. che c’è una corrispondenza biu- nivoca tra sottoinsiemi di A e stringhe di bit di lunghezza n.

Quindi contiamo le stringhe di bit di lunghezza n : sono le n-uple ordinate degli elementi 0, 1.

Per il I° posto della stringa abbiamo 2 scelte, idem per il II° , III°, …, n-esimo posto. In totale per la regola del pro- dotto ci sono 2 ⁿ stringhe e quindi 2 ⁿ è il numero dei sot- toinsiemi di A.

O SSERVAZIONE Tra i sottoinsiemi di A ci sono anche A stes-

so e l’insieme vuoto che sono rappresentati risp. dalla

stringa di lunghezza n che ha tutti 1 ( gli elementi stanno

tutti in A), e dalla stringa di lunghezza n costituita da tutti

0 ( l’insieme vuoto non contiene nessun elemento di A).

ESERCIZIO 7.

Combinazioni

Al termine di ogni stagione delle 22 squadre che compongono la serie B le prime due squadre in classifica vengono diretta- mente promosse in Serie A e retrocedono direttamente in Pri- ma Divisione le tre squadre peggio classificate.

a) Quante sono le possibili coppie di squadre promosse in A?

b) Quante sono le possibili terne di squadre retrocesse in C?

a) Se contiamo come nell’es 3. tutte le coppie ordinate (s ₁ , s ₂ ) abbiamo 22 scelte per s ₁ e 21 scelte per s ₂ , quindi 22⋅21 scelte.

Ma non è esatto perché le coppie qui non sono ordinate ! Ad ogni coppia non ordinata corrispondono due coppie ordina- te, quindi dobbiamo dimezzare il numero 22⋅21.

Il n° richiesto è 2

21

22 ⋅ = 231.

b) In questo caso se contiamo le terne ordinate (s ₁ , s ₂ , s ₃ ) con il criterio precedente ne otteniamo 22⋅21⋅20.

Ma come in a) non è esatto, poiché non conta l’ordine dei tre elementi che costituiscono la terna.

Per quanto dovremo dividere questa volta ?

Fissati s 1 , s 2 , s 3 quante sono le possibili terne ordinate?

(s ₁ , s ₂ , s ₃ ), (s ₁ , s ₃ , s ₂ ), …

sono tante quante le permutazioni di 3 elementi: 3! = 3⋅2⋅1.

Ne segue che il n° richiesto è 3 !

20 21

22 ⋅ ⋅ = 1540.

P ROPRIETÀ

Una collezione di elementi in cui l’ordine NON conta non è altro che l’insieme degli elementi stessi !

7a) equivale a: Se A è un insieme di 22 elementi, quanti sono i sott.

di A costituiti da 2 elementi ? ( 7b) idem …da 3 elementi ).

Se estraiamo k oggetti da n oggetti ( n≥k) senza tener conto dell’ordine diciamo che abbiamo una combinazione di classe k di n oggetti.

Il numero di queste possibili combinazioni è indicato C n,k e vale ^D _k!

, il coefficiente binomiale ^⎟

⎠

⎜ ⎞

⎝

⎛ k n .

Nel caso dell’esercizio 7a) : C _22,2 = ^⎟

⎠

⎜ ⎞

⎝

⎛ 2

22 = ^D _2!

= ²² _2! ^{⋅ 21} = ²² ₂ ^{⋅ 21}

Nel caso dell’esercizio 7b): C _22,3 = ^⎟

⎠

⎜ ⎞

⎝

⎛ 3

22 = ^D _3!

= ²² ₃ ^⋅ _⋅ ²¹ _{2 ⋅} ^⋅ ₁ ²⁰

In generale ⎟

⎠

⎜ ⎞

⎝

⎛ k

n = ^{n ( n − 1 )( n − 2 )} _k! ^{⋅ ⋅ ⋅ (n - (k - 1))}

(al numeratore ci sono k fattori decrescenti)

= _{k! (n} ^n! _{- k)!} ( discende dall’estensione della

proprietà del fattoriale n! = n (n-1)! )

I L TRIANGOLO DI P ASCAL – IL BINOMIO DI N EWTON

La figura a destra illustra la ′nascita′ del triangolo di Pa- scal. Escludendo i bordi, che valgono 1, tutti gli altri ele- menti si generano dall’alto verso il basso ( leggendo per righe) in modo tale che ogni elemento è la somma dei due elementi adiacenti della riga che sta sopra.

La figura a sinistra illustra il triangolo di Pascal con i rispet- tivi coefficienti binomiali.

Qui a sinistra:

Uno dei tanti insiemi numerici che si possono leggere nel triangolo di Pascal :

la successione dei numeri naturali .

La parola ′binomiale′ deriva dal fatto che i coefficienti bi- nomiali compaiono nello sviluppo del binomio (x+y) ⁿ , co- me mostra la fig. seg.

Binomio di Newton : ( ) ∑

=

⎟ −

⎠

⎜ ⎞

⎝

= ⎛

+ ⁿ

k

k k n n

y k x

y n x

0

R IEPILOGO CALCOLO COMBINATORIO

Denominazione Definizione Numero Disposizione con ripeti-

zione

Funzione : A →B

A={1,2,3,…k}, |B|=n n

Disposizione (semplice) Funzione iniettiva: A →B

A={1,2,3,…k}, |B|=n, con k ≤ n n(n-1)(n-2)…(n-(k-1)) Permutazione

Funzione bigettiva: A →A o funzione bigettiva f :{1,2,3,…,n}→A, n=|A|

n!

Combinazione di classe k di n elementi , k≤n

Sottoinsieme di {1,2,3,…n} di k

elementi ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

k

n