Alcune nozioni di
Combinatoria Enumerativa
Simone Rinaldi
Corso di Laurea in Matematica
Corso di Laurea in Scienza e Teoria dell’Informatica
La Combinatoria Enumerativa
Sia O una classe di oggetti,
p:O  N un parametro su O (taglia) tale che:
n On  o  O : p(o)  n
è un insieme finito
Problema: determinare
La sequenza
parametro p
an  On
an n0 enumera la classe O rispetto al
La Combinatoria Enumerativa
Sia O una classe di oggetti,
p:O  N un parametro su O tale che:
n On  o  O : p(o)  n
è un insieme finito
Problema: determinare
an  On
La sequenza an n0 si dice interpretazione
combinatoria per la classe O rispetto a p
Quanto vale an ?
Quanto vale an ?
Forma chiusa per an
Quanto vale an ?
Forma chiusa per an
Esempio
4n  3n 
an 
 
3n  1  n 
1
an  sin( n ) 
2
 5
n
Quanto vale an ?
Forma chiusa per an
Esempio
4n  3n 
an 
 
3n  1  n 
1
an  sin( n ) 
2
4k  3n 
an  


n

k
3
k

1
k 1


n
 5
n
Non è forma chiusa !!!
Quanto vale an ?
Forma chiusa per an
Relazione di ricorrenza per an
Esempio
a0  1
Numeri di
Fibonacci
a0  1
Numero delle
Involuzioni
a1  1
a1  1
an  an 1  an  2
an  an 1  (n  1)an  2
Quanto vale an ?
Forma chiusa per an
Relazione di ricorrenza per an Funzione generatrice di an
f ( x)   an x n  a0  a1 x  a2 x 2  a3 x 3  ...  ai x i  ...
n0
Quanto vale an ?
Forma chiusa per an
Relazione di ricorrenza per an Funzione generatrice di an
 2n  n
1
f ( x)     x 
1 4x
n0  n 
1
f ( x)   Fn x 
1  x  x2
n0
n
Funzione generatrice dei
coefficienti binomiali centrali
Funzione generatrice dei
numeri di Fibonacci
Quanto vale an ?
Forma chiusa per an
Relazione di ricorrenza per an Funzione generatrice di an
Andamento asintotico di an
Quanto vale an ?
Forma chiusa per an
Relazione di ricorrenza per an Funzione generatrice di an
Esempio
Fn
1 1 5 


2
5

n
Numeri di Fibonacci
Andamento asintotico di an
Quanto vale an ?
Esempio
Composizioni aventi la parte più
grande in prima posizione
1,1, 2,3,5,8,14, 24, 43,...
i
x
n
a
x
 (1  x)

n
i 1
n0
i 0 1  2 x  x
2n
an 
(1   (log 2 n))
n log(2)
Funzione generatrice di an
Andamento asintotico di an
Esempio 1. Alfabeto Morse
A  , 
Sia O la classe delle parole su A
e sia On la classe delle parole di O di lunghezza n
lunghezza 1:
lunghezza 2:
lunghezza 3:
lunghezza 4:

 ,
 ,   , 
 ,  ,   , , 
Quanto vale an=|On | ?
1, 2, 3, 5, 8, 13, 21, 34, 55, …
1
2
3
5
Gli oggetti di dimensione n2 possono essere ottenuti a
partire dagli oggetti di dimensione n-2

On-2
aggiungendo una linea
finale
oppure a partire dagli oggetti di dimensione n-1

On-1
an  an1  an2
a1  1
a2  2
aggiungendo un punto
finale
Numeri di Fibonacci
I numeri di Fibonacci enumerano la
classe O rispetto alla lunghezza
Gli oggetti di dimensione n2 possono essere ottenuti a
partire dagli oggetti di dimensione n-2

On-2
aggiungendo una linea
finale
oppure a partire dagli oggetti di dimensione n-1

On-1
an  an1  an2
a1  1
a2  2
aggiungendo un punto
finale
PROBLEMA: Quanto vale an ?
1  5   1  5 


n
an 1
2n 5
n
Torre di Hanoi
Torre con n dischi con
disposizione iniziale
data in figura
Scopo: trasferire l’intera torre in uno degli altri pali
muovendo un solo disco per volta e senza mai disporre un
disco sopra uno più piccolo
Tn= numero minimo di mosse per trasferire n dischi su un
palo rispettando le regole del gioco
Quanto vale Tn ?
T0=0
T1=1
T2=3
Per trasferire n dischi da A a C:
1. Si traferiscono gli n-1 più piccoli su B (Tn-1 mosse)
2. Si muove il disco più grande sul palo C, vuoto (1 mossa)
3. Si trasferiscono gli n-1 dischi da B a C (Tn-1 mosse)
T0  0
Tn  2Tn 1  1
Relazione di ricorrenza
La relazione ci permette di computare tutti i valori che
vogliamo di Tn
0,1,3,7,15,31,...
E’ possibile trovare una forma chiusa?
T0  1  1
Tn  1  2Tn1  2
n0
Posto U n  Tn  1
U0  1
U n  2n
U n  2U n 1
Tn  2 n  1
Linee nel piano
 Qual è il massimo numero di regioni definito da n
linee nel piano? Sia tale numero Ln
L0  1
L1  2
1
2
L2  4
1
3
2
4
 Se aggiungo una nuova linea (la n-esima) ho le
Ln-1 regioni definite dalle n-1 linee più n nuove
regioni
Ln 1
n
…
3
1
2
L0  1
Ln  Ln 1  n
1,2,4,7,11,16,22,...
Ln  Ln1  n 
 Ln 2  (n  1)  n 
 Ln 3  (n  2)  (n  1)  n 
........
 L0  n  (n  1)  ....  1  1  Sn
n
con
Sn   k
k 1
n ( n  1)
Sn 
2
n( n  1)
Ln 
1
2
Somma dei primi n numeri
positivi
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) ?
1
1

0
0

0
1
0
1
1
0
0
1
1
1

1
0 
il numero di tali matrici con dimensione n è 2nxn
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 ?
1
1

0
0

0
1
0
1
1
0
0
1
1
1

1
0 
il numero di tali matrici con dimensione n è 2nxn
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 ?
1
1

0
0

0
1
0
1
1
0
0
1
1
1

1
0 
il numero di tali matrici con dimensione n è 2nxn
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 ?
1
1

0
0

0
1
0
1
1
0
0
1
1
1

1
0 
il numero di tali matrici con dimensione n è 2nxn
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 ?
1
1

0
0

0
0
0
1
0
1
0
0
1
0

1
1 
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 ?
1 ,  0 
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 ?
1 ,  0 
 0 0 1 0  0 1  0 0  0 0
 0 0, 0 0, 0 0, 1 0 , 0 1 ,

 
 
 
 

 0 1   1 0   1 0   0 1
 1 0  ,  0 1  ,  1 0  ,  0 1

 
 
 

il numero di tali matrici con dimensione n è
con Fn n-esimo numero di Fibonacci
n
n 1
F
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 né orizzontale né verticale?
1
0

1
0

0
1
0
1
1
0
0
0
0
0

1
0 
Problemi difficili
Quante sono le matrici binarie quadrate (n x n) che non
contengono la sequenza 11 né orizzontale né verticale?
1 ,  0 
0
0

0
1

0 1 0  0 1  0 0  0 0
,
,
,
,
,





0  0 0  0 0 1 0  0 1
1 1 0
,

0   0 1 
Il numero di tali matrici con dimensione n non è noto !!
Esercizi sulle ricorrenze

Determinare la forma chiusa per la sequenza
definita dalla relazione di ricorrenza
a0  1
an  3an1  n  1
a1  5
a2  18
a3  58
an  ...
Esercizi sulle ricorrenze

Determinare la forma chiusa per la sequenza
definita dalla relazione di ricorrenza
a0  1
an  3an1  n  1
a1  5
a2  18
a3  58
an  ...
9 n n 5
an   3  
4
2 4
Osservazione: le condizioni iniziali
sono importanti !!
a0  1
a1  2
an  5an 1  6an 2
an  2 n 1
Osservazione: le condizioni iniziali
sono importanti !!
a0  1
a1  2
an  2 n 1
an  5an 1  6an 2
a0  1
a1  4
an  5an 1  6an  2
an  3n 1
Osservazione: le condizioni iniziali
sono importanti !!
a0  1
a1  2
an  2 n 1
an  5an 1  6an 2
a0  1
a1  4
an  3n 1
an  5an 1  6an  2
a0  1
a1  4
an  5an 1  6an  2
an  2  3n 1  2n 1
Esercizi

Determinare la forma chiusa per la sequenza
definita dalla relazione di ricorrenza
a0  1
an  an 1  k

Determinare la forma chiusa per la sequenza
definita dalla ricorrenza
a1  1
nan  (n  2)an1  2

Determinare la forma chiusa per la sequenza
definita dalla ricorrenza
a0  1
n
an 
an1  1
n 1
Esercizi
 Determinare la forma chiusa per la
sequenza definita dalla relazione di
ricorrenza
a0  1
an   an 1  
,   N
 Trasformare la seguente ricorrenza in una
ricorrenza finita
a0  1
a1  2
an  2an 1  an 2  ...  a0
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
n0
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
Osservazione: se
a0  0
a0  2
la soluzione è
an  2
n0
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
Osservazione: se
a0  1
la soluzione è
an  1
n0
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
n0
Osservazione: se
a0  1
la soluzione è
an  1
Dunque consideriamo valori inziali
a0  s  0,1, 2
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
n0
Ricorrenza quadratica, di difficile soluzione.
Poniamo:
1
an  bn 
bn
La ricorrenza diviene:
1
b0   a0  s
b0
1
1
2
bn   bn1  2
bn
bn1
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
n0
Ricorrenza quadratica, di difficile soluzione.
Poniamo:
1
an  bn 
bn
La ricorrenza diviene:
1
b0   a0  s
b0
1
1
2
bn   bn1  2
bn
bn1
bn  bn21
Cambio di variabile
Consideriamo la ricorrenza
an  an21  2
n0
Ricorrenza quadratica, di difficile soluzione.
Poniamo:
1
an  bn 
bn
La ricorrenza diviene:
1
b0   a0  s
b0
1
1
2
bn   bn1  2
bn
bn1
bn  b
2
n 1
bn  b
2n
0
Cambio di variabile
Poichè:

1
b0   s
b0
1
b0  s  s 2  4
2

Allora:


2n


1
1
an   s  s 2  4    s  s 2  4 
2

2

2n
Esercizio. Usando il metodo del cambio di variabile
risolvere la ricorrenza
a0  1
1
an 
1  an1
Sommatorie
 Consideriamo somme finite della forma
a1+a2+…+an
 Proprietà distributiva
 ca
kK
k
c  ak
kK
 Proprietà associativa
 a
kK
k
 bk    ak   bk
kK
kK
 Proprietà commutativa
a
kK
k


p ( k )K
a p(k )
con p(k) permutazione
degli interi
Principio di inclusione/esclusione
a   a
kK
k
kK '
k


kK  K '
ak 

kK  K '
ak
Esempio.
m
n
a  a
k 1
k
m
a
k m
n
k
 am   ak
k 1
1 m  n
m
 a0   a k
n0
n 1
a

ax
k
ax


1 x
k 0
x 1
k 0
n
k
k 1
Esercizio
Provare che:
n
k
n 1
k
2

(
n

1)2
2

k 0
Suggerimento:
Sn 1  Sn  (n  1)2
n
 k2
k 0
k 1
n
n 1
  2k 1
k 0
n
  ( k  1)2 k 1 
k 0
Esercizio
Provare che:
n
k
kx
 
k 0
x  ( n  1) x n 1  nx n 2
1  x 
2
Induzione sui numeri naturali
 Sia P una proprietà sui numeri
naturali
 Se valgono:
1. P(0);
2. P(n-1)  P(n)
allora P(n) per ogni n naturale
Esercizi
 Utilizzando l’induzione dimostrare che:
n ( n  1)(2n  1)
1 k 
6
n
2
n
2
(2
k

1)

n

k 0
n
k 1
n
k
2

(
n

1)2
1

k 1
 Utilizzando l’induzione dimostrare che:
a0  1
a1  4
an  5an 1  6an  2
an  2  3n 1  2n 1