Principis combinatoris

En provar els resultats en combinatòria, es reconeixen i utilisen comunament vàries regles combinatòries o principis combinatoris útils.

La regla de la suma, la regla del producte i el principi d'inclusió-exclusió s'utilisen a sovint en fins enumerativos. Les proves biyectivas s'utilisen per a demostrar que dos conjunts tenen el mateix número d'elements. El principi de caseller a sovint determina l'existència d'alguna cosa o s'usa per a determinar el número mínim o màxim d'alguna cosa en un context discret.

Moltes identitats combinatòries sorgixen de métodos de conteo doble o del método de l'element distinguit. La generació de funcions i relacions de recurrencia són ferramentes poderoses que poden usar-se per a manipular seqüències i poden descriure, si no resoldre, moltes situacions combinatòries.

Regla de la suma

Artícul principal → Regla de la suma.

La regla de la suma és un principi intuïtiu que establix que si hi ha possibles resultats per a un event (o formes de fer alguna cosa) i possibles resultats per a un atre event (o formes de fer una atra cosa), i els dos events no poden ocórrer al mateix temps ( o les dos coses no es poden fer abdós), llavors hi ha un total de possibles resultats per als events (o possibles formes totals de fer una de les coses). Més formalment, la suma dels tamanys de dos conjunts disjuntos és igual al tamany de la seua unió.

Regla del producte

Artícul principal → Principi del producte (combinatòria).

La regla del producte és un atre principi intuïtiu que establix que si hi ha $a$ formes de fer alguna cosa i $b$ formes de fer una atra cosa, llavors hi ha $a\cdot b$ formes de fer abdós coses.

Referències

• J. H. van Lint and R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press. ISBN 0-521-00601-5