Combinatoria

Con il termine combinatoria o combinatorica (che comprende anche la geometria combinatoria) si intende il settore della matematica che studia come contare gli elementi degli insiemi finiti, come mezzo per ottenere altro o come fine, e più in generale studia le proprietà di insiemi finiti di "oggetti semplici" (per esempio interi, stringhe, nodi e collegamenti, punti e linee, configurazioni discrete).

Storia

Problemi combinatori sono stati studiati fin dall'antichità, ma la combinatoria come area consistente della matematica è stata riconosciuta solo nell'ultimo cinquantennio. Un primo testo che ha dato peso alla combinatoria è dovuto a Netto. La combinatoria ha raggiunto una certa autonomia dopo la pubblicazione del testo Combinatory Analysis di Percy Alexander MacMahon nel 1915. La sua importanza è cresciuta gradualmente negli anni successivi: sono da ricordare i testi di König sulla teoria dei grafi e di Marshall Hall.

Il suo sviluppo ha ricevuto impulso dall'opera di Gian-Carlo Rota, che a partire dagli anni 1960, ha contribuito alla fondazione di teorie unificatrici di ampia portata e di grande chiarezza formale. Un'altra figura influente è stata quella di Marcel-Paul Schützenberger. Un'azione diversa ma molto efficace si deve a Paul Erdős e alla sua capacità di porre e risolvere problemi, i suoi contributi riguardano soprattutto problemi estremali.

Descrizione generale

Un aspetto di primaria importanza in questi studi riguarda l'enumerazione delle configurazioni: per alcuni esempi di questa problematica si vedano ad esempio fattoriale, coefficiente binomiale, numeri di Catalan e la successione di Fibonacci. Un altro aspetto fondamentale della combinatoria è quello algoritmico: innanzi tutto la conoscenza delle caratteristiche combinatorie di un tipo di configurazioni è essenziale per individuare i meccanismi che consentano di manipolarle; inoltre ogni algoritmo può essere oggetto di indagini combinatorie, come quelle di natura enumerativa richieste per valutare la sua efficienza (v. complessità degli algoritmi). Lo schema di classificazione MSC2000 per i documenti della ricerca matematica dedica esplicitamente la sezione di primo livello caratterizzata dalla sigla 05-XX. È utile segnalare le sezioni di secondo livello della combinatoria, insieme alla relativa sigla e al numero delle sezioni di terzo livello loro attribuite:

• 05Axx Combinatoria enumerativa (11)
• 05Bxx Disegni e configurazioni (12)
• 05Cxx Teoria dei grafi (38)
• 05Dxx Combinatoria estremale (5)
• 05Exx Combinatoria algebrica (8)

Si trovano però problemi di natura combinatoria in moltissimi settori della matematica: nella teoria degli insiemi, nelle teorie delle strutture algebriche con assiomi deboli, nella teoria dei campi, nella teoria dei gruppi, nella geometria proiettiva, nelle geometrie finite, nello studio delle configurazioni geometriche convesse, nello studio dei politopi e dei poliedri, nello studio delle funzioni speciali, nello studio dei sistemi dinamici, nella teoria della probabilità, nella teoria della ottimizzazione, nella teoria dei giochi. Una considerazione particolare merita il collegamento fra combinatoria e studio degli algoritmi cui si è già accennato e per il quale vanno ricordati anche i metodi per il calcolo simbolico automatico e la computer algebra. I collegamenti fra la combinatoria e ciascuna delle aree suddette sono stretti e articolati: le relazioni di dipendenza non forniscono buoni chiarimenti, ma risulta invece più opportuno considerare gli stimoli e gli aiuti reciproci che si sviluppano tra queste aree.

Anche quando si esce dalla matematica per scorrere le discipline scientifiche, tecnologiche ed umanistiche si incontra una varietà di problematiche combinatorie. Per queste è necessario un elenco anche più esteso dei precedenti:

• Teorie quantistiche e fisica delle particelle elementari,
• Meccanica statistica e fisica della materia,
• Chimica molecolare (in particolare dei polimeri),
• Chimica combinatoria,
• Biologia molecolare,
• Ingegneria strutturale,
• Telecomunicazione, codici autocorrettori e crittologia,
• Ingegneria del software e metrica del software,
• Ricerca operativa, ottimizzazione e pianificazione,
• Modelli per l'economia e l'organizzazione aziendale,
• Problemi di trasporto e di logistica,
• Biblioteconomia,
• Lessicografia e linguistica,
• antropologia e archeologia.

Terminologia

Taluni, invece del sostantivo combinatoria preferiscono usare il sostantivo combinatorica; mentre combinatoria si avvicina ai termini più usati in francese (combinatoire), spagnolo (combinatoria), combinatorica si avvicina alla combinatorics dell'inglese, alla Kombinatorik del tedesco e ai termini vicini a quest'ultimo di tante altre lingue influenzate dal tedesco (v. Wiktionary); inoltre combinatorica si avvicina a sostantivi come elettronica e informatica e molti cultori del settore ritengono che la combinatorica sia da considerare una disciplina che avrà sulla società un impatto paragonabile a quello delle altre due citate. Per i corrispondenti aggettivi, invece, prevalgono decisamente combinatorio e le sue flessioni.

Per gli aspetti matematici di questo settore si usa anche il termine teoria combinatoria, per sottolineare la disponibilità di un apparato teorico in grado di presentare in modo unificato i molteplici problemi di natura combinatoria ed i metodi di portata generale in grado di affrontare tali problemi. Altri viceversa preferiscono usare il termine teorie combinatorie per sottolineare il fatto che le diverse teorie disponibili, pur essendo in grado di inquadrare ampie gamme di problemi, sono comunque rivolte a tematiche circoscritte: algebra di incidenza, teoria delle matroidi, calcolo umbrale, funzioni generatrici, teorie estremali, ....

Un termine simile ma differente è matematica discreta, termine usato soprattutto in contrapposizione a matematica del continuo. Con il termine combinatoria, invece, questa contrapposizione non viene sottolineata, in accordo con il fatto che nello studio delle funzioni speciali i metodi combinatori (in particolare quelli relativi alle funzioni generatrici) e i metodi del continuo sono utilizzati complementarmente.

Un termine analogo ampiamente usato è calcolo combinatorio; esso compare soprattutto nei capitoli iniziali dei testi di calcolo infinitesimale e delle introduzioni alla probabilità e alla statistica e riguarda una cerchia ristretta di argomenti (disposizioni, combinazioni, permutazioni, coefficienti binomiali e pochi altri) considerati solo come preliminari degli sviluppi formali successivi. Questo calcolo combinatorio viene collocato in posizione ancillare rispetto al calcolo infinitesimale e al calcolo delle probabilità, ma questa ancillarità viene oggi recisamente rifiutata dai cultori della combinatoria. Molti di loro affermano invece la essenzialità di molti sviluppi della loro area, una sua raggiunta autonomia e anche una certa primarietà delle sue problematiche.

Un termine che si colloca in posizione intermedia fra calcolo combinatorio e combinatoria è analisi combinatoria.

Esempi

Esempi di collezioni di oggetti studiate nell'ambito della combinatoria sono:

• le permutazioni di $n$ oggetti;
• le combinazioni con ripetizione di 5 dei primi 7 interi;
• i grafi poliedrali;
• i quadrati magici e i quadrati latini.

La combinatoria si propone di studiare sul piano matematico le situazioni pratiche ed i relativi problemi i cui aspetti essenziali si possono esprimere con modelli discreti. Alcuni esempi di queste situazioni sono:

• le disposizioni delle persone intorno ad un tavolo circolare;
• le estrazioni di palline di colori diversi da un'urna;
• le disposizioni dei pezzi del gioco degli scacchi su una scacchiera.

Bibliografia

Introduzioni

• (EN) Martin Aigner, Combinatorial theory, Berlino, Springer, ISBN 3-540-61787-6.
• (EN) Ronald Graham, Donald Knuth e Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1989, ISBN 0-201-14236-8.
• (EN) Norman L. Biggs, Discrete mathematics, 2ª ed., Oxford Clarendon Press, 2002, ISBN 0-19-850717-8.
• (EN) J. H. Van Lint e Robin Wilson, A Course in Combinatorics, 2ª ed., Cambridge University Press, 2001, ISBN 978-05-21-00601-9.
• (EN) George E. Martin, Counting: The Art of Enumerative Combinatorics, Berlino, Springer, 2001, ISBN 978-03-87-95225-3.

Manuali

• (EN) Ronald Graham, Martin Grötschel e László Lovász, Handbook of Combinatorics, Vol. I, Elsevier, 1996, ISBN 0-444-82346-8.
• (EN) Ronald Graham, Martin Grötschel e László Lovász, Handbook of Combinatorics, Vol. II, Elsevier, 1996, ISBN 0-444-82351-4.
• (EN) Charles J. Colburn e Jeffey H. Dinitz, The CRC handbook of Combinatorial Designs, CRC Press, 1996, ISBN 0-8493-8948-8.
• (EN) Richard P. Stanley, Enumerative Combinatorics, Volumes 1 and 2, Cambridge, Cambridge University Press, 1997, ISBN 978-14-61-59765-0. Enumerative Combinatorics, Volumes 1 and 2

Problemi classici

• (EN) George E. Andrews, The Theory of Partitions, Cambridge, Cambridge University Press, 2008, ISBN 978-05-21-63766-4.

Teoria dei grafi

• (EN) Krishnaiyan Thulasiraman e M. N. S. Swamy, Graphs: Theory and Algorithms, J.Wiley, 1992, ISBN 978-81-26-54958-0.
• (EN) Béla Bollobás, Modern Graph Theory, Berlino, Springer, 1998, ISBN 0-387-98488-7.
• (EN) Lowell W. Beineke, Robin J. Wilson e Peter J. Cameron, Topics in Algebraic Graph Theory, Cambridge, Cambridge University Press, 2004, ISBN 978-05-21-80197-3.
• (EN) D. Cvetković, P. Rowlison e S. Simic', Eigenspaces of Graphs, Cambridge, Cambridge University Press, 1997, ISBN 978-05-21-57352-8.

Combinatoria algebrica

• (EN) Steve Roman, Umbral calculus, Academic Press, 1984, ISBN 0-12-594380-6.
• (EN) Herbert Wilf, Generatingfunctionology, 2ª ed., Academic Press, 1994, ISBN 0-12-751956-4.
• (EN) Marko Petrovsek, Herbert Wilf e Doron Zeilberger, A=B, A. K. Peters, 1996, ISBN 978-15-68-81063-8.
• (EN) Richard P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge, Cambridge University Press, 1996, ISBN 0-521-55309-1. Companion site dei due volumi
• (EN) Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge, Cambridge University Press, 1999, ISBN 0-521-56069-1.
• (EN) François Bergeron, Gilbert Labelle e Pierre Leroux, Combinatorial species and tree-like structures, Cambridge, Cambridge University Press, 1998, ISBN 0-521-57323-8.
• (EN) Henry Crapo e Domenico Senato, Algebraic combinatorics and Computer Science - A tribute to Gian-Carlo Rota, Berlino, Springer, 2001, ISBN 88-470-0078-5.
• (EN) Miklos Bona, Combinatorics of permutations, Chapman-Hall / CRC Press, 2004, ISBN 978-15-84-88434-7.
• (EN) Anders Björner e Francesco Brenti, Combinatorics of Coxeter Groups, Berlino, Springer, 2005, ISBN 3-540-44238-3.

Matroidi

• (EN) Neil White, Theory of matroids, Cambridge, Cambridge University Press, 2009, ISBN 978-05-21-09202-9.
• (EN) Neil White, Matroid applications, Cambridge, Cambridge University Press, 2009, ISBN 978-05-21-11967-2.
• (EN) James G. Oxley, Matroid Theory, Oxford, Oxford University Press, 1992, ISBN 0-19-853563-5.
• (EN) Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White e Günter M.Ziegler, Oriented matroids, Cambridge, Cambridge University Press, 2008, ISBN 978-05-21-77750-6.
• (EN) Bruno Korte, László Lovász e R. Schrader, Greedoids, Berlino, Springer, 1991, ISBN 978-3-642-58191-5.

Disegni combinatori

• (EN) Thomas Beth, Dieter Jungnickel e Hanfried Lenz, Design Theory Vol. 1, 2ª ed., Cambridge, Cambridge University Press, 1999, ISBN 0-521-44432-2.
• (EN) Thomas Beth, Dieter Jungnickel e Hanfried Lenz, Design Theory Vol. 2, 2ª ed., Cambridge, Cambridge University Press, 1999, ISBN 0-521-77231-1.

Combinatoria estremale

• (EN) Ronald Graham, B. Rothschild e J. H. Spencer, Ramsey Theory, 2ª ed., J.Wiley, 2013, ISBN 978-11-18-79966-6.
• (EN) B. S. Stechkin e V. I. Baranov, Extremal Combinatorial Problems and their Applications, New York, Sperling-Verlag, 1995, ISBN 978-94-01-74122-4.

Combinatoria delle parole

• (EN) M. Lothaire, Combinatorics on Words, 2ª ed., Cambridge, Cambridge University Press, 2008, ISBN 978-05-21-59924-5.
• (EN) M. Lothaire, Algebraic combinatorics on Words, Cambridge, Cambridge University Press, 2002, ISBN 978-05-21-81220-7.
• (EN) M. Lothaire, Applied combinatorics on Words, Cambridge, Cambridge University Press, 2005, ISBN 978-05-21-84802-2.

Combinatoria analitica

• (EN) Philip Flajolet e Robert Sedgewick, Analytic Combinatorics, Cambridge, Cambridge University Press, 2009, ISBN 978-05-21-89806-5.

Voci correlate

• Calcolo combinatorio
• 05-XX sigla della sezione della MSC dedicata alla combinatoria.
• Glossario di combinatoria
• Principio di inclusione-esclusione

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «combinatoria»
• Wikimedia Commons contiene immagini o altri file sulla combinatoria

Collegamenti esterni

• combinatòria, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• (EN) Raj C. Bose e Branko Grünbaum, combinatorics, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Combinatorics, su MathWorld, Wolfram Research.
• Appunti di geometria combinatoria (PDF) , su setticarraro.edu.it.