COMBINATORIA, ANALISI

COMBINATORIA, ANALISI (X, p. 912)

Lo scopo principale dell'a. c. consiste nello studio di raggruppamenti di elementi in insiemi. Di norma, si ha soltanto un numero finito di elementi e i raggruppamenti debbono soddisfare condizioni particolari imposte dal problema. I problemi che s'incontrano sono di due tipi. Uno, il più classico, consiste nel contare il numero di raggruppamenti in questione, sia attraverso formule esplicite esatte sia mediante formule approssimate. Il secondo problema, rivelatosi d'importanza fondamentale nelle applicazioni, è centrato sulle questioni di esistenza e costruzione di raggruppamenti aventi proprietà assegnate.

Sebbene in un certo senso il secondo problema sia un caso particolare del primo, in pratica esso viene trattato separatamente. Infatti, quando il problema dell'enumerazione delle soluzioni risulta matematicamente trattabile, il problema dell'esistenza di una soluzione è in generale assai semplice. Tuttavia, in molti casi, il problema dell'esistenza di soluzioni è già estremamente difficile e quello dell'enumerazione delle soluzioni stesse risulta essere al di fuori della portata delle tecniche attuali. Questo fa sì che i problemi di esistenza presentino caratteristiche notevolmente diverse dai problemi di enumerazione.

Al giorno d'oggi, l'importanza pratica dell'a. c. è notevole: nella statistica, specialmente nell'analisi dei dati di esperimenti, nella teoria delle comunicazioni e dell'informazione, nella programmazione degli elaboratori elettronici. L'importanza teorica dei metodi di a. c. in svariati rami della matematica è andata sempre più crescendo, in particolare in algebra e teoria dei numeri, topologia algebrica e geometria.

Alcuni interessanti e molteplici aspetti della a. c. moderna si possono illustrare attraverso i seguenti esempi: il principio di esclusione, il principio di Dirichlet e il teorema di Ramsey, la teoria delle identità combinatorie, la teoria dei disegni combinatori con i suoi casi particolari: i quadrati latini, le matrici di Hadamard, i piani proiettivi finiti.

1. - Principio di esclusione. Sia S un n-insieme, cioè un insieme di n oggetti, e siano P₁, P₂, ..., P_N, N proprietà connesse con gli elementi di S. Indichiamo con S(P_i1, P_i2, ..., P_ik) il numero di elementi di S che verifichino simultaneamente le proprietà P_i1, ..., P_ik e sia S(k) = Σ S(P_i1, ..., P_ik), dove la somma è estesa a tutti i k-sottoinsiemi dell'insieme delle proprietà P₁, ..., P_N; si pone per definizione S(0) = n, il numero di elementi di S. Allora il principio di esclusione afferma che il numero E(m) di elementi di S che verificano esattamente m delle proprietà P_i è dato da

In particolare, per m = 0, il numero di elementi di S che non verificano nessuna delle proprietà P_i è dato da E(0) = S(0) − S(1) + S(2) − ... + (− 1)^N S(N). Si noti anche per che ogni m si ha S(0) − S(1) + ... − S(2m − 1) ≤ E(0) ≤ S(0) − S(1) + ... + S(2m), un'utile disuguaglianza che permette di ottenere stime superiori e inferiori per E(0) mediante somme aventi un numero non troppo elevato di termini. Questi ultima formula, detta "formula del crivello", è attribuita al matematico inglese J. J. Sylvester ma certamente era nota molto prima. Essa trova applicazioni nel calcolo delle probabilità e soprattutto in aritmetica.

Un esempio famoso in aritmetica è legato all'algoritmo di Eratostene per la determinazione dei numeri primi fino a n, una volta noti quelli fino a √n; il numero 1 non si considera numero primo. Se S consiste degl'interi 1, 2, ..., n, e se per ogni primo p ≤ √n la proprietà P_p consiste nella divisibilità per il numero primo p, vediamo subito che gli elementi di S che non soddisfano a nessuna delle proprietà P_p sono esattamente i numeri primi compresi tra √n ed n, più l'unità. Indicando perciò con π(n) il numero dei numeri primi che non superano n, il principio di esclusione dà la formula

dove [x] indica la parte intera di x, e i p_k indicano numeri primi distinti ≤ √n. La formula esatta precedente è di scarsa utilità anche dal punto di vista del calcolo numerico, in quanto essa contiene troppi termini. Formule approssimate per π(n) si possono ottenere usando le disuguaglianze di esclusione, e il matematico norvegese Viggo Brun è riuscito a dare una forma maneggevole a queste in quello che oggi è chiamato il "crivello di Viggo Brun". Le sue idee sono alla base di moderni metodi di crivello impieganti tecniche altamente sofisticate, in gran parte di natura combinatoria, che hanno permesso la risoluzione di problemi fondamentali di aritmetica.

2. - Principio di Dirichlet e teorema di Ramsey. Il principio di Dirichlet, o "dei cassetti", consiste nella semplicissima osservazione che se n oggetti vengono ripartiti in n − 1 classi, esiste certamente una classe che contiene almeno due oggetti. L'importanza logica di questa osservazione è dovuta al fatto che essa conduce direttamente all'esistenza di una classe avente una data proprietà (in questo caso, il contenere almeno due elementi), senza che vi sia un procedimento costruttivo per la determinazione di quale classe abbia la proprietà voluta. Il principio di Dirichlet trova numerose applicazioni in tutti i rami della matematica ed è di particolare importanza nei problemi di approssimazione diofantea.

Una generalizzazione molto profonda di questo semplicissimo principio si trova nel teorema di Ramsey. Sia S un n-insieme e sia P_r(S)

i cui elementi sono gli r-sottoinsiemi di S. Sia adesso P_r(S) = A₁ ⋃ A₂ ⋃ ... ⋃ A_t una partizione arbitraria ordinata di P_r(S) in t parti A_i e siano q₁, q₂, ..., q_t interi tali che 1 ≤ r 〈 q_i per ogni i. Il teorema di Ramsey afferma che esiste un intero N(q₁, ..., q_t, r), tale che se n ≥ N(q₁, q₂, ..., q_t; r) e se P_r(s) = A₁ ⋃ A₂ ⋃ ... ⋃ A_t è una partizione come in precedenza, esiste un indice i e un q_i-sottoinsieme Σ di S tale che P_r(Σ) ⊂ A_i, cioè ogni r-sottoinsieme di Σ è un elemento di A_i. Per r = 1, q₁ = ... = q_t = 2, si ha N(2, ..., 2, 1) = t + 1 ed è facile verificare che il teorema di Ramsey non è altro che il principio di Dirichlet. Le conoscenze attuali sui numeri di Ramsey N(q₁, ..., q_t; r) sono molto scarse. È noto che N(q₁, ..., q_t; 1) = q₁ + ... + q_t − t + 1, N(3, 3; 2) =6, N(3, 4; 2) = 9, N(3, 5; 2) = 14, N(4, 4; 2) = 18, N(3, 3, 3; 2) =17. Il teorema di Ramsey ha trovato applicazione in moltissimi campi, inclusa la logica matematica.

Un elegante risultato di geometria elementare che si dimostra agevolmente con l'ausilio del teorema di Ramsey è il seguente. Sia m ≥ 3, e sia n ≥ N(5, m; 4); dati nel piano n punti, di cui mai tre siano allineati, allora si possono scegliere m di questi punti come vertici di un poligono convesso a m lati.

3. - Identità combinatorie. La più semplice e antica identità c. è quella famosa del binomio di Newton:

La funzione generatrice può essere usata per ricavare direttamente le proprietà dei coefficienti. Per es., la relazione

dimostra la proprietà di simmetria

e dalla formula

si ricava la formula di ricorrenza

L'uso di funzioni generatrici è particolarmente utile nello studio delle relazioni inverse; un esempio particolarmente semplice di relazione inversa è il seguente. Se {a_n} e {b_n} sono due successioni con

per ogni n, allora

Lo studio di queste relazioni inverse si fa attraverso il calcolo simbolico di Blissard, nel quale le successioni {a_n} vengono trattate come variabili aⁿ ⊄ a_n, e

Se ora c e γ sono variabili simboliche tali che exp(xc) exp(xγ) = 1, da exp(xa) = exp(xb) exp(xc) si ricava exp(xb) = exp(xa) exp(xγ), e se

segue che

L'esempio precedente di relazione inversa è il caso particolare di exp(xc) = e^-x, exp(xγ) = e^-x, per il quale c_n = 1 e γ_n = (− 1)ⁿ.

4. - Disegni combinatori. Un quadrato latino n × n è una matrice (a_ij), i, j = 1, 2, ..., n tale che ogni riga e ogni colonna è una permutazione degl'interi 1, 2, ..., n. I quadrati latini si presentano in modo naturale in questioni teoriche: per es., la tavola di moltiplicazione di un gruppo finito di ordine n s'identifica con un quadrato latino normalizzato, cioè tale che la prima colonna e la prima riga sono nell'ordine standard 1, 2, ..., n. Il numero L_n di quadrati latini normalizzati cresce rapidamente con n: L₄ = 4, L₅ = 56, L₆ = 9408, L₇ = 16942080. Se A₁ = (a1_ij) e A₂ = (a2_ij) sono due quadrati latini n × n tali che le coppie ordinate (a1_ij, a2_ij) sono tutte distinte, essi si dicono "ortogonali" e la matrice ((a¹_ij, a²_ij)) viene chiamata un "quadrato greco-latino".

L'esistenza di quadrati greco-latini di ordine n S-110??? 2 (mod 4) si stabilisce facilmente. Eulero congetturò nel 1782 che non esistono quadrati greco-latini di ordine n ⊄ 2 (mod 4); per n = 6 ciò equivale alla non esistenza di soluzioni del "problema dei 36 ufficiali". Questo problema ricerca il modo di disporre 36 ufficiali di 6 gradi e di 6 reggimenti diversi in una formazione quadrata 6 × 6, in modo tale che ogni riga e ogni colonna contengano uno e uno solo ufficiale per ogni grado e ogni reggimento. La congettura di Eulero è vera per n = 6. Tuttavia, un teorema di Bose, Shrikande e Parker (1960) dimostra l'esistenza di quadrati grecolatini per ogni n ⊄ 2 (mod 4) e n ≥ 10. La congettura di Eulero è pertanto falsa se n > 6.

Il problema dei quadrati latini è connesso a un difficile problema di geometria, quello della costruzione dei piani proiettivi. Un piano proiettivo astratto π è un sistema matematico consistente di oggetti chiamati punti e rette, con una relazione di appartenenza tra punto e retta, tali che: (i) due punti distinti di π appartengono a una e una sola retta; (ii) due rette distinte di π determinano uno e uno solo punto; (iii) esistono almeno quattro punti di π, di cui mai tre siano allineati. Si dice allora che π è finito se contiene un numero finito di punti; le rette di π contengono allora sempre lo stesso numero n + 1 di punti e l'intero n così individuato si dice "ordine" del piano proiettivo π. Se n > 3, l'esistenza di π è equivalente a quella di n −1 quadrati latini di ordine n mutualmente ortogonali.

Uno dei maggiori problemi insoluti dell'a. c. è quello di determinare i valori di n per cui esiste un piano proiettivo di ordine n. È noto che un tale piano proiettivo esiste certamente se n = p^α è una potenza di un numero primo p, ed è nota l'unicità per n ≤ 8. Un teorema di Bruck e Ryser afferma la non esistenza di piani proiettivi di ordine n se n ⊄ 1 oppure 2 (mod 4) e se la parte libera da quadrati di n è divisibile per un primo p, p ⊄ 3 (mod 4). Il primo caso non risolto è quello in cui n = 10.

Configurazioni che generalizzano quelle dei piani proiettivi sono i "disegni combinatori", di grande importanza nella statistica e nell'analisi e progettazione di esperimenti. Una (b, v, r, k, λ)-configurazione consiste di un v-insieme X di elementi x₁, ..., x_v e k-sottoinsiemi X₁, ..., X_b, detti "blocchi", tali che ogni elemento x appartiene a esattamente r blocchi e ogni coppia x, y appartiene a esattamente λ blocchi. Dev'essere necessariamente r(k − 1) = (v − 1)λ e bk = vr. Le configurazioni per cui λ = 1, k = 3, vengono chiamate "sistemi di Steiner di ordine v"; per un sistema di Steiner,

Per v = 3, 7, 9 vi è un solo sistema di Steiner, per v = 13 ve ne sono 2 e per v =15 ve ne sono 80. Se esistono sistemi di Steiner di ordine v₁, v₂ ne esistono anche di ordine v₁v₂. Altri casi importanti sono quelli in cui b = v, r = k, che formano le (v, k, λ)-configurazioni. Esse consistono di un v-insieme X e k-sottoinsiemi X₁, X₂, ..., X_v che, a due a due, hanno in comune esattamente λ elementi. Le (n² + n + 1, n + 1, 1)-configurazioni sono esattamente i piani proiettivi di ordine n, X essendo il piano proiettivo e i blocchi X_i essendo le rette di X. Un altro caso importante è quello in cui (v, k, λ) = (4t − 1, 2t − 1, t − 1) che si verifica essere equivalente alla costruzione di una matrice di Hadamard di ordine 4t. Una matrice H di ordine n è detta di Hadamard se i suoi elementi sono soltanto + 1 oppure − 1 e se inoltre H • H* = nI, dove H* è la matrice trasposta di H e I la matrice unità. Il problema della costruzione di matrici di Hadamard per ogni n ⊄ 0 (mod 4) è tuttora non risolto, nonostante notevoli progressi siano stati fatti.

Bibl.: H. J. Ryser, Combinatorial matemathics, New York 1963; J. Riordan, Combinatorial identities, ivi 1968.