Questo glossario di combinatoria raccoglie termini e concetti relativi a questa importante branca della matematica. Per ogni voce viene fornita una brevissima definizione o spiegazione e viene citato l'articolo di Wikipedia a cui si rimanda per il trattamento completo dell'argomento.
A Algoritmo greedy
Algoritmo che cerca la soluzione migliore, dal punto di vista globale, di un problema attraverso la scelta, passo dopo passo, delle soluzioni più promettenti da un punto di vista locale
Approssimazione di Stirling Sinonimo di formula di Stirling
C Calcolo combinatorio
Chiamato anche Matematica combinatoria o semplicemente Combinatoria. Branca della matematica che studia i metodi e gli algoritmi per raggruppare e/o ordinare, secondo particolari regole e procedure, insiemi finiti di oggetti, e di contare le configurazioni risultanti
Calcolo umbrale
Notazione che permette di trattare identità su successioni numeriche considerando gli indici dei componenti come se fossero esponenti. Questo metodo, anche se privo di completi e rigorosi fondamenti, si rivela spesso efficace. Legato al coefficiente binomiale, attualmente il calcolo umbrale viene principalmente utilizzato per lo studio delle sequenze di Sheffer
Ciclo
Particolare permutazione che, presi alcuni oggetti da un insieme ordinato più ampio, sposta ognuno di essi nel posto del successivo (l'ultimo viene spostato al posto del primo), mentre lascia inalterata la posizione di tutti gli altri
Coefficiente binomiale Funzione a due variabili intere n > 0 e 0 ≤ k ≤ n , definita come
(dove n! è il fattoriale di n). Il coefficiente binomiale può essere calcolato anche col triangolo di Tartaglia. Oltre ad avere importanza nello sviluppo delle potenze dei binomi, per quanto riguarda la combinatoria il coefficiente binomiale è strettamente legato al numero delle combinazioni semplici
Coefficiente binomiale simmetrico
Variante del coefficiente binomiale a due variabili (intere e positive) simmetriche nei loro argomenti. Può essere espressa come
È una funzione capace di enumerare configurazioni discrete equivalenti di un sistema
Coefficiente multinomiale
Generalizzazione del coefficiente binomiale ad un numero qualunque di variabili intere positive.Se n è un intero positivo e con sono interi non negativi, il coefficiente multinomiale è definito come
Il coefficiente multinomiale è legato allo sviluppo delle potenze dei polinomi, e, per quanto riguarda la combinatoria, è strettamente legato al numero delle permutazioni di n oggetti di cui uguali fra loro, uguali fra loro, ecc
Combinatoria enumerativa Sinonimo di Enumerazione
Combinatoria Sinonimo di Geometria combinatoria
Combinazione Le combinazioni di n oggetti a k a k sono i modi con cui si possono raggruppare (o scegliere, o estrarre) k oggetti (con k minore di n) alla volta dagli n iniziali. In altre parole rappresentano i sottoinsiemi di cardinalità k di un insieme di cardinalità n > k. Le combinazioni si considerano diverse solo se hanno diversa composizione (cioè non conta l'ordine in cui gli oggetti sono scelti). Le combinazioni di n oggetti presi k alla volta, possono essere: se ogni elemento non può essere ripetuto; in pratica ogni oggetto che viene scelto non viene più considerato per le scelte successive. Il numero delle combinazioni semplici di n oggetti presi k a k è pari al coefficiente binomiale di n e k:
se ogni elemento può essere scelto anche più volte. Il loro numero è pari al coefficiente binomiale di (n + k – 1) e k:
Costante di Gauss-Kuzmin-Wirsing
Costante matematica utilizzata nello studio dell'efficienza dell'algoritmo di Euclide per il calcolo del massimo comun divisore. Non è noto se sia un numero razionale oppure no; vale all'incirca 0,3036630029...
D Delta di Kronecker Funzione in due variabili intere che vale 1 se i valori delle variabili coincidono, e 0 in caso contrario. Solitamente si rappresenta con δi,j; è quindi definita come:
Utilizzata per rappresentare formule che riguardano matrici o comunque insiemi di numeri espressi tramite due indici: per esempio la matrice identità si può definire come: con
Dismutazione
Una dismutazione è una permutazione in cui non resta fisso nessun elemento. Si può dimostrare che il numero di dismutazioni di n elementi è
Disposizione Le disposizioni di n oggetti a k a k sono i modi ordinati con cui si possono disporre k oggetti alla volta, scelti fra gli n iniziali; due disposizioni sono considerate differenti se hanno almeno un oggetto differente o gli stessi oggetti differiscono per l'ordine in cui sono disposti. Le disposizioni di n oggetti presi k alla volta, possono essere:
se ogni elemento non può essere ripetuto; in pratica ogni oggetto che viene scelto non viene più considerato per le scelte successive: in questo caso quindi k deve essere minore di n. In altre parole le disposizioni semplici rappresentano i sottoinsiemi ordinati di cardinalità k di un insieme di cardinalità n > k. Il numero delle disposizioni semplici di n oggetti presi k a k è pari a
se ogni elemento può essere ripetuto più volte: in questo caso k può essere maggiore di n. Il numero delle disposizioni con ripetizione di n oggetti presi k a k è pari a nk
E Enumerazione
Branca della matematica che si occupa di metodologie e tecniche per contare, in senso astratto, gli oggetti
F Fattoriale
Funzione discreta definita per i numeri interi non negativi. Se n è un intero positivo, si definisce fattoriale di n (o n fattoriale) il prodotto dei primi n numeri interi positivi. Il fattoriale di n si indica con n!. È definibile in modo ricorsivo in quanto Coerentemente con la funzione gamma di Eulero, che, in un certo senso, estende il concetto di fattoriale ai numeri complessi, si assume 0! = 1
Fattoriale doppio Sinonimo di semifattoriale
Fattoriale quadruplo
Il fattoriale quadruplo di un numero naturale n non è un multifattoriale, ma è dato dall'espressione
Fattoriale crescente Se x è un numero reale (o più genericamente un elemento di un anello), il fattoriale crescente di x con n fattori è il prodotto . Se x è un intero positivo, vale l'identità:
Fattoriale crescente di base q
Se q e x sono variabili reali o complesse ed n è un numero naturale, il fattoriale crescente di base q nella x relativo ad n è il prodotto di n fattori
Analogamente si può definire il fattoriale crescente di base q nella x relativo ad infinito con una analoga produttoria infinita di fattori
Fattoriale decrescente Se x è un numero reale (o più genericamente un elemento di un anello), il fattoriale decrescente di x con n fattori è il prodotto . Se x ed n < x sono interi positivi, vale l'identità: .
Formula di Faulhaber
Formula generale che esprime la somma delle potenze di interi successivi. Fa uso dei numeri di Bernoulli
Formula di Stirling
Formula che fornisce un valore approssinato del fattoriale di numeri grandi. In pratica afferma che
Funzione E di MacRobert
Generalizzazione della serie ipergeometrica esprimibile in termini della funzione G di Meijer, ma meno generale di quest'ultima
Funzione Gamma di Eulero
Detta anche semplicemente “funzione Gamma”, è una funzione definita in campo complesso, continua sui numeri reali positivi, che estende il concetto di fattoriale ai numeri complessi. Infatti nella funzione Gamma vale, per qualunque valore z complesso, esclusi gli interi negativi, la relazione di ricorsività , tipica del fattoriale. Per ogni numero intero non negativo n si ha per cui, per gli interi positivi, si ha
Funzione G di Meijer
Funzione definita in campo complesso. Il suo scopo è la definizione di una funzione generale che contenga come casi particolari la maggior parte delle funzioni speciali, analogamente a quanto fanno la funzione ipergeometrica e la funzione E di MacRobert. La definizione della funzione G di Meijer comporta un integrale in campo complesso
Funzione di Mertens
Funzione che associa ad ogni numero intero positivo n la somma dei valori della funzione di Möbius da 1 ad n: dove μ(k) denota la funzione di Möbius
Funzione di Möbius Funzione definita sui numeri naturali che classifica questi ultimi in base al modo in cui possono essere scomposti in fattori primi, Indicata con μ(n), è una funzione a tre valori: -1 se n è scomponibile in un numero dispari di fattori primi distinti; 0 se ha uno o più fattori primi ripetuti; +1 se n è scomponibile in un numero pari di fattori primi distinti
Funzione di partizione
Funzione che associa ad ogni numero naturale n il numero dei modi in cui n può essere scritto come somma di numeri naturali, senza tener conto dell'ordine degli addendi. Ogni sequenza di addendi che formi il numero n, ordinata in modo crescente, prende il nome di “partizione di n”
Funzione simmetrica
Una funzione a più variabili è simmetrica se è invariante rispetto a qualunque permutazione dei suoi argomenti. Manca una teoria completa sulle funzioni simmetriche non polinomiali. Un'altra definizione, non identica alla precedente, identifica una funzione simmetrica come il limite degli anelli dei polinomi simmetrici in n variabili al tendere di n all'infinito. Utile in combinatoria per studiare i rapporti tra polinomi simmetrici
G Geometria combinatoria Sinonimo di Geometria discreta
Geometria discreta
Branca della matematica che studia gli insiemi finiti o numerabili e le loro relazioni di ordine e di appartenenza
Gruppo simmetrico
Il gruppo simmetrico di un insieme è il gruppo di tutte le permutazioni dei suoi elementi
I Identità combinatoria
Applicazione alla combinatoria del concetto generale di identità matematica (uguaglianza tra due espressioni valida per tutti i valori delle variabili). In particolare le identità combinatorie riguardano l'uguaglianza della cardinalità di due insiemi
Iperfattoriale
L'iperfattoriale di un numero naturale n è il prodotto di tutti i numeri naturali inferiori o uguali ad n, ognuno elevato alla potenza pari al numero stesso:
L'iperfattoriale produce numeri molto più grandi del fattoriale (i primi valgono: 1, 4, 108, 27648)
M Matrice di Hadamard
Matrice quadrata di ordine n con tutti gli elementi uguali a +1 o -1, la cui inversa è uguale alla trasposta divisa per n. In modo equivalente si può dire, al posto dell'ultima affermazione, che le righe della matrice formano un insieme di vettori mutuamente ortogonali. Utilizzate per la realizzazione di codici per la correzione di errori e in calcoli statistici.
Matrice sparsa
Matrice in cui "quasi tutti" gli elementi sono nulli (dove "quasi tutti" dipende dal contesto)
Matroide
Struttura matematica (generalmente di cardinalità finita) a cui si possa applicare un concetto di indipendenza che sia una generalizzazione della indipendenza lineare definita per gli spazi vettoriali
Multifattoriale Funzione, derivata dal fattoriale. Il multifattoriale di un numero naturale n con passo k (fattoriale k-esimo) è il prodotto di n e dei numeri che lo precedono con passo k (vale a dire: n – k, n – 2k, ecc.). In genere si indica con ; il fattoriale doppio (k = 2) in genere si indica con , e quello triplo (k = 3) con Formalmente è definito tramite la formula ricorsiva
N Notazione multi-indice Notazione matematica che permette di estendere, semplificandole, molte formule del calcolo combinatorio (ma non solo) al caso multidimemsionale. Per esempio dato due vettori n-dimensionali di numeri naturali e , la notazione è da intendersi equivalente a , e
La notazione multi-indice, per la quale sono definite alcune regole di composizione, risulta utile in vari campi della matematica, come nel calcolo infinitesimale in più variabili, nelle equazioni differenziali alle derivate parziali e nella teoria delle distribuzioni
Numeri di Bernoulli
Successione di numeri razionali definiti in modo ricorsivo: l’m-esimo numero di Bernoulli è la radice dell'equazione lineare avendo posto