Combinatoria

Archiu:Countingprinciple.svg

Combinatoria

La combinatoria, també cridada teoria coordinatoria, és una branca de la matemàtica pertanyent a l'àrea de matemàtiques discretes que estudia l'enumeració, construcció i existència de propietats de configuracions que satisfan certes condicions establides. Ademés, estudia les ordenacions o agrupacions d'un determinat número d'elements.

Els aspectes de la combinatoria inclouen contar les estructures d'un tipo i tamany donat (combinatòries enumerativas), decidir quàn poden complir-se certs criteris i construir i analisar objectes que complixquen els criteris (com en els dissenys combinatoris i la teoria de matroides) trobar objectes "més grans", "més menuts" o estructures combinatòries sorgides en un context algebraic, o aplicar tècniques algebraiques a problemes combinatoris (combinatoria algebraica).

En este últim camp, alvanços recents han introduït la «enumeració irracional», que estén les tècniques de conteo a objectes en dimensions no sanceres per mig de l'us d'exponents irracionals en funcions generadores.

Els problemes combinatoris sorgixen en moltes àrees de la matemàtica pura, especialment en àlgebra, teoria de provabilitats, topología i geometria, i la combinatoria també té moltes aplicacions en l'optimisació matemàtica, l'informàtica, la teoria ergòdica i la física estadística. Recentment, el seu us s'ha estés a l'economia espacial; per eixemple, utilisant ferramentes de geometria discreta per a resoldre els complexos problemes combinatoris que sorgixen en modelar l'ubicació òptima, el tamany i la distribució de plantes industrials en grans espais geogràfics (Oberfield et al., 2020).

Moltes qüestions combinatoriales han segut històricament considerades aisladamente, donant una solució adequada a un problema que sorgix en algun context matemàtic. A finals de el XX, no obstant, es varen desenrollar métodos teòrics poderosos i generals, convertint la combinatoria en una branca independent de les matemàtiques per dret propi. Una de les parts més antigues i accessibles de la combinatoria és la teoria de grafos, que també té numeroses conexions naturals a atres àrees. La combinatoria s'utilisa en freqüència en informàtica per a obtindre fòrmules i estimacions en l'anàlisis d'algoritmes.

Combinatoria

Per a saber qué cas d'combinatoria estem tractant cal determinar tres característiques:

• Si influïx o no l'orde dels elements.
• Si el número d'elements disponibles en el conjunt: n, és igual o distint dels presents en cada succés: r.
• Si es produïxen o no repeticions en el succés.

Vore el diagrama de la dreta. Es poden diferenciar:

P: #Permutació sense repetició.

V: Variacions sense repetició.

C: Combinacions sense repetició.

PR: #Permutació en repetició.

VR: Variacions en repetició.

CR: Combinacions en repetició.

$\begin{array}{cc}P{R}_n^{r,s,t,\dots }=\frac{n!}{r!\cdot s!\cdot t!\cdot \dots }& P_n=n!\\ V{R}_n^r=n^r& V_n^r=\frac{n!}{(n-r)!}\\ C{R}_n^r=(\genfrac{}{}{0ex}{}{n+r-1}{r})=\frac{(n+r-1)!}{r!(n-1)!}& C_n^r=(\genfrac{}{}{0ex}{}{n}{r})=\frac{n!}{r!\cdot (n-r)!}\end{array}$

Combinatoria sense repetició

La combinatoria estudia tres tipos de casos en elements finitos: #permutació, variacions i combinacions en este cas sense repetició, ya que cada element solament pot aparéixer una sola volta en cada event.

$\text{Combinatoria sin repetición}\{\begin{array}{c}\text{Permutaciones sin repetición}\\ \text{Variaciones sin repetición}\\ \text{Combinaciones sin repetición}\end{array}$

Vejam estos casos:

#Permutació sense repetició

Les #permutació de n elements són les possibles ordenacions d'un conjunt de n elements distints.

El seu número:

$P_n=n\cdot (n-1)\cdot (n-2)\cdot 3\cdot 2\cdot 1=n!$

(es llig “factorial de n”). Per conveni 0!=1

En la calculadora: en la tecla x! es calcula “factorial de x” , sent x un número entero no negatiu.

Eixemple: ¿Quants números de 4 sifres distintes poden escriure's en els dígits 2, 3 , 5 i 8?

Solució:

$P_4=4!=4\cdot 3\cdot 2\cdot 1=24$

Hi ha 24 números i són:

$\begin{array}{cccccccc}1:& 2358& 7:& 3258& 13:& 5238& 19:& 8235\\ 2:& 2385& 8:& 3285& 14:& 5283& 20:& 8253\\ 3:& 2538& 9:& 3528& 15:& 5328& 21:& 8325\\ 4:& 2583& 10:& 3582& 16:& 5382& 22:& 8352\\ 5:& 2853& 11:& 3825& 17:& 5823& 23:& 8523\\ 6:& 2835& 12:& 3852& 18:& 5832& 24:& 8532\end{array}$

Variacions sense repetició

Les variacions de n elements presos de r en r : possibles mostres ordenades de r elements distints que es poden extraure d'un conjunt de n elements, sent $r\le n$.

El seu número:

$V_n^r=\frac{n!}{(n-r)!}=n\cdot (n-1)\cdot (n-2)\dots (n-r+1)$

(r factors sancers consecutius decreixents a partir de n)

En la calculadora: en la tecla nPr es calcula: : $V_n^r,siendor\le n$.

Notem que: $V_n^n=P_n=n!$

Eixemple:

En una carrera en 6 atletes, ¿de quantes formes distintes podrien repartir-se les medalles d'or i argent?

Solució:

$V_6^2=\frac{6!}{(6-2)!}=\frac{6!}{4!}=\frac{6\cdot 5\cdot 4!}{4!}=6\cdot 5=30$

formes distintes i serien, numerant els dorsals de l'1 al 6 i senyalant primer l'or i segon l'argent:

$\begin{array}{cccccc}1:& 12& 11:& 31& 21:& 51\\ 2:& 13& 12:& 32& 22:& 52\\ 3:& 14& 13:& 34& 23:& 53\\ 4:& 15& 14:& 35& 24:& 54\\ 5:& 16& 15:& 36& 25:& 56\\ 6:& 21& 16:& 41& 26:& 61\\ 7:& 23& 17:& 42& 27:& 62\\ 8:& 24& 18:& 43& 28:& 63\\ 9:& 25& 19:& 45& 29:& 64\\ 10:& 26& 20:& 46& 30:& 65\end{array}$

Combinacions sense repetició

Les combinacions de n elements presos de r en r: possibles mostres sense orde de r elements distints que es poden extraure d'un conjunt de n elements $(r\le n)$.

El número de combinacions de r elements d'un conjunt de n ve dau pel coeficient binomial:

$C_n^r=(\genfrac{}{}{0ex}{}{n}{r})=\frac{n!}{r!\cdot (n-r)!}$

En la calculadora: en la tecla nCr es calcula $(\genfrac{}{}{0ex}{}{n}{r})$ (que es llig “n sobre r”)

Eixemple:

En una reunió de 8 persones deu nomenar-se una comissió formada per dos d'elles. ¿Quantes comissions distintes podrien nomenar-se?

Solució:

$C_8^2=(\genfrac{}{}{0ex}{}{8}{2})=\frac{8!}{2!\cdot (8-2)!}=\frac{8!}{2!\cdot 6!}=\frac{8\cdot 7\cdot 6!}{2!\cdot 6!}=\frac{8\cdot 7}{2\cdot 1}=4\cdot 7=28$

comissions distintes i serien estes, numerant a les persones de l'1 al 8:

$\begin{array}{cccccccc}1:& 12& 8:& 23& 15:& 35& 22:& 48\\ 2:& 13& 9:& 24& 16:& 36& 23:& 56\\ 3:& 14& 10:& 25& 17:& 37& 24:& 57\\ 4:& 15& 11:& 26& 18:& 38& 25:& 58\\ 5:& 16& 12:& 27& 19:& 45& 26:& 67\\ 6:& 17& 13:& 28& 20:& 46& 27:& 68\\ 7:& 18& 14:& 34& 21:& 47& 28:& 78\end{array}$

Combinatoria en repetició

La combinatoria en repetició estudia els casos d'combinatoria en els que alguns elements poden aparéixer més d'una volta en un event, com en el cas anterior es poden vore: #permutació, variacions i combinacions:

$\text{Combinatoria con repetición}\{\begin{array}{c}\text{Permutaciones con repetición}\\ \text{Variaciones con repetición}\\ \text{Combinaciones con repetición}\end{array}$

Vejam estos casos:

#Permutació en repetició

Les #permutació en repetició són les possibles ordenacions d'una seqüència de n signes entre els que hi ha alguns repetits (un es repetix x voltes, un atre i voltes, un atre z voltes… etc.).

El seu número:

$P{R}_n^{x,y,z,\dots }=\frac{n!}{x!\cdot y!\cdot z!\cdot \dots }$

Notem que:

$P{R}_n^{x,n-x}=(\genfrac{}{}{0ex}{}{n}{x})$

Eixemple: ¿Quants números distints de 6 sifres es poden escriure usant tres uns, dos cincos i un huit?

Solució:

$P{R}_6^{3,2,1}=\frac{6!}{3!\cdot 2!\cdot 1!}=\frac{6\cdot 5\cdot 4\cdot 3!}{3!\cdot 2}=\frac{6\cdot 5\cdot 4}{2}=6\cdot 5\cdot 2=60$

números distints i són:

$\begin{array}{cccccccccccc}1:& 111558& 11:& 118515& 21:& 155811& 31:& 511158& 41:& 518151& 51:& 811155\\ 2:& 111585& 12:& 118551& 22:& 158115& 32:& 511185& 42:& 518511& 52:& 811515\\ 3:& 111855& 13:& 151158& 23:& 158151& 33:& 511518& 43:& 551118& 53:& 811551\\ 4:& 115158& 14:& 151185& 24:& 158511& 34:& 511581& 44:& 551181& 54:& 815115\\ 5:& 115185& 15:& 151518& 25:& 181155& 35:& 511815& 45:& 551811& 55:& 815151\\ 6:& 115518& 16:& 151581& 26:& 181515& 36:& 511851& 46:& 558111& 56:& 815511\\ 7:& 115581& 17:& 151815& 27:& 181551& 37:& 515118& 47:& 581115& 57:& 851115\\ 8:& 115815& 18:& 151851& 28:& 185115& 38:& 515181& 48:& 581151& 58:& 851151\\ 9:& 115851& 19:& 155118& 29:& 185151& 39:& 515811& 49:& 581511& 59:& 851511\\ 10:& 118155& 20:& 155181& 30:& 185511& 40:& 518115& 50:& 585111& 60:& 855111\end{array}$

Variacions en repetició

Les variacions en repetició de n elements presos de r en r: possibles mostres ordenades de r elements no necessàriament distints que es poden extraure d'un conjunt de n elements.

El seu número:

$V{R}_n^r=n^r$

Notem que ací pot ser r > n

Eixemple: ¿Quants números distints de 3 sifres s'escriuen usant solament les sifres 1, 2, 5 i 8 ?

Solució:

$V{R}_4^3=4^3=64$

números distints i són:

$\begin{array}{cccccccccccccccc}1:& 111& 9:& 151& 17:& 211& 25:& 251& 33:& 511& 41:& 551& 49:& 811& 57:& 851\\ 2:& 112& 10:& 152& 18:& 212& 26:& 252& 34:& 512& 42:& 552& 50:& 812& 58:& 852\\ 3:& 115& 11:& 155& 19:& 215& 27:& 255& 35:& 515& 43:& 555& 51:& 815& 59:& 855\\ 4:& 118& 12:& 158& 20:& 218& 28:& 258& 36:& 518& 44:& 558& 52:& 818& 60:& 858\\ 5:& 121& 13:& 181& 21:& 221& 29:& 281& 37:& 521& 45:& 581& 53:& 821& 61:& 881\\ 6:& 122& 14:& 182& 22:& 222& 30:& 282& 38:& 522& 46:& 582& 54:& 822& 62:& 882\\ 7:& 125& 15:& 185& 23:& 225& 31:& 285& 39:& 525& 47:& 185& 55:& 825& 63:& 885\\ 8:& 128& 16:& 188& 24:& 228& 32:& 288& 40:& 528& 48:& 588& 56:& 828& 64:& 888\end{array}$

Combinacions en repetició

Les combinacions en repetició de n elements presos de r en r: possibles mostres no ordenades de r elements no necessàriament distints que es poden extraure d'un conjunt de n elements.

El seu número:

$C{R}_n^r=(\genfrac{}{}{0ex}{}{n+r-1}{r})=\frac{(n+r-1)!}{r!(n-1)!}$

Notem que ací pot ser r > n

Eixemple: Un banc oferix un regal a elegir entre 5 possibles regals per cada llibreta. Un senyor que té tres llibretes en dit banc ¿de quantes formes pot elegir el lot de tres obsequios si no li importa repetir regals?

Solució:

$C{R}_5^3=(\genfrac{}{}{0ex}{}{5+3-1}{3})=\frac{(5+3-1)!}{3!*(5-1)!}=\frac{7!}{3!*4!}=\frac{7*6*5*4!}{3!*4!}=\frac{7*6*5}{3*2*1}=\frac{7*6*5}{6}=7*5=35$

lots distints i són:

$\begin{array}{cccccccccc}1:& 111& 8:& 124& 15:& 155& 22:& 235& 29:& 344\\ 2:& 112& 9:& 125& 16:& 222& 23:& 244& 30:& 345\\ 3:& 113& 10:& 133& 17:& 223& 24:& 245& 31:& 355\\ 4:& 114& 11:& 134& 18:& 224& 25:& 255& 32:& 444\\ 5:& 115& 12:& 135& 19:& 225& 26:& 333& 33:& 445\\ 6:& 122& 13:& 144& 20:& 233& 27:& 334& 34:& 455\\ 7:& 123& 14:& 145& 21:& 234& 28:& 335& 35:& 555\end{array}$

Història

Els conceptes bàsics sobre la combinatoria i els resultats enumerativos han aparegut a lo llarc del món antic. En el VI a. C., en l'antiga Índia, el mege Sushruta assegura en el Susruta-samhita que és possible formar 63 combinacions a partir de 6 sabors distints, presos d'un en un, de dos en dos, etc., aixina calculant totes les 2⁶ − 1 possibilitats. El historiador grec Plutarco va debatre en Crisipo de #Solo (III a. C.) i Hiparco de Nicea (II a. C.) sobre un problema enumerativo un tant delicat, el qual es va demostrar més alvance que guardava relació en el número Schröder–Hiparcos.

En l'Edat Mija, la combinatoria va continuar sent estudiada, sobretot fòra de la civilisació Europea. El matemàtic indi Mahāvīra (c. 850) va falcar una fòrmula per al número de permutacionés i combinacions, i és possible que estes fòrmules ya resultaren familiars als matemàtics indis a principis de el VI d. C. El filòsof i astrònom Rabbi Abraham ibn Ezra (c. 1140) va establir la simetria dels coeficients binomiales, mentres que una fòrmula concreta va ser trobada més alvance pel talmudista i matemàtic Gersónides, en 1321. El triàngul aritmètic —un diagrama gràfic mostrant les relacions entre els coeficients binomiales— ya havia aparegut en tractats matemàtics tan arrere com el X, i en el temps serien millor coneguts com el Triàngul de Pascal.

Durant el Renaixença, junt al restant de les matemàtiques i les cièncias, la combinatoria va gojar d'un renàixer. Treballs de Pascal, Newton, Jacob Bernoulli i Euler es varen tornar fonamentals en l'emergent camp. En els temps moderns, els treballs de J. J. Sylvester (a finals de el XIX) i Percy MacMahon (a principis de el XX) varen ajudar a assentar les bases per a la combinatòria enumerativa i combinatoria algebraica. La teoria de grafos també va gojar d'una explosió d'interés al mateix temps, en especial conexió en el teorema dels quatre colors.

En la segona mitat de el XX, la combinatoria va sofrir un creiximent ràpit, que va dur a l'establiment de dotzenes de nous diaris i conferències sobre este tema. En part, el creiximent va ser estimulat per les noves conexions i aplicacions en atres camps, des d'àlgebra fins a provabilitats, des del anàlisis funcional a la teoria de números, etc. Estes conexions varen terminar per trencar les vores entre la combinatoria i parts de la matemàtica i l'informàtica teòrica, pero al mateix temps va causar certa fragmentació dins del camp.

Àrees de la combinatoria

No existix una classificació tallant de lo que constituïx una subárea, sino que totes compartixen cert grau de traslape entre sí, de la mateixa manera que en atres branques de la matemàtica discreta. Diferents autors proponen vàries divisions de la combinatoria per lo que qualsevol llistat és merament indicatiu. Per eixemple, alguns autors consideren la teoria de grafos com una subárea de la combinatoria, mentres que uns atres la consideren un àrea independent.

Entre les subdivisions més comunes es troben les següents:

Combinatòria enumerativa

La combinatoria enumerativa és l'àrea més clàssica de la combinatoria i es concentra en contar el número de certs objectes combinatoris. Encara que contar el número d'elements en un conjunt és un problema matemàtic prou ampli, molts dels problemes que sorgixen en les aplicacions tenen una descripció combinatòria relativament simple. Els números de Fibonacci són l'eixemple bàsic d'un problema en la combinatòria enumerativa. La forma de dotze voltes major proporciona un marc unificat per a contar les #permutació, combinacions i particions.

Combinatoria analítica

La combinatoria analítica es referix a l'enumeració d'estructures combinatòries utilisant ferramentes d'anàlisis complex i teoria de provabilitats. En contrast en la combinatoria enumerativa, que utilisa fòrmules combinatòries explícites i funcions generadores per a descriure els resultats, la combinatoria analítica té com a objectiu obtindre fòrmules asintòtiques.

Teoria de la partició

La teoria de la partició estudia diferents problemes asintòtics i numerals relacionats en particions sanceres, i està estretament relacionada en les séries, funcions especials i polinomis ortogonals. Originalment era una part de la teoria numèrica i l'anàlisis, ara es considera una part de la combinatoria o un camp independent. Incorpora l'enfocament biyectivo i diverses ferramentes en anàlisis i teoria analítica de números, i té conexions en la mecànica estadística.

Teoria de grafos

Els grafos són objectes bàsics en la combinatoria. Les preguntes van des del reconte (per eixemple, el número de grafos en n vèrtiços en vores k) fins a estructurals (per eixemple, quines grafos contenen cicles hamiltonianos) a preguntes algebraiques (per eixemple, donat un grafo G i dos números x i i, el "Polinomi Tutte" TG (x, i) ¿té una interpretació combinatòria?). cal senyalar que, si be hi ha conexions molt fortes entre la teoria de grafos i la combinatoria, a voltes estos dos es consideren subjectes separats. Açò es deu al fet de que mentres que els métodos combinatoris s'apliquen a molts problemes de teoria de grafos, els dos s'utilisen generalment per a buscar solucions a diferents problemes.

Teoria del disseny

La teoria del disseny és un estudi de dissenys combinatoris, que són coleccions de subconjunts en certes propietats d'intersecció. Els dissenys de blocs són dissenys combinatoris d'un tipo especial. Esta àrea és una de les parts més antigues de la combinatoria, com en el problema de la colegiala de Kirkman propost en 1850. La solució del problema és un cas especial d'un sistema Steiner, els sistemes del qual juguen un paper important en la classificació de grups finitos simples. L'àrea té conexions adicionals en la teoria de la codificació i la combinatoria geomètrica.

Geometria finita

La geometria finita és l'estudi de sistemes geomètrics que tenen solament un número finito de punts. Els principals elements estudiats són estructures anàlogues a les trobades en #geometria contínues (pla euclidiano, espai proyectivo real, etc.) pero definides combinatorialmente. Esta àrea proporciona una rica font d'eixemples per a la teoria del disseny. No deu confondre's en la geometria discreta (geometria combinatòria).

Teoria de l'orde

La teoria de l'orde és l'estudi de conjunts parcialment ordenats, tant finitos com a infinits. En l'àlgebra, la geometria, la teoria de números i en tota la teoria combinatòria i gràfica apareixen varis eixemples d'órdens parcials. Algunes classes notables i eixemples d'órdens parcials inclouen rets i #àlgebra booleanas.

Teoria del matroide

La teoria del matroide abstrau part de la geometria. Estudia les propietats de conjunts (generalment, conjunts finitos) de vectores en un espai vectorial que no depenen dels coeficients particulars en una relació de dependència llineal. No solament l'estructura sino també les propietats enumerativas pertanyen a la teoria del matroide. La teoria del matroide va ser introduïda per Hassler Whitney i estudiada com a part de la teoria de l'orde. Ara és un camp d'estudi independent en una série de conexions en atres parts de la combinatoria.

Combinatoria extrema

La combinatoria extrema estudia les preguntes extremes sobre els sistemes de conjunts. Els tipos de preguntes abordades en este cas són sobre el major grafo possible que satisfà certes propietats. Per eixemple, el major grafo lliure de triànguls en 2n vèrtiços és un grafo bipartito complet Kn, n. A sovint és massa difícil inclús per a trobar la resposta extrema f(n) exactament i solament es pot donar una estimació asintòtica. La teoria de Ramsey és una atra part de la combinatoria extrema. Indica que qualsevol configuració suficientment gran contindrà algun tipo d'orde. És una generalisació alvançada del principi del colomer.

Combinatoria provabilística

En la combinatoria provabilística, les preguntes són del tipo següent: ¿quin és la provabilitat d'una certa propietat per a un objecte aleatori discret, tal com un grafo a l'encert? Per eixemple, ¿quin és el número promig de triànguls en un grafo a l'encert? Els métodos provabilístics també s'utilisen per a determinar l'existència d'objectes combinatoris en certes propietats prescrites (per a les quals poden ser difícils de trobar eixemples explícits), simplement observant que la provabilitat de seleccionar aleatoriamente un objecte en eixes propietats és major que 0. Este enfocament (a sovint referit com el método provabilístic) va demostrar ser altament eficaç en aplicacions a la combinatoria extremal i a la teoria dels grafos. Un àrea estretament relacionada és l'estudi de cadenes de Markov finitas, especialment en objectes combinatoris. Ací també s'utilisen ferramentes provabilístiques per a estimar el temps de mesclat. A quina associada en Paul Erdős, que va fer el treball pioner en el tema, la combinatoria provabilística va ser vista tradicionalment com un conjunt de ferramentes per a estudiar problemes en atres parts de la combinatoria. No obstant, en el creiximent de les aplicacions per a l'anàlisis d'algoritmes en l'informàtica, aixina com la provabilitat clàssica, la teoria aditiva i provabilística de número, l'àrea va créixer recentment per a convertir-se en un camp independent de la combinatoria.

Combinatoria algebraica

La combinatoria algebraica és un àrea de matemàtiques que ampra métodos d'àlgebra abstracta, notablement teoria de grup i teoria de representació, en varis contexts combinatoris i, a l'inversa, aplica tècniques combinatoria a problemes en àlgebra. La combinatoria algebraica està contínuament expandint el seu alcanç, tant en temes com en tècniques, i pot ser vista com l'àrea de matemàtiques a on l'interacció de métodos combinatoris i algebraics és particularment fort i significativa.

Combinatoria de paraules

La combinatoria de paraules tracta de llenguages formals. Es planteja de forma independent dins de vàries branques de les matemàtiques, incloent la teoria de números, la teoria de grups i la provabilitat. Té aplicacions a la combinatoria enumerativa, a l'anàlisis fractal, a l'informàtica teòrica, a la teoria dels autómates i a la llingüística. Encara que moltes aplicacions són noves, la jerarquia clàssica de classes de gramàtiques formals de Chomsky-Schützenberger és potser el resultat més conegut en el camp.

Combinatoria geomètrica

La combinatoria geomètrica està relacionada en la geometria convexa i discreta, en particular la combinatoria polièdrica. Es pregunta, per eixemple, quantes cares de cada dimensió pot tindre un politopo convexo. Les propietats mètriques dels politopos juguen també un paper important. Per eixemple: la teorema de Cauchy sobre la rigidea dels politopos convexos. També es consideren politopos especials, com el permutohedra, el associahedra i els politopos de Birkhoff. Devem tindre en conte que la geometria combinatòria és un nom antiquat per a la geometria discreta.

Combinatoria topològica

Els anàlecs combinatoris de conceptes i métodos en topología s'usen per a estudiar dibuix gràfic, divisió justa, particions, conjunts parcialment ordenats, arbres de decisió, problemes de collar i teoria de Morse discreta. No deu confondre's en la topología combinatòria que és un nom antic per a la topología algebraica.

Combinatoria aritmètica

La combinatoria aritmètica va sorgir de l'interacció entre la teoria numèrica, la combinatoria, la teoria ergòdica i l'anàlisis harmònic. Es tracta d'estimacions combinatòries associades en operacions aritmètiques (adició, substracció, multiplicació i divisió). La combinatòria aditiva es referix al cas especial quan solament estan involucrades les operacions de suma i resta. Una tècnica important en la combinatoria aritmètica és la teoria ergòdica dels sistemes dinàmics.

Combinatoria infinita

La combinatoria infinita, o teoria de conjunts combinatòria, és una extensió d'idees en combinatoria a conjunts infinits. És una part de la teoria de conjunts, un àrea de llògica matemàtica, pero utilisa ferramentes i idees tant de la teoria de conjunts com de la combinatoria extrema. Gian-Carlo Trencada va usar el nom d'combinatoria contínua per a descriure la provabilitat geomètrica, ya que hi ha moltes #analogia entre el reconte i la mida.

Combinatoria de conjunts

La combinatoria de conjunts és una branca de les matemàtiques, la llògica matemàtica i la teoria de conjunts que estudia l'enumeració, construcció, existència de propietats de configuracions que satisfan certes condicions establides relacionades en els conjunts, per la qual cosa estudia les ordenacions o agrupacions d'un determinat número d'elements per mig de diagrames de Euler, Leibniz, Venn i operacions basades en la teoria de conjunts, els quals varen aparéixer a lo llarc de les interaccions numèriques elementals.

Combinatòria enumerativa

La combinatoria enumerativa o enumeració estudia els métodos per a contar (enumerar) les distintes configuracions dels elements d'un conjunt que complixquen certs criteris especificats.

Esta va ser una de les primeres àrees de la combinatoria en ser desenrollada, i com atres àrees més recents s'estudien solament en cursos especialisats, és comú que es faça referència a esta subárea quan es menciona combinatoria en entorns escolars.

En tot problema combinatori hi ha varis conceptes claus que devem distinguir:

• 1. Població:

Es diu aixina al conjunt dels elements que estem estudiant. Designarem en una m al número d'elements del conjunt.

• 2. Mostra:

Es tracta d'un subconjunt de la població. Es denominarà en la lletra n al número d'elements que formen la mostra.

Els tipos de la mostra vénen determinats per dos aspectes:

Orde

Determina si és important o no que els elements de la mostra apareguen ordenats.

Repetició

La possibilitat de repetició o no dels elements.

Eixemple.

¿De quantes formes es pot obtindre 8 en tirar 2 daus?

Imagina que volem contar de quantes formes es pot obtindre 8 en tirar un parell de daus. Un pot realisar el clàssic diagrama de coordenades:

$\begin{array}{ccccccc}& 1& 2& 3& 4& 5& 6\\ 1& 2& 3& 4& 5& 6& 7\\ 2& 3& 4& 5& 6& 7& \underset{\_}{8}\\ 3& 4& 5& 6& 7& \underset{\_}{8}& 9\\ 4& 5& 6& 7& \underset{\_}{8}& 9& 10\\ 5& 6& 7& \underset{\_}{8}& 9& 10& 11\\ 6& 7& \underset{\_}{8}& 9& 10& 11& 12\end{array}$

I concloure que hi ha 5 formes d'obtindre el 8. En el mateix diagrama, podem trobar el resultat f(k) per a qualsevol suma k:

$f(2)=1,f(3)=2,f(4)=3,f(5)=4,f(6)=5,f(7)=6,f(8)=5,f(9)=4,f(10)=3,f(11)=2,f(12)=1.$

Pero ¿qué passa si volem tirar tres daus?, ¿cinc daus?, ¿20 daus?, ¿m donats? Ya no és pràctic usar la representació de coordenades, necessitem un nou model.

Considerem solament un dau. ¿De quantes formes podem obtindre el valor k? Puix d'una forma si k=1,2,3,4,5,6 i 0 de qualsevol atra forma. Anem a codificar tots els resultats possibles en una única expressió: $a+a^2+a^3+a^4+a^5+a^6$.

Entre els contes, pot perdre un de punt de vista l'idea central: estem representant una successió de varis valors (formes de tirar un dau) per mig d'un sol objecte algebraic (un poliomio), i manipulacions en este objecte nos donen informació sobre la combinatoria del problema.

El método pot modificar-se per a resoldre problemes similars (per eixemple, si volguérem saber de quantes formes es pot obtindre 30 en tirar 3 daus normals i dos daus en forma d'icosaedre, intentaríem trobar el coeficient de $a^{30}$ en el desenroll de $(a+a^2+a^3+a^4+a^5+a^6{)}^3\cdot (a+a^2+a^3+\dots +a^{20}{)}^2$.

Est és un cas particular del método de funcions generadores, en el que una série de potències representa una cantitat (possiblement infinita) de valors d'una successió.

Eixemple.

Considere's el conjunt $S=\{A,E,I,O,U\}$. Podem imaginar que estos elements corresponen a targetes dins d'un capell.

• Un primer problema podria consistir en trobar el número de formes diferents en que podem traure les targetes una despuix d'una atra (és dir, el número de #permutació del conjunt).

Per eixemple, dos formes distintes podrien ser: EIAOU o OUAIE.

• Despuix, es pot preguntar pel número de formes en que es pot traure solament 3 targetes del capell (és dir, el número de 3-#permutació del conjunt).

En este cas, eixemples poden ser IOU, AEI o EAI.

• També es pot preguntar sobre quins són els possibles grups de 3 targetes que es poden extraure, sense donar consideració a l'orde en que ixen (en atres paraules, el valor d'un coeficient binomial).

Ací, consideraríem AOU i UAO com un mateix resultat.

• Un atre problema consistix en trobar el número de formes en que poden eixir 5 targetes, una despuix d'una atra, pero en cada moment es retorna la targeta triada al capell.

En este problema els resultats possibles podrien ser EIOUO, IAOEU o IEAEE.

La combinatòria enumerativa estudia les tècniques i métodos que permeten resoldre problemes anteriors, aixina com uns atres més complexos, quan el número d'elements del conjunt és arbitrari. D'esta forma, en el primer eixemple la generalisació corresponent és determinar el número de formes en que es poden ordenar tots els elements d'un conjunt en n elements, sent la resposta el factorial de n.

Combinatòria extremal

L'enfocament ací és determinar qué tan gran o menuda deu ser una colecció d'objectes per a que satisfaça una condició prèviament establida;

Eixemple.

Considere's un conjunt S. en n elements. A continuació s'escomença a fer un llistat de subconjunts de tal manera que qualsevol parella de subconjunts del llistat tinga algun element en comú.

Per a clarificar, siga $S=\{A,B,C,D\}$ i un possible llistat de subconjunts podria ser

$\{B,C\},\{A,B\},\{A,B,C,D\},\{B,D\},\dots$

Conforme aumenta el llistat (i ya que hi ha una cantitat finita d'opcions), el procés es fa cada volta més complicat. Per eixemple, no podríem afegir el conjunt {A, D} al llistat puix encara que té elements en comú en els últims 3 subconjunts del llistat, no compartix cap element en el primer.

La pregunta sobre quina tan gran pot fer-se el llistat de manera que qualsevol parella de subconjunts tinga un element en comú és un eixemple de problema d'combinatoria extremal (o combinatoria extrema). La resposta a este problema és que si el conjunt original té n elements, llavors el llistat pot tindre com a màxim $2^{n-1}$ subconjunts.

Campos relacionats

Optimisació combinatòria

L'optimisació combinatòria és l'estudi de l'optimisació d'objectes discrets i combinatoris. Va començar com a part de la teoria combinatòria i la teoria de grafos, pero ara es veu com una branca de la matemàtica aplicada i l'informàtica, relacionada en l'investigació d'operacions, la teoria d'algoritmes i la teoria de la complexitat computacional.

Teoria de la codificació

La teoria de la codificació va començar com a part de la teoria del disseny en construccions combinatoriales primerenques de còdics correctors d'errors. L'idea principal del tema és dissenyar métodos eficients i confiables de transmissió de senyes. Ara és un gran camp d'estudi, part de la teoria de l'informació.

Geometria discreta i computacional

La geometria discreta (també cridada geometria combinatòria) també va començar com una part de la combinatoria, en resultats primerencs en politopos convexos i "números propencs". En l'aparició d'aplicacions de geometria discreta a la geometria computacional, estos dos camps es varen fusionar parcialment i es varen convertir en un camp d'estudi independent. Seguixen existint moltes conexions en combinatoria geomètriques i topològiques, que poden ser vistes com a conseqüència de la geometria discreta primerenca.

Combinatoria i sistemes dinàmics

Els aspectes combinatoris dels sistemes dinàmics són un atre camp emergent. Ací es poden definir sistemes dinàmics sobre objectes combinatoris. Vejau, per eixemple, el sistema dinàmic de grafos.

Combinatoria i física

Hi ha interaccions cada volta majors entre la combinatoria i la física, particularment la física estadística. Els eixemples inclouen una solució exacta del model de Ising, i una conexió entre el model de Potts en una mà, i els polinomis cromàtics i de Tutte per una atra part.

Cardinalidad de l'Unió de Conjunts

Principi de la suma

Para conjunts disjuntos

Siguen $A_1$ i $A_2$ conjunts disjuntos ($A_1\cap A_2=\varnothing$) llavors: $|A_1\cup A_2|=|A_1|+|A_2|$

Tal i com enuncia El Principi de la Suma:

El número d'elements en una unió de conjunts disjuntos és igual a la suma dels tamanys de tots els conjunts

Este principi es pot demostrar per inducció sobre el número de conjunts.

La demostració pot escomençar basant-se que els conjunts {$0,1,2,3,\mathrm{...},m-1$} i {$n,n+1,\mathrm{...},n+m-1$}. Este principi pot estendre's a tres o més conjunts, en tal cas, diu que si $A_1,A_2,\mathrm{...},A_n$ són conjunts disjuntos dos a dos ($A_i\cap A_j=\varnothing$ per a $i\ne j$):

$|A\cup A_2\cup A_3\mathrm{...}\cup A_n|=|A_1|+|A_2|+\mathrm{...}+|A_n|$

Aixina i tot, el principi de la suma pot enunciar-se com:

Per a conjunts no disjuntos

Sean $A_1$ i $A_2$ dos conjunts ($A_1\cap A_2\ne \varnothing$) llavors: $|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|$

Per a demostrar este enunciat es pot escomençar suponent que $A_1=(A_1\mathrm{\setminus }{A}_2)\cup (A_1\cap A_2)$ en $(A_1\mathrm{\setminus }{A}_2)\cap (A_1\cap A_2)=\varnothing$ després $|A_1|=|A_1\mathrm{\setminus }{A}_2|+|A_1\cap A_2|$ provocant que:$|A_1\mathrm{\setminus }{A}_2|=|A_1|-|A_1\cap A_2|$

Ya que $A_1\cup A_2=(A_1\mathrm{\setminus }{A}_2)\cup (A_1\cap A_2)\cup (A_2\mathrm{\setminus }{A}_1)$:

$|A_1\cup A_2|=|A_1\mathrm{\setminus }{A}_2|+|A_1\cap A_2|+|A_2\mathrm{\setminus }{A}_1|=|A_1|-|A_1\cap A_2|+|A_1\cap A_2|+|A_2|-|A_1\cap A_2|=|A_1|+|A_2|-|A_1\cap A_2|$

Principi del producte

Sean $A_1$ i $A_2$ dos conjunts: $|A_1\times A_2|=|A_1|\cdot |A_2|$.

Per a demostrar este enunciat es deu trobar una biyección entre {$0,1,\mathrm{...},m+n-1$} i {$0,1,\mathrm{...},m-1$} $\times${$0,1,\mathrm{...},n-1$}. La biyección vindria donada per $a\mapsto (amodb,a$ div $m)$.

El principi pot generalisar-se a tres o més conjunts obtenint-se: $|A_1\times A_2\times \mathrm{...}\times A_m|=|A_1|\cdot |A_2|\mathrm{...}|A_m|$

Ademés, este principi pot ser enunciat de la següent manera:

Si una tasca podem dividir-la en dos o més tasques consecutives de manera que hi ha $n_1$ formes de realisar la primera tasca, i $n_2$ formes de realisar la segona tasca, llavors hi ha $n_1{n}_2$formes de completar la tasca.

Generalisació del principi d'Inclusió-Exclusió

Siga S un conjunt finito $|S|=N$ i $p_1,p_2,\mathrm{...},p_k$ una colecció de propietats o condicions que són complides per a lo manco un element del conjunt S.

S'indica per mig de $\overline{p_i}$ que no complixca la propietat $p_i$.

D'esta manera $N(p_i)$ és el número d'elements de S que complixen $p_i$ i $N(\overline{p_i})=N-N(p_i)$ és el número d'elements de S que no complixen $p_i$.

El número d'elements de S que no complixen cap propietat $p_i,1\le i\le k$ serà:

$\bar{N}=N({\bar{p}}_1{\bar{p}}_2{\bar{p}}_3\mathrm{...}{\bar{p}}_k)=N-\sum _{1\le i\le k}N(p_i)+\sum _{1\le i,j\le k}N(p_i{p}_j)+\mathrm{...}+(-1{)}^{k}N(p_1{p}_2\mathrm{...}{p}_k)$

Binomi de Newton

Donats dos números a, b ∈ R sabem que el desenroll del quadrat del binomi a + b ve dau per: (a + b)² = a² + 2ab + b².

Podem reescriure este desenroll com:

$(a+b{)}^2=(\genfrac{}{}{0ex}{}{2}{0})a^0{b}^2+(\genfrac{}{}{0ex}{}{2}{1})a^1{b}^1+(\genfrac{}{}{0ex}{}{2}{2})a^2{b}^0=\sum _{k=0}^2(\genfrac{}{}{0ex}{}{2}{k})a^k{b}^{2-k}$

Análogamente per al desenroll de la gaveta d'un binomi:

(a + b)³ = a³ + 3a²b + 3ab² + b³ que també pot reescriure's com:

$(a+b{)}^3=(\genfrac{}{}{0ex}{}{3}{0})a^0{b}^3+(\genfrac{}{}{0ex}{}{3}{1})a^1{b}^2+(\genfrac{}{}{0ex}{}{3}{2})a^2{b}^1+(\genfrac{}{}{0ex}{}{3}{3})a^3{b}^0=\sum _{k=0}^3(\genfrac{}{}{0ex}{}{3}{k})a^k{b}^{3-k}$

La fòrmula del binomi de Newton generalisa lo anterior al desenroll de qualsevol potència natural d'un binomi i s'expressa de la següent manera.

Teorema 1 (Fòrmula del binomi de Newton)

Para qualssevol números a, b ∈ R i qualsevol número n ∈ N es verifica:

$(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}$

Demostració

Per inducció respecte de n demostrarem que la proposició

$p(n):\mathrm{\forall }a,bϵR,(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}$ és verdadera per a tot número natural n.

Passe base: Provem que p(1) és V.

$p(1):\mathrm{\forall }a,bϵR,(a+b{)}^1=\sum _{k=0}^1(\genfrac{}{}{0ex}{}{1}{k})a^k{b}^{1-k}$

El membre esquerre de l'igualtat és simplement a + b. El membre dret és:

$(\genfrac{}{}{0ex}{}{1}{0})a^0{b}^1+(\genfrac{}{}{0ex}{}{1}{1})a^1{b}^0=a+b$ de modo que p(1) és verdadera.

(HI)Hipòtesis inductiva: Supongam que p(n) és verdadera.

Ara provarem que necessàriament p(n + 1) és verdadera, baix el supòsit (HI). Per a això procedim aixina:

$(a+b{)}^{n+1}=(a+b)(a+b{)}^n=(a+b)\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}=$

$=a\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}+b\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}=$

$=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{k+1}{b}^{n-k}+\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k+1}=$

$=\sum _{j=1}^{n+1}(\genfrac{}{}{0ex}{}{n}{j-1})a^j{b}^{n-j+1}+\sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})a^j{b}^{n-j+1}=$

$=(\genfrac{}{}{0ex}{}{n}{n})a^{n+1}+\sum _{j=1}^n(\genfrac{}{}{0ex}{}{n}{j-1})a^j{b}^{n-j+1}+(\genfrac{}{}{0ex}{}{n}{0})b^{n+1}+\sum _{j=1}^n(\genfrac{}{}{0ex}{}{n}{j})a^j{b}^{n-j+1}=$

$=(\genfrac{}{}{0ex}{}{n}{0})b^{n+1}+\{\sum _{j=1}^n[(\genfrac{}{}{0ex}{}{n}{j-1})+(\genfrac{}{}{0ex}{}{n}{j})]a^j{b}^{n-j+1}\}+(\genfrac{}{}{0ex}{}{n}{n})a^{n+1}=$

$=(\genfrac{}{}{0ex}{}{n}{0})b^{n+1}+\sum _{j=1}^n(\genfrac{}{}{0ex}{}{n+1}{j})a^j{b}^{n-j+1}+(\genfrac{}{}{0ex}{}{n}{n})a^{n+1}=$

$=(\genfrac{}{}{0ex}{}{n+1}{0})a^0{b}^{n+1}+\sum _{j=1}^n(\genfrac{}{}{0ex}{}{n+1}{j})a^j{b}^{n-j+1}+(\genfrac{}{}{0ex}{}{n+1}{n+1})a^{n+1}{b}^0=$

$=\sum _{j=0}^{n+1}(\genfrac{}{}{0ex}{}{n+1}{j})a^j{b}^{n+1-j}=$

que mostra que p(n + 1) és verdadera. Després, per inducció completa p(n) és verdadera per a tot n ∈ N.

Principis de la Combinatoria

Principi fonamental de conteo

El principi fonamental de conteo establix que si hi ha p formes de fer una cosa, i q formes de fer una atra cosa, llavors hi ha p × q formes de fer abdós coses.

<o>Eixemple 1:</o>

Suponga que té 3 camises (cridem-les A, B, i C), i 4 parells de pantalons (cridem-los w , x , i , i z ). Llavors Vosté té

3 × 4 = 12

combinacions possibles:

A w , A x , A i , A z

B w , B x , B i , B z

C w , C x , C i , C z

<o>Eixemple 2:</o>

Suponga que llança un dau de 6 cares i trau una carta d'un mall de 52 cartes. Hi ha 6 resultats possibles en el dau, i 52 resultats possibles en el mall de cartes. Aixina, hi ha un total de

6 × 52 = 312 resultats possibles de l'experiment.

El principi de conteo pot estendre's a situacions a on tinga més de 2 opcions. Per eixemple, si hi ha p formes de fer una cosa, q formes per a una segona cosa, i r formes de fer una tercera cosa, llavors hi ha p × q × r formes de fer les tres coses.

Principi de la Multiplicació

Si es desija realisar una activitat que consta de r passos, en a on el primer pas de l'activitat a realisar pot ser portat a terme de N₁ maneres o formes, el segon pas de N₂ maneres o formes i el r-ésimo pas de N_r maneres o formes, llavors esta activitat pot ser duta a efecte de. El principi multiplicativo implica que cada u dels passos de l'activitat deuen ser duts a efecte, un darrere l'atre. Si un event I1 pot succeir de n1 maneres diferents, l'event I2 pot ocórrer de n2 maneres diferents, i aixina successivament fins a l'event Ep el qual pot ocórrer de np maneres diferents, llavors el total de maneres distintes en que pot succeir l'event “ocorren I1 i I2…..i Ep” és igual a producte.

N1 x N2 x ..........x  Nr  maneres o formes

<o>Eixemple:</o>

Es dispon de 3 vies per a viajar de C1 a C2   i de 4 vies per a viajar de C2 a C1. ¿De quantes formes es pot organisar el viage d'anada i regrés de C1 a C2.Resposta: (3)(4)=12

Principi Aditiu

Si es desija dur a efecte una activitat, la qual té formes alternatives per a ser realisada, a on la primera d'eixes alternatives pot ser realisada de M maneres o formes, la segona alternativa pot realisar-se de N maneres o formes ..... i l'última de les alternatives pot ser realisada de W maneres o formes, llavors eixa activitat pot ser duta  a veta de,

                       M + N + .........+ W  maneres o formes

<o>Eixemples:</o>

1)      Una persona desija comprar una llavadora de roba, per ad açò ha pensat que pot seleccionar d'entre les marques Whirpool, Easy i General Electric, quan acodix a fer la compra es troba que la llavadora de la marca W es presenta en dos tipos de càrrega ( 8 o 11 quilograms), en quatre colors diferents i pot ser automàtica o semiautomàtica, mentres que la llavadora de la marca I, es presenta en tres tipos de càrrega (8, 11 o 15 quilograms), en dos colors diferents i pot ser automàtica o semiautomàtica i la llavadora de la marca GE, es presenta en solament un tipo de càrrega, que és d'11 quilograms, dos colors diferents i solament hi ha semiautomàtica. ¿Quantes maneres té esta persona de comprar una llavadora?

Solució:

M = Número de maneres de seleccionar una llavadora Whirpool

N = Número de maneres de seleccionar una llavadora de la marca Easy

W = Número de maneres de seleccionar una llavadora de la marca General Electric

M = 2 x 4 x 2 = 16 maneres

N = 3 x 2 x 2 = 12 maneres

W = 1 x 2 x 1 = 2 maneres

M + N + W = 16 + 12 + 2 = <o>30 maneres de seleccionar una llavadora</o>

Principi de la Suma o de l'Adició

Si una primera operació pot realisar-se de m maneres i una segona operació de n maneres, llavors una operació o l'atra poden efectuar-se de:

                     m+n maneres.

<o>Eixemple:</o>

Una parella que es té que casar, junta diners per a l'enganche de la seua casa, en el fraccionament lomas de l'assut li oferixen un model econòmic o un condomini, en el fraccionament Plages li oferixen un model econòmic com a models un residencial, un californià i un provençal. ¿Quantes alternatives diferents de vivenda li oferixen a la parella?

PRESA                     PLAGES

Econòmic             Residencial

Condomini           Californià

                             Provençal

m=2                           n=3 b=7 v=9 i=3 q=1 x=54 p=67 i=90

          2+3= 5 maneres

Principi de permutació

A diferència de la fòrmula de la multiplicació, li l'utilisa per a determinar el número de possibles apanys quan solament hi ha un sol grup d'objectes. Permutació: un apany o posició de r objectes seleccionats d'un sol grup de n objectes possibles. Si nos donem conte els apanys a, b, c i b, a, c són #permutació diferents, la fòrmula que s'utilisa per a contar el número total de #permutació distintes és:

                                             <o>FÒRMULA</o>: n P r = n!/(n - r)!

<o>Eixemple:</o> ¿Cóm es pot designar els quatre primers llocs d'un concurs, a on existixen 15 participants?

Aplicant la fòrmula de la permutació tenim:                                        

n P r = n! (n - r)! = 15! = 15*14*13*12 *11*10*9*8*7*6*5*4*3*2*1 /(15-4)! 11*10*9*8*7*6*5*4*3*2*1 = 32760

A on:

n= número total d'objectes

r= número d'objectes seleccionats

!= factorial, producte dels número natural entre 1 i n.

NOTA: es poden cancelar números quan es tenen les mateixes sifres en numerador i denominador.

Principi de combinació

En una permutació, l'orde dels objectes de cada possible resultat és diferent. Si l'orde dels objectes no és important, cada u d'estos resultats es denomina combinació. Per eixemple, si es vol formar un equip de treball format per 2 persones seleccionades d'un grup de tres (A, B i C). Si en l'equip hi ha dos funcions diferents, llavors si importa l'orde, els resultats seran #permutació. Pel contrari si en l'equip no hi ha funcions definides, llavors no importa l'orde i els resultats seran combinacions. Els resultats en abdós casos són els següents:

1. Permutació: AB, AC, BA, CA, BC, CB

Combinacions: AB, AC, BC

Combinacions: És el número de formes de seleccionar r objectes d'un grup de n objectes sense importar l'orde.

La fòrmula de combinacions és:

                                  n C r = n! / [r!(n – r)!]

<o>Eixemple:</o> En una companyia es vol establir un còdic de colors per a identificar cada una de les 42 parts d'un producte. Es vol marcar en 3 colors d'un total de 7 cada una de les parts, de tal sòrt que cada una tinga una combinació de 3 colors diferents. ¿Serà adequat este còdic de colors per a identificar les 42 parts del producte? Usant la fòrmula de combinacions:

                n! = 7! = 5040
                r! (n – r )! =  3! (7 – 3)! = 3! 4! =6 * 24 = 144

Llavors: n C r = 5040 / 144 =35

El prendre tres colors de 7 possibles no és suficient per a identificar les 42 parts del producte.

Vore també

• Permutació
• Coeficient binomial
• Teoria de Ramsey
• Combinacions en repetició
• Factorial d'un número
• [[Archiu:{{#switch:Matemàtica|20px|Vore el portal sobre Matemàtica]] Portal:Matemàtica. Contingut relacionat en Matemàtica.

Referències

Bibliografia

• Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
• Bóna, Miklós; (2011); A Walk Through Combinatorics (3rd Edition). ISBN 978-981-4335-23-2, ISBN 978-981-4460-00-2(pbk)
• Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); Handbook of Combinatorics, Volumes 1 and 2. Ámsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. ISBN 0-262-07169-X
• Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press; 1st. edition (October 31, 1997). ISBN 0-8493-3986-3.
• Riordan, John (1958); An Introduction to Combinatorial Analysis, New York, NY: Wiley & Sons (republished)
• Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1
• van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd Edition, Cambridge University Press. ISBN 0-521-80340-3
• Handbook of Combinatorics, Volumes 1 and 2, R.L. Graham, M. Groetschel and L. Lovász (Eds.), MIT Press, 1996. ISBN 0-262-07169-X

• Enumerative Combinatorics, Volumes 1 and 2, Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N
• http://www.vitutor.com/pro/1/a_1.html
• https://combinatorica.wordpress.com/tag/combinatòria-enumerativa/

https://www.unirioja.es/talleres/creatividad_matematica/seminariobachillerato/combinatoria.pdf https://sites.google.com/site/estadisticayprobabilidad111/8---principi-fonamental-de-conteo https://www.varsitytutors.com/hotmath/hotmath_help/spanish/topics/fundamental-counting-principle#::text=El%20principi%20fonamental%20de%20conteo,formes%20de%20fer%20abdós%20coses.&text=resultats%20possibles%20de el%20experiment.,tinga%20m%C3%A1s%20de%202%20opcions.

Enllaços externs

Commons

• Wikimedia Commons alberga contingut multimèdia sobre Combinatòria.
• Plantilla:Springer
• Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
• Combinatorics, a MathWorld article with many references.
• Combinatorics, from a MathPages.com portal.
• The Hyperbook of Combinatorics, a collection of math articles links.
• The Two Cultures of Mathematics by W. T. Gowers, article on problem solving vs theory building.
• "Glossary of Terms in Combinatorics"
• Archivat el 17 de agost de 2017 archivat en Wayback Machine.
• List of Combinatorics Software and Databases
• Eixemples i demostracions. Combinatoria
• Principi d'Inclusió-Exclusió

• http://portal.perueduca.edu.pe/modulos/mod_matconteo/mod_4publish/index.html
• http://cibermath.com/cuarto/principios-fonamentals-de-conteo.htm