Combinatoria

CAPITULO 12.- ANALISIS COMBINATORIO SIMPLE El ANALISIS COMBINATORIO exige el conocimiento de ciertas reglas y métodos para determinar el número o la manera de formar diferentes grupos con los elementos de un conjunto. Nos ocuparemos entonces de la correcta aplicación de tales reglas y procedimientos, como así también de la definición de algunos símbolos que nos servirán en el desarrollo de estecapítulo. I.- El símbolo de sumatoria: permite abreviar la notación de una suma cuyos términos admiten cierta ley de formación. Por ejemplo, para indicar la suma: a1 + a2 + a3 + a4 + a5 + a6 + a7 escribimos:

åa
i=1

7

i

y se lee, sumatoria de ai con i variando de 1 a 7.

Si el índice i es variable desde 1 a n, la notación es:

åa
i=1

n

i

y significa la suma abreviada delos n términos: a1 + a2 + a3 + ... + an.

El desarrollo de una sumatoria se obtiene asignando a i, cada uno de los sucesivos valores de su rango de variación y sumando los términos así obtenidos. Ejemplo 1:

åi =
2 i=1

4

12

+

22

+

32

+

42

II.- Factorial de un número: el factorial de un número natural n mayor que uno (1) es igual al producto de los n primeros númerosnaturales; el símbolo característico es "!". Ejemplo 2: n! = 1.2.3.4...n n! = n(n-1)(n-2)...3.2.1 De la definición se deduce que el factorial de un número es igual al producto de dicho número por el factorial del anterior. Ejemplo 3: 6! = 6.5! = 6.5.4! En general: n (n-1)! = n! Además se define: 0! = 1 y 1! = 1. o bien

Arreglos Definición: Se llama arreglo de orden n, a todo subconjuntoordenado de n elementos elegidos de un conjunto que contiene m elementos. La definición establece que dos arreglos son distintos cuando difieren en algún elemento o, si tienen los mismos, cuando difieren en el orden en que se encuentran. Al número de arreglos se lo indicará con Am,n o bien Vm,n y se lee "arreglos de m en n" o “variaciones de m en n”. Para obtener la fórmula que nos permita calcular elnúmero de arreglos, consideraremos el siguiente ejemplo: Tomemos el conjunto M = {1,2,3,4,5} formado por cinco elementos y obtengamos: A5,1 ; A5,2 ; A5,3. Para n = 1 son: 1; 2; 3; 4; 5. A5,1 = 5 Para n = 2. Colocamos en columna los arreglos de orden 1 y agregamos a la derecha de cada uno un elemento de M de tal manera que no se repita. (o sea no puede ser 11 , 22 , 33, etc) 12 21 31 41 51 13 23 32 4252 14 24 34 43 53 15 25 35 45 54

A5,2 = 5.(5-1) = 20

Para n = 3 procederemos de igual manera que en el caso anterior: 123 124 125 132 134 135 142 143 145 152 153 154 213 214 215 231 234 235 241 243 245 251 253 254 312 314 315 321 324 325 341 342 345 351 352 354 412 413 415 421 423 425 431 432 435 451 452 453 512 513 514 521 523 524 531 532 534 541 542 543

A5,3 = 5.(5-1).(5-2) = 60Estos 60 subconjuntos se lograron agregando a cada uno de los arreglos binarios obtenidos anteriormente, los elementos faltantes. Aprovechando lo analizado, obtendremos una fórmula que nos permita determinar rápidamente el número de arreglos en cualquier situación. El método utilizado permite calcular el número de arreglos de un cierto orden, conociendo el del orden anterior, es decir:

Am,1 = mAm,2 = Am,1 (m-1) Am,3 = Am,2 (m-2) Am,4 = Am,3 (m-3) .... .......... Am,n-2 = Am,n-3 (m-n+3) Am,n-1 = Am,n-2 (m-n+2) Am,n = Am.n-1 (m-n+1) Multiplicando miembro a miembro estas igualdades y simplificando los factores comunes, resulta la siguiente expresión: Am,n = m (m-1) (m-2) (m-3) ... (m-n+3) (m-n+2) (m-n+1) Es decir: el número de arreglos de m elementos tomados de n en n es igual al productode n factores consecutivos decrecientes, comenzando con m. Ejemplo 4: A5,3 = 5 . 4 . 3 = 60 Ejemplo 5: Cuatro personas ascienden a un colectivo en el que hay seis asientos disponibles, ¿de cuántas maneras diferentes pueden sentarse?. Se trata de determinar el número de arreglos que se pueden formar con 6 objetos diferentes tomando cuatro a un mismo tiempo. Es decir calculamos: A6,4 = 6.5.4.3 =...