COMBINACION Y PERMUTACION

Combinación (desambiguación)

El término combinación puede referirse a:

• Coeficiente binomial, en combinatoria, son números que determinan el número de formas de seleccionar elementos de un conjunto y aparecen en la expansión binomial;

• Combinación lineal, como suma de vectores;

• Combinación química, como un compuesto químico;

• Combinación, como estrategia en el ajedrez.

• Coeficiente binomial

Los coeficientes binomiales, números combinatorios o combinacionesnota 1 son números estudiados en combinatoria que corresponden al número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado. Sin embargo, dependiendo del enfoque que tenga la exposición, se pueden usar otras definiciones equivalentes.

Definición combinatoria

, pues hay 10 formas de escoger (en rojo) 3 objetos a partir de un conjunto con 5 elementos

Se tiene un conjunto con 6 objetos diferentes {A,B,C,D,E,F}, de los cuales se desea escoger 2 (sin importar el orden de elección). Existen 15 formas de efectuar tal elección:

A,B A,C A,D A,E A,F

B,C B,D B,E B,F

C,D C,E C,F

D,E D,F

E,F

El número de formas de escoger k elementos a partir de un conjunto de n, puede denotarse de varias formas:nota 2 , , , o . Así, en el ejemplo anterior se tiene entonces que C(6,2)=15, puesto que hay 15 formas de escoger 2 objetos a partir de un conjunto con 6 elementos.

Los números C(n,k) se conocen como «coeficientes binomiales», pero es frecuente referirse a ellos como «combinaciones de n en k», o simplemente «n en k». Por tanto, la primera definición es:

El coeficiente binomial es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

Es importante notar que la definición asume implícitamente que n y k son naturales, y que además k no excede a n. Podemos definir C(n,k)=0 si k>n, puesto que no es posible escoger más elementos que los que tiene el conjunto dado (por tanto hay cero formas de hacer la elección). Estas precisiones cobrarán relevancia más adelante cuando se discutan generalizaciones del concepto (por ejemplo, cuando n o k sean negativos o cuando no sean números enteros).

[editar] Definición algebraica

Hay 5×4×3 formas de escoger ordenadamente 3 objetos de un conjunto con 5.

La definición no permite calcular el valor de los coeficientes binomiales, salvo listando los subconjuntos y contándolos. Sin embargo, existe una fórmula explícita que nos proporciona el valor de C(n,k).

Supongamos que el conjunto original tiene 5 elementos, de los cuales se deben escoger 3. Al momento de escoger el primero, se tiene 5 opciones disponibles, pero una vez fijo el primero, sólo hay 4 opciones para el segundo, y por tanto sólo 3 opciones para el último (pues no se puede repetir los escogidos en los primeros 2 pasos). De este modo, la selección puede hacerse de 5×4×3=60 formas.

Sin embargo, en tal conteo, el orden en que se escogen los elementos hace diferencia. Por ejemplo, tomar C, luego B, luego E, es una selección diferente de tomar B, luego C y luego E. Pero en la definición de coeficiente binomial, no importa el orden en que se eligen los objetos, únicamente cuáles se escogen. Por tanto, las elecciones BCE, BEC, CEB, CBE, ECB y EBC son todas equivalentes. Del mismo modo, las elecciones ABC, ACB, BCA, BAC, CAB y CBA son equivalentes, y así para cualquier terna de letras.

De esta forma, el resultado obtenido (60) no es la cantidad de subconjuntos de 3 elementos de {A,B,C,D,E}, sino que cada subconjunto está contado 6 veces, por lo que la cantidad de subconjuntos es realmente 60/6 = 10.

El argumento presentado para el ejemplo puede generalizarse de la siguiente forma. Si se tiene un conjunto con n elementos, de los cuales se van a escoger k de ellos, la elección (ordenada) puede hacerse de

n × (n-1) × (n-2) ×... × (n-k+1)

ya que en el primer paso se tienen n opciones, en el segundo se tienen n-1, en el tercero n-2, y así sucesivamente, terminando en el paso k que tendrá n-k+1 opciones.

Ahora, hay que dividir el producto anterior entre el número de selecciones «equivalentes». Pero si se tiene k objetos, hay k! formas de permutarlos, es decir, k! formas de listarlos en distinto orden. Recordemos que k! se lee k-factorial y es igual a

k! = 1×2×3×...× k

Concluimos que el número de subconjuntos con k elementos, escogidos de un conjunto con n elementos es

.

Multiplicando el numerador y el denominador de la fracción por 1×2×3ו••×(n-k)

La expresión anterior puede escribirse de forma más compacta usando factoriales, expresión que es usada en ocasiones como la definición misma de coeficiente binomial (sobre todo en textos elementales que no explican el origen combinatorio de la misma):

El coeficiente binomial está dado por la fórmula

El teorema de binomio y coeficientes binomiales

Finalmente, existe una tercera forma de definir los coeficientes binomiales, la cual da origen a su nombre. Sin embargo, esta definición obscurece el significado combinatorio de los números, pues la equivalencia con las definiciones anteriores no es evidente.

El coeficiente binomial es el coeficiente del término obtenido al desarrollar

Combinación lineal

Un vector se dice que es combinación lineal de un conjunto de vectores si existe una forma de expresarlo como suma de parte o todos los vectores de multiplicados cada uno de ellos por un coeficiente escalar , de forma que:

.

Así, es combinación lineal de vectores de si podemos expresar como una suma de múltiplos de una cantidad finita de elementos de .

Ejemplo: . Se dice que es combinación lineal de y de , porque podemos escribir sin más que despejar la . De la misma manera, despejando oportunamente, cada una de estas variables se podría expresar como combinación lineal de las otras dos.

En otras palabras, cuánto de cada vector del conjunto necesito para que, cuando se combinen linealmente dichos elementos , pueda formar al vector en cuestión.

[editar] Expansión lineal

Dado un conjunto de vectores , finito o infinito, se llama expansión lineal, denotada como al conjunto:

Dicho conjunto es el mínimo subespacio vectorial de que contiene al conjunto .

COMBINACION Y PERMUTACION CON REMPLAZO

una permutación es tomar ciertos objetos... digamos n y revolverlos, es decir, importa el orden y así por ejemplo si tomamos el conjunto {1,2,3,4}

las siguientes dos permutaciones son diferentes:

...