Combinatoria

Na Galipedia, a Wikipedia en galego.

Definición[editar | editar a fonte]

Parte das matemáticas que estuda a aplicación inxectiva ou bixectiva, unívoca ou biunívoca dun conxunto noutro para esclarecer as súas posibilidades de combinación. O habitual é asocialo a problemas de escoller unha serie de elementos (e ou n) dun conxunto total para localizalos nun número determinado de lugares ou posicións (p) [por exemplo, as posibles localizacións de dúas pezas de xadrez nos escaques dun taboleiro], pero tamén se pode interpretar á viceversa, coma unha escolla un número determinado de veces (p ou r) de entre un grupo total de elementos (e) [como se se escollesen cartas dunha baralla]. De calquera xeito, pódese diseccionar un problema combinatorio coma unha suma de varios experimentos aleatorios individualizables, analizables estatísticamente. É importante traballar cunha terminoloxía clara e explícita, pois é doado cometer erros lingüísticos e malentendidos nas caracterizacións dos problemas.

Xeneralidades[editar | editar a fonte]

Inda que as posibilidades de análise combinatorio dependen do problema concreto, as operacións máis coñecidas son a permutación, a variación, a combinación e a ordenación. Debido á existencia dunha certa indefinición terminolóxica, definiranse os seus valores dependendo das características do problema. Para poder emprender a análise combinatoria, débense definir as propiedades do caso, que en termos xerais son as seguintes:

  1. Tras cada experimento individual, existe unha reposición de e no grupo onde estaba orixinariamente (se o grupo é aleatorio, a análise complícase moito máis) ou ben nestes grupos non hai repeticións nas circunstancias do experimento e polo tanto non son sorteos independentes: nesta caracterización, as palabras chave son repetición =reposición=independencia fronte a dependencia= sen reposición;
  2. Tras rematar toda a secuencia de experimentos, no resultado é pertinente a orde da secuencia ou ben non existe importancia na altura, posición ou tempo no que se conseguiu cada resultado de entre os experimentos: aquí as palabras definitorias serán ordenada =con orde e non ordenada= sen orde;
  3. Coincide que o número de experimentos aleatorios realizado (p) é igual ó número de elementos escollidos ou localizados (e) ou ben é menor (nunca pode ser maior se na característica 1 non hai experimentos independentes, se non hai reposición): isto definiráse cos propios valores numéricos de p e e (ou se se quere r e n respectivamente, como se adoita notar);
  4. Existen subgrupos internamente idénticos na identificación pero diferenciables entre si no universo estatístico de elementos, que obrigan a retomar unha variante especial da segunda característica pola cal a orde entre os elementos que son iguais non é discriminatoria (ou discriminante). Se tódolos elementos son distintos denominarase distinguibles ou diferenciables;

Exemplo de caracterización[editar | editar a fonte]

Supóñase un conxunto de bólas: unha branca, unha azul, unha vermella e unha negra, que se abreviarán coa inicial da súa cor: BAVN. Se se meten nunha bolsa opaca e se extraen aleatoriamente unha serie de veces, pódese facer unha caracterización do problema segundo os puntos mencionados antes:

  1. Se despois de sacar unha bóla se volve a meter na bolsa habería experimentos independentes e repetidos, xa que na segunda extracción volven estar as catro bólas iniciais. Se se fai a proba sen reposición, os experimentos serán dependentes;
  2. Se tralo sorteo, poñamos sacar tres bólas, dése igual obter BAV que BVA ou VBA ou VAB ou ABV ou AVB nesa orde senón que o que importa é non sacar a bola N, estarase ante un problema sen orde. Se estas seis posibilidades se consideran distintas, o sorteo é ordenado;
  3. Se se teñen catro bólas na bolsa e se fan dúas ou tres extraccións con ou sen reposición n sería distinto de r. Se se fan catro extraccións, entón n=r. Se se fan máis de catro extraccións, necesariamente debe haber reposición, pois se se sacan as catro bólas sen reintegralas ó saco non haberá bólas tralo cuarto experimento.
  4. Se houbese dúas bólas da mesma cor e non se puidesen diferenciar (por exemplo, tendo inicialmente B, A e dúas V), entón a vermella que foi sacada primeira podería ser calquera das dúas da bolsa: isto débese ter en conta no cálculo numérico e habería subgrupos. Se as bolas fosen B, A, V e N, os elementos serían diferenciables.

Posibilidades da análise[editar | editar a fonte]

Unha técnica de análise é a chamada árbore de experimentos, onde se vai estruturando a serie de posibles resultados dependendo das condicións dos experimentos. Esta técnica permite facerse unha idea das características do problema e acertar coa resolución. Velaí os exemplos definidos segundo as caracterizacións anteriores, para tres bolas de tres cores distintas:

  • AAA
  • AAB
  • ABA
  • ABB
  • BAA
  • BAB
  • BBA
  • BBB

Outra posibilidade é botar man directamente das ecuacións, que se representan na seguinte táboa tamén clasificadas segundo as súas características, numeradas igual cás anteriores, excluíndo a 4):

TIPO 1 SUBTIPO 2 3 = n <> r 3 =n= r NOME
1 = independentes 2 = con orde  \frac{n!}{(n-r)!}  \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n! Permutación
1 = independentes 2 = sen orde  \frac{n!}{(n-r)! \, r!}  \frac{n!}{(n-n)! \, n!} = \frac{n!}{0! \, n!} = \frac{n!}{1 \, n!} = \frac{n!}{n!} = 1 Combinación
1 = dependentes 2 = con orde  \frac{r^n}{r!}  \frac{n^n}{n!} = \frac{r^r}{r!} Reposición sen orde
1 = dependentes 2 = sen orde  r^n \,  n^n \, = r^r Reposición con orde

Subprobabilidades[editar | editar a fonte]

En todo o anterior simplemente importa o resultado de cada extracción, pero pode acontecer que cada extracción teña unha probabilidade intrínseca. Isto vese máis claro no seguinte exemplo.

Supoñamos que nunhas oposicións sácanse cinco bolas consecutivamente sen reposición (dependentes) dunha caixa con 75 en total, que cada unha tén un tema do temario oficial (de 75 temas en total), que len os temas que lle corresponden a cada bola e a persoa que vai facer o exame escolle un de entre eses cinco. Disto dedúcese que non hai subgrupos internos porque tódalas bólas son distintas e a serie non está ordenada porque a orde de extracción non importa.

Loxicamente, quen realiza o exame quere estudar cantos menos mellor, co cal supoñamos que só aprendeu ben x, pero que os sabe moi ben. O mellor (para o cálculo, non para ser gafe) é calcular as probabilidades de que non saia ningún tema dos estudados. As probabilidades de que saquen unha primeira bola dun tema non estudado son de 75-x (=número de temas non estudados)/75. As de que saquen unha segunda bóla de tema descoñecido son 74-x/74, etc. As probabilidades finais de que tódolos temas fosen descoñecidos son:

 \frac{75-x}{75} * \frac{74-x}{74} * \frac{73-x}{73} * \frac{72-x}{72} * \frac{71-x}{71} = \frac{(75-x)!}{75!} * \frac{70!}{(70-x)!}

Non tódalas calculadoras permiten cálculos con valores tan elevados, así que se pode pór isto nunha folla de cálculo e dándolle valores enteiros a x (número de temas estudados), as probabilidades de que saquen tódalas bólas con temas non estudados quedarían reflectidas nesta gráfica (loxicamente sae unha función polinómica de quinto grao que pasa por [0,100%] e [75,0%]):

ProbabilidadeOposicións.jpg

Por exemplo, se se estudan só 20 temas, a probabilidade de non saber ningún deles é do 20,16% (é dicir, habería case un 80% de saber algún e, con sabelo ben, aprobar). Con 27 temas ben estudados, a probabilidade de descoñecer o correspondente a tódalas bólas é do 9,92%. Para ter un 50% de probabilidades de aprobar, habería que estudar máis de 9 temas e sabelos ben, pero sempre cómpre estudar cantos máis mellor para mellorar as posibilidades e non confiar só na estatística.