Combinatoria

Na Galipedia, a wikipedia en galego.

Índice

[editar] Definición

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 ubicalos nun número determinado de lugares ou posicións (p) [por exemplo, as posibles ubicació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.

[editar] Xeralidades

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 ordeada = con orde e non ordeada = sen orde;
  3. Coincide que o número de experimentos aleatorios realizado (p) é igual ó número de elementos escollidos ou ubicados (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;

[editar] Exemplo de caracterización

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 é ordeado;
  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.

[editar] Posibilidades da análise

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. Eis 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