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 n0 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 n0 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 ... n0 Quanto vale an ? Forma chiusa per an Relazione di ricorrenza per an Funzione generatrice di an 2n n 1 f ( x) x 1 4x n0 n 1 f ( x) Fn x 1 x x2 n0 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 n0 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 n2 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 an1 an2 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 n2 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 an1 an2 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 2Tn1 2 n0 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 Ln1 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 3an1 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 3an1 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)an1 2 Determinare la forma chiusa per la sequenza definita dalla ricorrenza a0 1 n an an1 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 an21 2 n0 Cambio di variabile Consideriamo la ricorrenza an an21 2 Osservazione: se a0 0 a0 2 la soluzione è an 2 n0 Cambio di variabile Consideriamo la ricorrenza an an21 2 Osservazione: se a0 1 la soluzione è an 1 n0 Cambio di variabile Consideriamo la ricorrenza an an21 2 n0 Osservazione: se a0 1 la soluzione è an 1 Dunque consideriamo valori inziali a0 s 0,1, 2 Cambio di variabile Consideriamo la ricorrenza an an21 2 n0 Ricorrenza quadratica, di difficile soluzione. Poniamo: 1 an bn bn La ricorrenza diviene: 1 b0 a0 s b0 1 1 2 bn bn1 2 bn bn1 Cambio di variabile Consideriamo la ricorrenza an an21 2 n0 Ricorrenza quadratica, di difficile soluzione. Poniamo: 1 an bn bn La ricorrenza diviene: 1 b0 a0 s b0 1 1 2 bn bn1 2 bn bn1 bn bn21 Cambio di variabile Consideriamo la ricorrenza an an21 2 n0 Ricorrenza quadratica, di difficile soluzione. Poniamo: 1 an bn bn La ricorrenza diviene: 1 b0 a0 s b0 1 1 2 bn bn1 2 bn bn1 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 an1 Sommatorie Consideriamo somme finite della forma a1+a2+…+an Proprietà distributiva ca kK k c ak kK Proprietà associativa a kK k bk ak bk kK kK Proprietà commutativa a kK k p ( k )K a p(k ) con p(k) permutazione degli interi Principio di inclusione/esclusione a a kK k kK ' k kK K ' ak kK 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 n0 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