Insiemi e calcolo combinatorio

(1)

Insiemi e calcolo combinatorio

Università Roma Tre – Dipar3mento di Matema3ca e Fisica IN440 – O=mizzazione Combinatoria

Prof. Marco Liverani

(2)

Insiemi

§

Un insieme A è una collezione di elementi di qualsiasi natura, purché non contenga lo stesso A

§

Paradosso di Russel (Bertrand Russel, 1902):

Un insieme è «straordinario» se contiene anche se stesso. È «ordinario» se non contiene se stesso.

Sia S = {collezione di tutti gli insiemi ordinari}

Problema: S è ordinario? Se lo fosse, allora S ∈ S, collezione di tutti gli insiemi ordinari; ma allora S sarebbe

straordinario e questo ci porta ad una contraddizione! Se fosse straordinario, allora dovrebbe risultare S ∈ S, ma per definizione S contiene insiemi ordinari, per cui anche in questo caso abbiamo una contraddizione

§

Per evitare situazioni paradossali evitiamo di trattare insiemi straordinari: d’ora in avanti consideriamo come insieme solo una collezione di oggetti che non contengono come elemento anche la collezione stessa

§

In generale possiamo rappresentare un insieme con un computer attraverso una lista o un array. In Python esiste la struttura dati set (liste prive di elementi duplicati) su cui possiamo anche utilizzare gli operatori di unione «|», intersezione «&», differenza «-» e differenza simmetrica «^»

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 1

Bertrand Russel (1872 – 1970)

(3)

Insiemi

§

L’insieme delle parti (o insieme potenza) di un insieme A è l’insieme di tutti i sottoinsiemi di A e lo indichiamo con 𝒫(A)

§

Una partizione di un insieme A è una collezione di sottoinsiemi di A, {A₁, ..., A_k} ∈ 𝒫(A), tale che

∪

i = 1,...,k A_i = A e A_i ∩ A_j = ∅ per ogni i ≠ j

§

Una relazione di equivalenza 𝜌 sugli elementi di un insieme A è una relazione riflessiva (a 𝜌 a), simmetrica (a 𝜌 b ⇒ b 𝜌 a) e transitiva (a 𝜌 b e b 𝜌 c ⇒ a 𝜌 c)

§

Dato un elemento a ∈ A, una classe di equivalenza su A definita dalla relazione d’equivalenza 𝜌 è l’insieme [a]_𝜌 = {b ∈ A: a 𝜌 b}

§

Le classi di equivalenza su A definite mediante una relazione 𝜌 formano una partizione di A

(4)

Cardinalità

§

Insieme finito: gli elementi possono essere messi in corrispondenza biunivoca con l’insieme {1, 2, ..., n}. La cardinalità dell’insieme è n (n = |A|)

§

Insieme numerabile: è possibile mettere gli elementi dell’insieme in corrispondenza biunivoca con ℕ. L’insieme ha la cardinalità del numerabile ℵ₀

§

Insieme continuo: non è numerabile, non è possibile creare una corrispondenza biunivoca con ℕ.

L’insieme ha la cardinalità del continuo ℵ₁

§

Sia A un insieme finito, con |A| = n. Allora |𝒫(A)| = 2ⁿ

Dimostrazione per induzione su |A|: se A = ∅ allora 𝒫(A) = {∅} e quindi |𝒫(A)| = 1 = 2⁰. Si mostra poi che se

|𝒫(A)| = 2^n–1 per |A| = n–1, allora per A’ = A ∪ {x}, |A’| = n e |𝒫(A’)| = 2ⁿ; infatti avremo il doppio dei sottoinsiemi di A: tutti i sottoinsiemi di A e tutti i sottoinsiemi di A uniti a {x} ∎

Dimostrazione costruttiva: si può creare una corrispondenza biunivoca tra 𝒫(A) e le stringhe binarie con n elementi. Con n cifre binarie possiamo definire 2ⁿ numeri naturali: 0, 1, 2, ..., 2^n–1. Quindi |𝒫(A)| = 2ⁿ ∎

Georg Cantor (1845 – 1918)

(5)

Sottoinsiemi e stringhe binarie

A = { a₁, a₂, a₃, a₄, a₅ } A’ = { a₁, a₂, a₃, a₄, a₅ }

S = 1 0 1 1 0

n = 4 S = ( 0, 0, 0, 0 ) i = 1 S = ( 1, 0, 0, 0 ) i = 1, 2 S = ( 0, 1, 0, 0 ) i = 1 S = ( 1, 1, 0, 0 ) i = 1, 2, 3 S = ( 0, 0, 1, 0 ) i = 1 S = ( 1, 0, 1, 0 ) i = 1, 2 S = ( 0, 1, 1, 0 ) i = 1 S = ( 1, 1, 1, 0 ) i = 1, 2, 3, 4 S = ( 0, 0, 0, 1 ) i = 1 S = ( 1, 0, 0, 1 ) i = 1, 2 S = ( 0, 1, 0, 1 ) i = 1 S = ( 1, 1, 0, 1 ) i = 1, 2, 3 S = ( 0, 0, 1, 1 ) i = 1 S = ( 1, 0, 1, 1 ) i = 1, 2 S = ( 0, 1, 1, 1 ) i = 1 S = ( 1, 1, 1, 1 ) i = 1, 2, 3, 4 S = ( 0, 0, 0, 0 )

Esercizio: possiamo modificare l’algoritmo per produrre tutti i sottoinsiemi di una lista/array?

(6)

Permutazioni

§

Permutazione di un insieme A: corrispondenza biunivoca di A con se stesso.

Es.: A = {1, 2, 3}, π(A) = {1→2, 2→1, 3→3}

§

Se |A| = n allora possono essere definite n! permutazioni di A.

Dimostrazione: abbiamo n scelte per il primo elemento, per ciascuna di queste abbiamo n−1 scelte per il secondo elemento, ecc. Complessivamente quindi n (n−1) (n−2) ... 1 = n! ∎

§

Algoritmo per la costruzione delle permutazioni di A = ⟨a₁, a₂, ..., a_n⟩:

•

a partire da una generica permutazione π(A) si ricava la permutazione «successiva», πʹ(A), mediante il seguente procedimento:

•

si individua il massimo indice k, 0 ≤ k < n, tale che a_k< a_k+1 e si scambia l’elemento a_k con il più piccolo elemento a_h > a_k con k < h ≤ n

•

infine si ordinano in ordine crescente gli elementi a_k+1, a_k+2, ..., a_n

(7)

Permutazioni

A partire da una generica permutazione π(A) si ricava la permutazione «successiva», πʹ(A), mediante il seguente procedimento:

• si individua il massimo indice k, 0 ≤ k < n, tale che a_k< a_k+1 e si scambia l’elemento a_k con il più piccolo elemento a_h >

a_kcon k < h ≤ n

• infine si ordinano in ordine crescente gli elementi a_k+1, a_k+2, ..., a_n

n = 4 A = ( 1, 2, 3, 4 ) k = 3 A = ( 1, 2, 4, 3 ) k = 2 A = ( 1, 3, 2, 4 ) k = 3 A = ( 1, 3, 4, 2 ) k = 2 A = ( 1, 4, 2, 3 ) k = 3 A = ( 1, 4, 3, 2 ) k = 1 A = ( 2, 1, 3, 4 ) k = 3 A = ( 2, 1, 4, 3 ) k = 2 A = ( 2, 3, 1, 4 ) k = 3 A = ( 2, 3, 4, 1 ) k = 2 A = ( 2, 4, 1, 3 ) k = 3 A = ( 2, 4, 3, 1 )

k = 1 A = ( 3, 1, 2, 4 ) ... ...

(8)

Disposizioni

§

Disposizione semplice di k elemenO: sequenza ordinata di k elemenO di A senza ripeOzione degli elemenO («ordinata» signiﬁca che conta l’ordine con cui dispongo gli elemenO: due disposizioni semplici diverse possono avere gli stessi elemenO, ma disposO in ordine diverso)

Es.: se A = {1, 2, 3} le disposizioni su A con k = 2 elemen1 sono (1, 2), (1, 3), (2, 1), (2, 3), (3,1), (3,2)

§

Se |A| = n allora il numero di disposizioni semplici con k elemenO su A è

Dimostrazione. Abbiamo n scelte per il primo elemento di ogni disposizione, n – 1 scelte per il secondo elemento,

… (n – k + 1) scelte per il k-esimo elemento. Quindi in generale:

§

Le disposizioni con ripeOzioni di k elemenO su un insieme di n elemenO sono invece n^k: abbiamo infaQ a disposizione n scelte per il primo elemento, altre n scelte per il secondo elemento, ..., ancora n scelte per il k-esimo elemento

Università Roma Tre – Dipar=mento di Matema=ca e Fisica

Marco Liverani, O>mizzazione Combinatoria 7

<latexit sha1_base64="+1GJZvWpyD9m/l1R4oxgTaMlTXA=">AAACGnicbVC7SgNBFJ31GeNrfXRaTAxCBA27KdRGCJrCMoJ5QBLC7GQ2GTI7u8zMimHZxu/wA2z1E+zExsJCe8HWT3DyKEzigQuHc+7l3nucgFGpLOvTmJmdm19YTCwll1dW19bNjc2y9EOBSQn7zBdVB0nCKCclRRUj1UAQ5DmMVJzuRd+v3BAhqc+vVS8gDQ+1OXUpRkpLTXO30Iz4IezG8AzWXYFwxFNxlOFH3YNU3DTTVtYaAE4Te0TS+dzXz0fhbbvYNL/rLR+HHuEKMyRlzbYC1YiQUBQzEifroSQBwl3UJjVNOfKIbESDL2K4r5UWdH2hiys4UP9ORMiTsuc5utNDqiMnvb74n1cLlXvaiCgPQkU4Hi5yQwaVD/uRwBYVBCvW0wRhQfWtEHeQzkLp4Ma2BJIhRW7jpE7GnsxhmpRzWfs4a13Z6fw5GCIBdsAeyAAbnIA8uARFUAIY3IEH8AiejHvj2XgxXoetM8ZoZguMwXj/BaxXpC0=</latexit>

D_n,k = _{(n k)!}^n!

<latexit sha1_base64="COFrZO6z2etcFtI5F0sB4PXz5lc=">AAACi3icfVFda9swFJXdrcuypcs+Xspe1IRCQrdgZ7COsUJoO+hjB8sHJCHIipyIyLKRrkuD8U/Yf9vj9l7oa6F/oHIcWPPBLujqcM6594orLxJcg+P8teydJ093nxWeF1+8LO29Kr9+09FhrChr01CEqucRzQSXrA0cBOtFipHAE6zrzc4yvXvFlOah/AnziA0DMpHc55SAoUblX+ejRH7AsxSfYIlr8qNbz3KzjgfjEHSGZ0eGO8EDXxGa/M+T3XnOHLnm1tNkK5/+a3mwtByko3LVaTiLwJvAXYJqq3lz9+f897vLUfnWtKNxwCRQQbTuu04Ew4Qo4FSwtDiINYsInZEJ6xsoScD0MFmsLcWHhhljP1TmSMAL9nFFQgKt54FnnAGBqV7XMnKb1o/B/zJMuIxiYJLmg/xYYAhx9gd4zBWjIOYGEKq4eSumU2J2AeanVqZEWhBg12nRbMZd38Mm6DQb7ueG88Ottk5RHgX0HlVQDbnoGLXQBbpEbUTRvbVvVayqXbI/2V/tb7nVtpY1b9FK2N8fAPnWvxQ=</latexit>

D_n,k = n(n 1)(n 2)...(n k + 1) = n(n 1)(n 2)...(n k+1)(n k)(n k 1)...1)

(n k)(n k 1)...1 = _{(n k)!}^n!

(9)

Combinazioni

§

I sottoinsiemi di A con k elementi sono le combinazioni semplici di A con k elementi

§

In un insieme l’ordine degli elementi non conta, per cui il numero di combinazioni semplici di k elementi su un insieme di cardinalità n, è dato dal rapporto tra il numero D_n,k di disposizioni semplici di k elementi ed il numero k! di permutazioni di un insieme di k elementi:

§

Algoritmo ingenuo per la generazione delle combinazioni semplici con k elementi di A:

•

si generano tutte le stringhe binarie con n elementi

•

tra queste si scelgono solo quelle con k elementi uguali a 1

•

a ciascuna di queste stringhe binarie corrisponde una combinazione semplice di k elementi su A

§

L’algoritmo ingenuo genera tutte le stringhe binarie, ossia 2ⁿ stringhe, quando a noi interessa solo una piccola parte di queste... è eccessivamente oneroso (complesso)!

<latexit sha1_base64="imPufdtX6ZCfBPp7k2iuIWJTRzc=">AAACG3icbZC7SgNBFIZn4y3GW1SwEWFiFCJo2LVQGyGYxjKCuUASwuxkNhl2dnaZmRXDspWvoQ9gq62dndha+ATa+QpOLoVJ/GHg5z/ncM58dsCoVKb5aSRmZufmF5KLqaXlldW19PpGRfqhwKSMfeaLmo0kYZSTsqKKkVogCPJsRqq2W+zXqzdESOrza9ULSNNDHU4dipHSUSu9U2xF/NCN4TlsOALhiGfiyM3k+JF7kIlb6ayZNweC08YamWyh8PP9snW/V2qlvxptH4ce4QozJGXdMgPVjJBQFDMSpxqhJAHCLuqQurYceUQ2o8E3YrivkzZ0fKEfV3CQ/p2IkCdlz7N1p4dUV07W+uF/tXqonLNmRHkQKsLxcJETMqh82GcC21QQrFhPG4QF1bdC3EWahtLkxrYEkiFFbuOUJmNNcpg2leO8dZI3rzSiCzBUEmyDXZADFjgFBXAJSqAMMLgDj+AJPBsPxqvxZrwPWxPGaGYTjMn4+AUGNaRE</latexit>

C_n,k = n!

k!(n k)!

(10)

Combinazioni

§

^Strategia:

• generiamo solo combinazioni ordinate, in ordine crescente di k elemen2 seleziona2 dall’insieme {1, 2, ..., n}

• come elemento i-esimo della sequenza ordinata che rappresenta una determinata combinazione di k elemen2 su A, scegliamo c_i tale da soddisfare la seguente condizione: n − (k − i + 1) < c_i ≤ n − (k − i)

§

Per passare da una combinazione (c₁, c₂, ..., c_k) alla successiva nell’ordine lessicografico, si prendono in esame gli elemen: c_i a par:re da i = k fino ad i = 1 (ciclo alle righe 8–10) fino a quando non si incontra un elemento c_i che non abbia assunto il valore massimo per la posizione i-esima: c_i < n − (k − i)

§

In tal caso si incrementa di 1 l’elemento c_i e si impostano di conseguenza il valore degli elemen:

successivi, c_i+1, c_i+2, ..., c_k con il valore minimo per ciascun elemento

(11)

Combinazioni

n = 6, k = 4 A = { a, b, c, d, e, f }

1 2 3 4 5 6

C = (1, 2, 3, 4) à { a, b, c, d } C = (1, 2, 3, 5) à { a, b, c, e } C = (1, 2, 3, 6) à { a, b, c, f } C = (1, 2, 4, 5) à { a, b, d, e } C = (1, 2, 4, 6) à { a, b, d, f } C = (1, 2, 5, 6) à { a, b, e, f } C = (1, 3, 4, 5) à { a, c, d, e } C = (1, 3, 4, 6) à { a, c, d, f } C = (1, 3, 5, 6) à { a, c, e, f } C = (1, 4, 5, 6) à { a, d, e, f } C = (2, 3, 4, 5) à { b, c, d, e } C = (2, 3, 4, 6) à { b, c, d, f } C = (2, 3, 5, 6) à { b, c, e, f } C = (2, 4, 5, 6) à { b, d, e, f } C = (3, 4, 5, 6) à { c, d, e, f }

(12)

Coefficiente binomiale

§

Il numero di combinazioni di n elemenO in classi di k è il coeﬃciente binomiale:

§

Esprime il coeﬃciente nell’espressione della potenza di un binomio:

§

Dalla deﬁnizione di combinazione semplice e di coeﬃciente binomiale segue che un modo alternaOvo per contare gli elemenO dell’insieme delle parO di A, 𝒫(A), è quello di sommare il numero di combinazioni di n elemenO in classi di k, per k = 0, 1, 2, ..., n; per cui risulta:

<latexit sha1_base64="qBoe91nlyzu6k6CCPfuoIJPmoXs=">AAACInicbZDLSgMxFIYzXmu9VV26Sa2CLiwzLtSN4GXjsoKtQltKJj1jw2SSIcmIZZgX8Dl8AMGVLnwAd+JK0LWvYXpZWPWHwM9/zuGcfH7MmTau++6MjU9MTk3nZvKzc/MLi4Wl5ZqWiaJQpZJLdekTDZwJqBpmOFzGCkjkc7jww5Ne/eIalGZSnJtuDM2IXAkWMEqMjVqF9VTgBu1IqQGHOMMHuBEoQlNRzNKwuCm2w61i1iqU3LLbF/5rvKEpHR65D59Lz6LSKnw12pImEQhDOdG67rmxaaZEGUY5ZPlGoiEmNCRXULdWkAh0M+3/JsMbNmnjQCr7hMH99OdESiKtu5FvOyNiOvp3rRf+V6snJthvpkzEiQFBB4uChGMjcQ8NbjMF1PCuNYQqZm/FtEMsDWMBjmyJNScGbrK8JeP95vDX1HbK3m7ZPbOIjtFAObSK1tAm8tAeOkSnqIKqiKJbdI8e0ZNz57w4r87boHXMGc6soBE5H9+j0KaO</latexit>

✓n k

◆

= n!

k!(n k)!

<latexit sha1_base64="Co0x7p0d+4TZhIuPymE/dxJ3jX0=">AAACL3icbVC7SgNBFJ31bXxFLW0GRVDEsGuhNoJooWUEE4VsEmYnN2bY2ZllZlayLPsDdlZ+hx9gq7WV2Iid+BPiJLHwdeDCmXPu5c49QcyZNq777AwNj4yOjU9MFqamZ2bnivMLVS0TRaFCJZfqPCAaOBNQMcxwOI8VkCjgcBaEhz3/7BKUZlKcmjSGekQuBGszSoyVmkVvrbuRrjcE3sO+TqJmFu65uX1mAvu0I6UGHOIcdxshThuZ2AzzZnHFLbl94L/E+yIr+0dXhx/+9WO5WXzzW5ImEQhDOdG65rmxqWdEGUY55AU/0RATGpILqFkqSAS6nvVPy/GqVVq4LZUtYXBf/T6RkUjrNApsZ0RMR//2euJ/Xi0x7d16xkScGBB0sKidcGwk7uWEW0wBNTy1hFDF7F8x7RBFqLFp/tgSa04MdPOCTcb7ncNfUt0qedsl98RGdIAGmEBLaBmtIQ/toH10jMqogii6QXfoHj04t86T8+K8DlqHnK+ZRfQDzvsn0Ymsgg==</latexit>

(x + y)

ⁿ

=

Â

n k=0

✓n k

◆ x

^k

y

^{n k}

<latexit sha1_base64="cw3d3TL9MNXhy4eOCZEvf836XTE=">AAACeXicbVFNSxtBGJ7dWrWxarRHL6MiiGLYjdB6EaQe7DGFxgSyMcxO3pghszPLzLtiWPYP9OZP89hjT/4IoXQ2ySGJvjDwPM/7yTNxKoXFIPjj+R9WPq6urX+qbHze3Nqu7uzeWp0ZDk2upTbtmFmQQkETBUpopwZYEktoxaPrMt96AGOFVr9wnEI3YfdKDARn6KReNY9slvTy0WVQ3CmaKxrxodYW6IgW9HJeCAp6Os/DJV4vedTXaBd1dbZcqcrJ9Tu3/TCoBZOgb0E4A4dXN7+v/0VPz41e9cXN51kCCrlk1nbCIMVuzgwKLqGoRJmFlPERu4eOg4olYLv5xKSCHjmlTwfauKeQTtT5jpwl1o6T2FUmDId2OVeK7+U6GQ4uurlQaYag+HTRIJMUNS0dp31hgKMcO8C4Ee5WyofMMI7uXxa2pFYyhMei4pwJl314C27rtfBrLfjpLPpOprFO9sgBOSYh+UauyA/SIE3CyV9vzat6O96rv+8f+yfTUt+b9XwhC+Gf/wefjr/i</latexit>

Â

n k=0

✓n k

◆

= ✓n 0

◆

+✓n 1

◆

+✓n 2

◆

+··· +✓ n n 1

◆

+✓n n

◆

= 2ⁿ

(13)

Coefficiente binomiale

§

Osserviamo che per 0 < k < n vale la seguente identità:

Dimostrazione:

§

Sfruttando questa relazione si può costruire uno «schema tabulare» per semplificare il calcolo del coefficiente binomiale: il Triangolo di Tartaglia (o Triangolo di Pascal, per i francesi)

<latexit sha1_base64="o7O4kuVvabtMYvFjkodNbxZATbs=">AAACMXicbZDLSgMxFIYz9VbrrepShGARBGmdUVA3QtGNG6GCrUJbSiY9bUMzyZBkxDLMg/gcPoBL9RG6EzcufAnTC2irPwR+vnMO5+T3Q860cd2+k5qZnZtfSC9mlpZXVtey6xsVLSNFoUwll+rOJxo4E1A2zHC4CxWQwOdw63cvBvXbe1CaSXFjeiHUA9IWrMUoMRY1skexwDXakVID7ib4DMci7/2QvJfg/SmWNLI5t+AOhf8ab2xyxQP3qrzdeSk1sp+1pqRRAMJQTrSuem5o6jFRhlEOSaYWaQgJ7ZI2VK0VJABdj4efS/CuJU3ckso+YfCQ/p6ISaB1L/BtZ0BMR0/XBvC/WjUyrdN6zEQYGRB0tKgVcWwkHiSFm0wBNbxnDaGK2Vsx7RBFqLF5TmwJNScGHpKMTcabzuGvqRwWvOOCe+3liudopDTaQjtoD3noBBXRJSqhMqLoET2jV/TmPDl95935GLWmnPHMJpqQ8/UN61qq+g==</latexit>

nk

=

^{n 1}_{k 1}

+

^{n 1}_k

(14)

Coefficiente binomiale

§

Triangolo di Tartaglia: schema tabulare ricorsivo per la costruzione dei coeﬃcienO binomiali

§

Per n = 0 e k = 0 risulta

§

Per n = 1, 2, ... e per k = 0, 1, ..., n:

§

In questo modo si può costruire uno schema triangolare con cui diventa banale calcolare il coeﬃciente binomiale degli elemenO di una riga, uOlizzando i termini calcolaO nella riga precedente

<latexit sha1_base64="0w97K5DaWJpmQHEzF3x7BPU1NgA=">AAACH3icbVC7TgJBFJ31ifhCLW1GiYk2ZNdCbUyINpaYyCMBQmaHC0yYndnMzBpxQ21pa2tjZ6ufYGds+QJ/w1kgRsCTTHLuOffm3jl+yJk2rjtw5uYXFpeWUyvp1bX1jc3M1nZJy0hRKFLJpar4RANnAoqGGQ6VUAEJfA5lv3uZ+OVbUJpJcWN6IdQD0hasxSgxVmpk9mKBa7QjpQbc7eNzHLu/tZvUXiOTdXPuEHiWeGOSzR893oepl6dCI/Nda0oaBSAM5UTrqueGph4TZRjl0E/XIg0hoV3ShqqlggSg6/HwK318YJUmbkllnzB4qP6diEmgdS/wbWdATEdPe4n4n1eNTOusHjMRRgYEHS1qRRwbiZNccJMpoIb3LCFUMXsrph2iCDU2vYktoebEwF0/bZPxpnOYJaXjnHeSc6+9bP4CjZBCu2gfHSIPnaI8ukIFVEQUPaBX9IbenWfnw/l0vkatc854ZgdNwBn8ADxjpKM=</latexit>

nk

=

⁰₀

=

<latexit sha1_base64="va8IjL+UJx677kzA8ohb2y3kYAM=">AAACrnicbVFNaxsxENVu0ybdfjkt9JLL0NBSKDHaHtIebEhaEnJMoHYC3sVo5bEtVistkrbELPufCrn3f/TQc/9GZTsJtd0BwdN78zTDU1ZKYR2lv4LwwdbDR9s7j6MnT589f9Hafdm3ujIce1xLba4yZlEKhT0nnMSr0iArMomXWf51rl9+R2OFVt/crMS0YBMlxoIz56lh60etIOFTrS1C3kA3SjKcCFVz/6ZtolodxPc6beAdJEWmr2vw1wZy6AJNktWu/CBu4AOscutOCh3v7oBad2/O6KooQTW622jY2qdtuijYBPEt2D86pje/d3+q82HrTzLSvCpQOS6ZtYOYli6tmXGCS2yipLJYMp6zCQ48VKxAm9aLZBt465kRjLXxRzlYsP86alZYOysy31kwN7Xr2pz8nzao3PhzWgtVVg4VXw4aVxKchvk3wUgY5E7OPGDcCL8r8CkzjDv/mStTSiuZw+tFMvF6Dpug/7EdH7bphY/oC1nWDtkjb8h7EpNP5IickXPSIzx4HXSCk+A0pGE/TMPhsjUMbj2vyEqF078jKM+s</latexit>

1

✓n k

◆

= 8>

<

>:

n 10 se k = 0

n 1k 1 + ^{n 1}_k se 0 < k < n

n 10 se k = n

Niccolò Tartaglia (1499 – 1557)

(15)

Coefficiente binomiale

§

Per n = 0 e k = 0 risulta

§

Per n = 1, 2, ... e per k = 0, 1, ..., n:

<latexit sha1_base64="0w97K5DaWJpmQHEzF3x7BPU1NgA=">AAACH3icbVC7TgJBFJ31ifhCLW1GiYk2ZNdCbUyINpaYyCMBQmaHC0yYndnMzBpxQ21pa2tjZ6ufYGds+QJ/w1kgRsCTTHLuOffm3jl+yJk2rjtw5uYXFpeWUyvp1bX1jc3M1nZJy0hRKFLJpar4RANnAoqGGQ6VUAEJfA5lv3uZ+OVbUJpJcWN6IdQD0hasxSgxVmpk9mKBa7QjpQbc7eNzHLu/tZvUXiOTdXPuEHiWeGOSzR893oepl6dCI/Nda0oaBSAM5UTrqueGph4TZRjl0E/XIg0hoV3ShqqlggSg6/HwK318YJUmbkllnzB4qP6diEmgdS/wbWdATEdPe4n4n1eNTOusHjMRRgYEHS1qRRwbiZNccJMpoIb3LCFUMXsrph2iCDU2vYktoebEwF0/bZPxpnOYJaXjnHeSc6+9bP4CjZBCu2gfHSIPnaI8ukIFVEQUPaBX9IbenWfnw/l0vkatc854ZgdNwBn8ADxjpKM=</latexit>

nk

=

⁰₀

= 1

<latexit sha1_base64="va8IjL+UJx677kzA8ohb2y3kYAM=">AAACrnicbVFNaxsxENVu0ybdfjkt9JLL0NBSKDHaHtIebEhaEnJMoHYC3sVo5bEtVistkrbELPufCrn3f/TQc/9GZTsJtd0BwdN78zTDU1ZKYR2lv4LwwdbDR9s7j6MnT589f9Hafdm3ujIce1xLba4yZlEKhT0nnMSr0iArMomXWf51rl9+R2OFVt/crMS0YBMlxoIz56lh60etIOFTrS1C3kA3SjKcCFVz/6ZtolodxPc6beAdJEWmr2vw1wZy6AJNktWu/CBu4AOscutOCh3v7oBad2/O6KooQTW622jY2qdtuijYBPEt2D86pje/d3+q82HrTzLSvCpQOS6ZtYOYli6tmXGCS2yipLJYMp6zCQ48VKxAm9aLZBt465kRjLXxRzlYsP86alZYOysy31kwN7Xr2pz8nzao3PhzWgtVVg4VXw4aVxKchvk3wUgY5E7OPGDcCL8r8CkzjDv/mStTSiuZw+tFMvF6Dpug/7EdH7bphY/oC1nWDtkjb8h7EpNP5IickXPSIzx4HXSCk+A0pGE/TMPhsjUMbj2vyEqF078jKM+s</latexit>

✓n k

◆

= 8>

<

>:

n 10 se k = 0

n 1k 1 + ^{n 1}_k se 0 < k < n

n 10 se k = n

(16)

Combinatoria su insiemi finiti

Consideriamo un insieme A = {a₁, a₂, ..., a_n} con n elementi (|A| = n)

Operazione combinatoria Cardinalità Descrizione

insieme delle parti di A 2ⁿ tutti i sottoinsiemi di A, di qualsiasi cardinalità

permutazioni di A n! tutte le n-ple (sequenze di n elementi) distinte, formate utilizzando tutti gli elementi di A, senza ripeterli

disposizioni semplici di k

elementi di A tu8e le k-ple (sequenze di k elemen9) dis9nte, formate usando

solo k elemen9 di A, senza ripeterli disposizioni con ripetizione di k

elementi di A n^k tutte le k-ple (sequenze di k elementi) distinte, formate usando solo k elementi di A, anche ripetuti più volte

combinazioni semplici con k

elementi di A tu> i so+oinsiemi di A con soli k elemen9

<latexit sha1_base64="DEoMw1a759l72zQ//3THTavm3Fw=">AAACD3icbZA7TsNAEIbXPEN4OSDR0DgEpFAQ2RRAGUFDGSTykJIoWm/WySrrtbU7BiLLh6CHFo5AgxAtR+AE0HEFNo+CJPzSSL/+mdGMPjfkTIFtfxpz8wuLS8uplfTq2vrGppnZqqggkoSWScADWXOxopwJWgYGnNZCSbHvclp1exeDfvWGSsUCcQ39kDZ93BHMYwSDjlpmpuFJTGKRTeK8OOodZpOWmbML9lDWrHHGJlcs/ny/7jzsl1rmV6MdkMinAgjHStUdO4RmjCUwwmmSbkSKhpj0cIfWtRXYp6oZD19PrAOdtC0vkLoEWMP070aMfaX6vqsnfQxdNd0bhP/16hF4Z82YiTACKsjokBdxCwJrwMFqM0kJ8L42mEimf7VIF2sWoGlNXAkVx0DvkrQm40xzmDWV44JzUrCvNKJzNFIK7aI9lEcOOkVFdIlKqIwIukWP6Ak9G/fGi/FmvI9G54zxzjaakPHxCxgqoCQ=</latexit>

n!

(n k)!

<latexit sha1_base64="eB7MYqunM77yXFelr0zffWWatqQ=">AAACEXicbZDLSsNAFIYn9VbrLVpw42ZqFerCkrhQl0U3LivYC7ShTKaTduhkEmYmYgh5CreCW30EwYW49Ql8At35Ck4vC9v6w4Gf/5zDOXxuyKhUlvVpZBYWl5ZXsqu5tfWNzS1ze6cug0hgUsMBC0TTRZIwyklNUcVIMxQE+S4jDXdwOew3bomQNOA3Kg6J46Mepx7FSOmoY+bbnkA44YU0GRRK/HhwVEg7ZtEqWyPBeWNPTLFS+fl+3X04qHbMr3Y3wJFPuMIMSdmyrVA5CRKKYkbSXDuSJER4gHqkpS1HPpFOMno+hYc66UIvELq4gqP070aCfClj39WTPlJ9Odsbhv/1WpHyzp2E8jBShOPxIS9iUAVwSAJ2qSBYsVgbhAXVv0LcR5qG0rymroSSIUXu0pwmY89ymDf1k7J9WrauNaILMFYW7IF9UAI2OAMVcAWqoAYwiMEjeALPxr3xYrwZ7+PRjDHZyYMpGR+/ToqgxA==</latexit>

n!

k!(n k)!

(17)

Quadrati Latini

§

Un Quadrato Latino di ordine n è una matrice quadrata di n righe ed n colonne, i cui elementi

appartengono all’insieme {1, 2, ..., n} e su cui non si ripetono mai due elementi uguali su nessuna riga e nessuna colonna

•

Es.: Quadrato Latino di ordine 4

§

Due quadrati latini di ordine n si dicono ortogonali se le n² coppie formate dagli elementi corrispondenti dei due quadrati sono tutte distinte

§

Un quadrato latino normalizzato è ottenuto ponendo la prima riga e la prima colonna uguali alla sequenza (1, 2, ..., n)

1 2 3 4

2 3 4 1

4 1 2 3

3 4 1 2

(18)

Quadrati Latini

§

Calcolare il numero di quadrati latini di ordine n è molto difficile: il risultato è noto solo per quadrati latini di ordine minore di 16

§

In generale esiste una relazione che lega il numero di quadrati latini di ordine n, N(n,n), con il numero di quadrati latini normalizzati dello stesso ordine, L(n,n):

N(n,n) = n! (n−1)! L(n,n)

§

Il problema del calcolo del numero di quadrati latini differenti di ordine n, si riduce al calcolo del numero di quadrati latini normalizzati

§

Purtroppo non esiste una formula in grado di calcolare direttamente quel numero: al momento tale

risultato, calcolato con algoritmi esaustivi (i cosiddetti metodi «a forza bruta», che si limitano a costruire e contare tutte le possibili configurazioni)

•

Es.: L(2, 2) = 1, L(3, 3) = 1, L(4, 4) = 4, L(7, 7) = 16.942.080, L(9, 9) = 377.597.570.964.258.816

(19)

Il gioco del Sudoku

§

Il gioco del Sudoku è un rompicapo giapponese che sta riscuotendo un successo notevole nel cosiddetto

«grande pubblico»

§

Il problema da risolvere in una partita di Sudoku può essere riassunto nei seguenti termini: riempire una griglia di 9 × 9 elementi, in modo tale che ogni riga, ogni colonna ed ognuna delle nove sotto-griglie 3×3 contenga le cifre da 1 a 9.

§

La matrice è dunque un Quadrato Latino di ordine 9; al problema di determinare un quadrato latino, viene aggiunto il vincolo dell’obbligo di utilizzare tutti gli elementi dell’insieme {1, 2, ..., 9} nelle 9 sotto-matrici di quadrate di ordine 3

§

Per obbligare il giocatore a produrre ad ogni partita del gioco un quadrato latino differente, il gioco inizia con una matrice di 9 × 9 elementi in cui alcune delle posizioni sono preimpostate con dei valori

(20)

Il gioco del Sudoku

§

Esempio:

2 5 9 1 3

6 3 2 4 5

4

5 1 4 8

2 7

5 4 3 2 1

8 7 6 5

8 7 2 5 4 9 1 6 3

9 5 4 3 6 1 2 7 8

6 3 1 8 2 7 9 4 5

4 8 3 2 7 5 6 1 9

7 6 5 1 9 4 8 3 2

2 1 9 6 8 3 4 5 7

5 4 6 9 3 8 7 2 1

1 9 7 4 5 2 3 8 6

3 2 8 7 1 6 5 9 4

(21)

Il gioco del Sudoku: il numero di configurazioni

§

Quante diverse configurazioni è possibile costruire per il gioco del Sudoku?

§

Si deve osservare che due matrici diverse, M e M’ possono rappresentare la stessa configurazione nel caso in cui esista un isomorfismo 𝜑: M ⟶ M’ tale che 𝜑(m_i,j) = 𝜑(m_h,k) se e solo se m_i,j = m_h,k

§

Es.: 𝜑(1) = 8, 𝜑(2) = 7, 𝜑(3) = 2, 𝜑(4) = 5, 𝜑(5) = 4, 𝜑(6) = 9, 𝜑(7) = 1, 𝜑(8) = 6, 𝜑(9) = 3

§

Altre configurazioni equivalenti possono essere ottenute per rotazione della matrice o per simmetria

1 2 3 4 5 6 7 8 9

6 4 5 9 8 7 3 2 1

8 9 7 1 3 2 6 5 4

5 1 9 3 2 4 8 7 6

2 8 4 7 6 5 1 9 3

3 7 6 8 1 9 5 4 2

4 5 8 6 9 1 2 3 7

7 6 2 5 4 3 9 1 8

9 3 1 2 7 8 4 6 5

8 7 2 5 4 9 1 6 3

9 5 4 3 6 1 2 7 8

6 3 1 8 2 7 9 4 5

4 8 3 2 7 5 6 1 9

7 6 5 1 9 4 8 3 2

2 1 9 6 8 3 4 5 7

5 4 6 9 3 8 7 2 1

1 9 7 4 5 2 3 8 6

3 2 8 7 1 6 5 9 4

M M’ = 𝜑(M)

(22)

Il gioco del Sudoku: il numero di configurazioni

§

Teorema (Felgenhuer e Jarvis, 2005). Il numero di conﬁgurazioni valide del Sudoku è pari a 2⁷ × 27.704.267.971 = 3.546.146.300.288

§

È sorprendente notare che il fabore 27.704.267.971 è un numero primo

(23)

Il gioco del Sudoku: un algoritmo ricorsivo

§

Algoritmo ricorsivo per il calcolo della soluzione del Sudoku, a parOre da una conﬁgurazione valida (ma incompleta) M

§

Indichiamo con m_i,j = 0 i valori non deﬁniO della conﬁgurazione rappresentata dalla matrice M

§

La funzione ricorsiva SudokuSolve(M) resOtuisce 1 (true) se la conﬁgurazione M è compaObile, altrimenO resOtuisce 0 (false)

§

Al termine della catena di chiamate ricorsive, quando tuQ i valori della matrice sono staO assegnaO in modo compaObile con le regole, la funzione stampa la matrice M che rappresenta la conﬁgurazione ﬁnale che risolve la parOta

(24)

Riferimenti bibliografici

§

Cormen, Leiserson, Rivest, Stein, «Introduzione agli algoritmi e stru:ure da;», terza edizione, McGraw- Hill (Appendice C.1)

§

Marco Liverani, Dispense del Corso di O?mizzazione Combinatoria: Insiemi ed elemen; di calcolo combinatorio (hbp://www.mat.uniroma3.it/users/liverani/doc/disp_oc_02.pdf)