Matemáticas discretas: teoría del conteo

En la vida diaria, muchas veces es necesario averiguar el número de todos los resultados posibles para una serie de eventos. Por ejemplo, ¿de cuántas formas se puede elegir un panel de jueces compuesto por 6 hombres y 4 mujeres entre 50 hombres y 38 mujeres? ¿Cuántos números PAN de 10 letras diferentes se pueden generar de modo que las primeras cinco letras sean letras mayúsculas, las cuatro siguientes sean dígitos y la última sea nuevamente una letra mayúscula? Para resolver estos problemas, se utiliza la teoría matemática del conteo.Counting Abarca principalmente la regla de conteo fundamental, la regla de permutación y la regla de combinación.

Las reglas de suma y producto

los Rule of Sum y Rule of Product se utilizan para descomponer problemas de conteo difíciles en problemas simples.

  • The Rule of Sum- Si una secuencia de tareas $ T_1, T_2, \ dots, T_m $ se puede hacer en $ w_1, w_2, \ dots w_m $ formas respectivamente (la condición es que no se puedan realizar tareas simultáneamente), entonces el número de formas de hacer una de estas tareas es $ w_1 + w_2 + \ dots + w_m $. Si consideramos dos tareas A y B que son inconexas (es decir, $ A \ cap B = \ emptyset $), entonces matemáticamente $ | A \ cup B | = | A | + | B | $

  • The Rule of Product- Si una secuencia de tareas $ T_1, T_2, \ dots, T_m $ se puede hacer en $ w_1, w_2, \ dots w_m $ formas respectivamente y cada tarea llega después de la ocurrencia de la tarea anterior, entonces hay $ w_1 \ times w_2 \ times \ dots \ times w_m $ formas de realizar las tareas. Matemáticamente, si una tarea B llega después de una tarea A, entonces $ | A \ times B | = | A | \ veces | B | $

Ejemplo

Question- Un niño vive en X y quiere ir a la escuela en Z. Desde su casa X, primero debe llegar a Y y luego de Y a Z. Puede ir de X a Y por 3 rutas de autobús o 2 rutas de tren. Desde allí, puede elegir 4 rutas de autobús o 5 rutas de tren para llegar a Z. ¿Cuántas formas hay para ir de X a Z?

Solution- De X a Y, puede ir en $ 3 + 2 = 5 $ formas (Regla de la suma). A partir de entonces, puede ir de Y a Z en $ 4 + 5 = 9 $ formas (Regla de la suma). Por lo tanto, de X a Z puede ir en $ 5 \ veces 9 = 45 $ formas (Regla del producto).

Permutaciones

UNA permutationes una disposición de algunos elementos en los que el orden importa. En otras palabras, una permutación es una combinación ordenada de elementos.

Ejemplos

  • De un conjunto S = {x, y, z} tomando dos a la vez, todas las permutaciones son -

    $ xy, yx, xz, zx, yz, zy $.

  • Tenemos que formar una permutación de números de tres dígitos a partir de un conjunto de números $ S = \ lbrace 1, 2, 3 \ rbrace $. Se formarán diferentes números de tres dígitos cuando organicemos los dígitos. La permutación será = 123, 132, 213, 231, 312, 321

Número de permutaciones

El número de permutaciones de 'n' cosas diferentes tomadas 'r' a la vez se indica con $ n_ {P_ {r}} $

$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$

donde $ n! = 1.2.3. \ puntos (n - 1) .n $

Proof - Que haya 'n' elementos diferentes.

Hay n número de formas de llenar el primer lugar. Después de llenar el primer lugar (n-1) queda un número de elementos. Por lo tanto, hay (n-1) formas de ocupar el segundo lugar. Después de llenar el primer y segundo lugar, queda (n-2) número de elementos. Por tanto, existen (n-2) formas de ocupar el tercer lugar. Ahora podemos generalizar el número de formas de llenar el r-ésimo lugar como [n - (r – 1)] = n – r + 1

Entonces, el total no. de formas de llenar desde el primer lugar hasta el r-ésimo lugar -

$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $

$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ dots 3.2.1] / [(nr) (nr-1) \ dots 3.2.1] $

Por lo tanto,

$ n_ {P_ {r}} = n! / (nr)! $

Algunas fórmulas importantes de permutación

  • Si hay n elementos de los cuales $ a_1 $ son similares de algún tipo, $ a_2 $ son similares de otro tipo; $ a_3 $ son iguales de tercer tipo y así sucesivamente y $ a_r $ son de $ r ^ {th} $ tipo, donde $ (a_1 + a_2 + ... a_r) = n $.

    Entonces, ¡el número de permutaciones de estos n objetos es = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.

  • Número de permutaciones de n elementos distintos que toman n elementos a la vez = $ n_ {P_n} = n! $

  • El número de permutaciones de n elementos diferentes que toman r elementos a la vez, cuando x cosas particulares siempre ocupan lugares definidos = $ n-x_ {p_ {rx}} $

  • El número de permutaciones de n elementos diferentes cuando r cosas especificadas siempre se juntan es - $ r! (n − r + 1)! $

  • El número de permutaciones de n elementos diferentes cuando r cosas especificadas nunca se juntan es - $ n! - [r! (n − r + 1)!] $

  • El número de permutaciones circulares de n elementos diferentes tomados x elementos al tiempo = $ ^ np_ {x} / x $

  • El número de permutaciones circulares de n cosas diferentes = $ ^ np_ {n} / n $

Algunos problemas

Problem 1 - De un montón de 6 cartas diferentes, ¿de cuántas formas podemos permutarlo?

Solution- Como estamos tomando 6 cartas a la vez de una baraja de 6 cartas, la permutación será $ ^ 6P_ {6} = 6! = 720 $

Problem 2 - ¿De cuántas formas se pueden ordenar las letras de la palabra 'LECTOR'?

Solution - Hay 6 letras de palabra (2 E, 1 A, 1D y 2R.) En la palabra 'LECTOR'.

¡La permutación será $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $

Problem 3 - ¿De qué manera se pueden ordenar las letras de la palabra 'NARANJA' de modo que las consonantes ocupen sólo las posiciones pares?

Solution- Hay 3 vocales y 3 consonantes en la palabra 'NARANJA'. Número de formas de ordenar las consonantes entre sí $ = ^ 3P_ {3} = 3! = 6 $. Los 3 lugares vacantes restantes se llenarán con 3 vocales en $ ^ 3P_ {3} = 3! = 6 $ caminos. Por lo tanto, el número total de permutación es $ 6 \ times 6 = 36 $

Combinaciones

UNA combination es la selección de algunos elementos dados en cuyo orden no importa.

El número de todas las combinaciones de n cosas, tomadas r a la vez es -

$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$

Problem 1

Encuentra el número de subconjuntos del conjunto $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ que tiene 3 elementos.

Solution

La cardinalidad del conjunto es 6 y tenemos que elegir 3 elementos del conjunto. Aquí, el orden no importa. Por tanto, el número de subconjuntos será $ ^ 6C_ {3} = 20 $.

Problem 2

Hay 6 hombres y 5 mujeres en una habitación. ¿De cuántas formas podemos elegir 3 hombres y 2 mujeres de la habitación?

Solution

La cantidad de formas de elegir 3 hombres de 6 hombres es $ ^ 6C_ {3} $ y la cantidad de formas de elegir 2 mujeres de 5 mujeres es $ ^ 5C_ {2} $

Por lo tanto, el número total de vías es - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $

Problem 3

¿De cuántas formas puede elegir 3 grupos distintos de 3 estudiantes de un total de 9 estudiantes?

Solution

Numeremos los grupos como 1, 2 y 3

Para elegir 3 estudiantes para el primer grupo, el número de formas - $ ^ 9C_ {3} $

El número de formas de elegir 3 estudiantes para el 2º grupo después de elegir el 1º grupo - $ ^ 6C_ {3} $

El número de formas para la elección de 3 estudiantes de 3 er grupo después de la elección de 1 st y 2 nd grupo - $ ^ {3} 3C_ $

Por lo tanto, el número total de formas $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $

Identidad de Pascal

Identidad de Pascal, primera derivada por Blaise Pascal en 17 º siglo, los estados que el número de maneras para elegir k elementos de n elementos es igual a la suma de número de maneras para elegir elementos (k-1) de (1 n-) elementos y el número de formas de elegir elementos de n-1 elementos.

Matemáticamente, para cualquier entero positivo kyn: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $

Proof -

$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$

$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! PS

$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $

$ = (n-1)! \ frac {n} {k! (nk)! PS

$ = \ frac {n! } {k! (nk)! PS

$ = n_ {C_ {k}} $

Principio del casillero

En 1834, el matemático alemán Peter Gustav Lejeune Dirichlet estableció un principio al que llamó principio del cajón. Ahora, se conoce como el principio del casillero.

Pigeonhole Principleestablece que si hay menos casilleros que el número total de palomas y cada paloma se coloca en un casillero, entonces debe haber al menos un casillero con más de una paloma. Si se ponen n palomas en m casilleros donde n> m, hay un hoyo con más de una paloma.

Ejemplos

  • Diez hombres están en una habitación y participan en un apretón de manos. Si cada persona da la mano al menos una vez y ningún hombre da la mano al mismo hombre más de una vez, entonces dos hombres participaron en el mismo número de apretones de manos.

  • Debe haber al menos dos personas en una clase de 30 cuyos nombres comiencen con el mismo alfabeto.

El principio de inclusión-exclusión

los Inclusion-exclusion principlecalcula el número cardinal de la unión de múltiples conjuntos no disjuntos. Para dos conjuntos A y B, el principio establece:

$ | A \ taza B | = | A | + | B | - | A \ cap B | $

Para tres conjuntos A, B y C, el principio establece:

$ | A \ taza B \ taza C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $

La fórmula generalizada -

$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limits_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limits_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $

Problem 1

¿Cuántos números enteros del 1 al 50 son múltiplos de 2 o 3 pero no ambos?

Solution

Del 1 al 100, hay $ 50/2 = 25 $ números que son múltiplos de 2.

Hay $ 50/3 = 16 $ números que son múltiplos de 3.

Hay $ 50/6 = 8 $ números que son múltiplos de 2 y 3.

Entonces, $ | A | = 25 $, $ | B | = 16 $ y $ | A \ cap B | = 8 $.

$ | A \ taza B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $

Problem 2

En un grupo de 50 estudiantes, a 24 les gustan las bebidas frías ya 36 les gustan las bebidas calientes y a cada estudiante le gusta al menos una de las dos bebidas. ¿A cuántos les gusta tanto el café como el té?

Solution

Sea X el conjunto de estudiantes a los que les gustan las bebidas frías e Y sea el conjunto de personas a las que les gustan las bebidas calientes.

Entonces, $ | X \ cup Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $

$ | X \ cap Y | = | X | + | Y | - | X \ taza Y | = 24 + 36 - 50 = 60 - 50 = 10 $

Por lo tanto, hay 10 estudiantes a los que les gusta tanto el té como el café.