Todas las combinaciones posibles de números. Combinatoria: reglas y fórmulas básicas.

COMBINATARIA

La combinatoria es una rama de las matemáticas que estudia los problemas de seleccionar y organizar elementos de un determinado conjunto básico de acuerdo con reglas dadas. Las fórmulas y principios de la combinatoria se utilizan en la teoría de la probabilidad para calcular la probabilidad de eventos aleatorios y, en consecuencia, obtener leyes de distribución. variables aleatorias. Esto, a su vez, nos permite estudiar los patrones de fenómenos aleatorios masivos, lo cual es muy importante para una correcta comprensión de los patrones estadísticos que se manifiestan en la naturaleza y la tecnología.

Reglas para la suma y multiplicación en combinatoria.

Regla de la suma. Si dos acciones A y B son mutuamente excluyentes, y la acción A se puede realizar de m maneras y la B de n maneras, entonces una de estas acciones (ya sea A o B) se puede realizar de n + m maneras.

Ejemplo 1.

Hay 16 niños y 10 niñas en la clase. ¿De cuántas maneras se puede asignar a un oficial de servicio?

Solución

Se puede asignar el deber a un niño o a una niña, es decir el oficial de turno puede ser cualquiera de los 16 niños o cualquiera de las 10 niñas.

Usando la regla de la suma, encontramos que un oficial de servicio puede ser asignado de 16+10=26 maneras.

Regla del producto. Sean k acciones que deben realizarse secuencialmente. Si la primera acción se puede realizar de n 1 maneras, la segunda acción de n 2 maneras, la tercera de n 3 maneras, y así sucesivamente hasta la k-ésima acción que se puede realizar de n k formas, entonces se pueden realizar todas las k acciones juntas. :

maneras.

Ejemplo 2.

Hay 16 niños y 10 niñas en la clase. ¿De cuántas maneras se pueden nombrar dos oficiales de servicio?

Solución

Se puede designar a un niño o a una niña como primera persona en turno. Porque Hay 16 niños y 10 niñas en la clase, entonces puedes designar a la primera persona de turno de 16+10=26 maneras.

Después de haber elegido al primer oficial de servicio, podemos elegir al segundo entre las 25 personas restantes, es decir 25 maneras.

Según el teorema de la multiplicación, se pueden seleccionar dos asistentes de 26*25=650 formas.

Combinaciones sin repetición. Combinaciones con repeticiones.

Un problema clásico en combinatoria es el problema del número de combinaciones sin repeticiones, cuyo contenido puede expresarse mediante la pregunta: cuántos maneras Poder elegir soy de n elementos diferentes?

Ejemplo 3.

Debes elegir 4 de 10 libros diferentes disponibles para regalar. ¿De cuántas maneras se puede hacer esto?

Solución

Necesitamos elegir 4 libros de 10 y el orden de elección no importa. Por lo tanto, necesitas encontrar el número de combinaciones de 10 elementos de 4:

.

Considere el problema del número de combinaciones con repeticiones: hay r objetos idénticos de cada uno de n varios tipos; cuántos maneras Poder elegir soy de estos (n*r) artículos?

.

Ejemplo 4.

La pastelería vendía 4 tipos de tartas: napoleones, canutillos, galletas de mantequilla y hojaldres. ¿De cuántas maneras puedes comprar 7 pasteles?

Solución

Porque Entre 7 pasteles puede haber pasteles del mismo tipo, entonces el número de formas en las que se pueden comprar 7 pasteles está determinado por el número de combinaciones con repeticiones de 7 a 4.

.

Colocaciones sin repetición. Colocaciones con repeticiones.

Un problema clásico en combinatoria es el problema del número de colocaciones sin repeticiones, cuyo contenido puede expresarse mediante la pregunta: cuántos maneras Poder elegir Y correo Por soy diferente lugares soy de n diferente ¿elementos?

Ejemplo 5.

Algún periódico tiene 12 páginas. Es necesario colocar cuatro fotografías en las páginas de este periódico. ¿De cuántas maneras se puede hacer esto si ninguna página del periódico debe contener más de una fotografía?

Solución.

En esta tarea no nos limitamos a seleccionar fotografías, sino que las colocamos en determinadas páginas del periódico, y cada página del periódico no debe contener más de una fotografía. Así, el problema se reduce al clásico problema de determinar el número de colocaciones sin repeticiones de 12 elementos de 4 elementos:

Así, 4 fotografías en 12 páginas se pueden organizar de 11.880 maneras.

También un problema clásico en combinatoria es el problema del número de ubicaciones con repeticiones, cuyo contenido puede expresarse mediante la pregunta: cuántos maneras Poder Túbejército Y correo Por soy diferente lugares soy de n artículos,Conlisto cual Hay ¿lo mismo?

Ejemplo 6.

El niño tiene sobras del set para juego de mesa sellos con los números 1, 3 y 7. Decidió utilizar estos sellos para poner números de cinco dígitos en todos los libros, para crear un catálogo. ¿Cuántos números diferentes de cinco cifras puede formar un niño?

Permutaciones sin repetición. Permutaciones con repeticiones.

Un problema clásico en combinatoria es el problema del número de permutaciones sin repetición, cuyo contenido puede expresarse mediante la pregunta: cuántos maneras Poder correo norte varios elementos en n diferente ¿lugares?

Ejemplo 7.

¿Cuántas “palabras” de cuatro letras puedes formar con las letras de la palabra “matrimonio”?

Solución

La población general son las 4 letras de la palabra “matrimonio” (b, p, a, k). El número de “palabras” está determinado por las permutaciones de estas 4 letras, es decir

Para el caso en que entre los n elementos seleccionados haya elementos idénticos (selección con retorno), el problema del número de permutaciones con repeticiones se puede expresar mediante la pregunta: ¿De cuántas maneras se pueden reordenar n objetos ubicados en n lugares diferentes si entre n objetos hay k tipos diferentes (k< n), т. е. есть одинаковые предметы.

Ejemplo 8.

¿Cuántas combinaciones de letras diferentes se pueden hacer con las letras de la palabra "Mississippi"?

Solución

Hay 1 letra "m", 4 letras "i", 3 letras "c" y 1 letra "p", para un total de 9 letras. Por lo tanto, el número de permutaciones con repeticiones es igual a

RESUMEN DE ANTECEDENTES DE LA SECCIÓN "COMBINATÓRICA"

Considere el problema de contar el número de muestras de un conjunto dado en vista general. Que haya algún conjunto norte, que consiste en norte elementos. Cualquier subconjunto formado por metro Los elementos se pueden considerar sin tener en cuenta su orden, o tenerlo en cuenta, es decir. al cambiar el orden, pasar a otro metro– muestreo.

Formulemos las siguientes definiciones:

Colocaciones sin repetición

Colocación sin repetición denorte elementos pormetro norteque contienemetrovarios elementos.

De la definición se deduce que las dos disposiciones difieren entre sí, tanto en sus elementos como en su orden, incluso si los elementos son los mismos.

Teorema 3. El número de colocaciones sin repetición es igual al producto. metro factores, el mayor de los cuales es el número norte . Anote:

Permutaciones sin repetición

Permutaciones denorte Los elementos se llaman diferentes ordenamientos del conjunto.norte.

De esta definición se deduce que las dos permutaciones difieren sólo en el orden de los elementos y pueden considerarse como un caso especial de colocaciones.

Teorema 4. El número de permutaciones diferentes sin repetición se calcula mediante la fórmula

Combinaciones sin repeticiones.

Una combinación sin repetición denorte elementos pormetro cualquier subconjunto desordenado de un conjunto se llamanorteque contienemetro varios elementos.

De la definición se deduce que las dos combinaciones se diferencian sólo en los elementos; el orden no es importante.

Teorema 5. El número de combinaciones sin repeticiones se calcula mediante una de las siguientes fórmulas:

Ejemplo 1. Hay 5 sillas en la habitación. ¿De cuántas maneras puedes colocarlos sobre ellos?

a) 7 personas; b) 5 personas; c) 3 personas?

Solución: a) En primer lugar, debes seleccionar 5 personas de 7 para que se sienten en las sillas. Se puede hacer
forma. Con cada elección de cinco específicos, puedes producir
reordenamientos. Según el teorema de la multiplicación, el número requerido de métodos de aterrizaje es igual.

Comentario: El problema se puede resolver utilizando únicamente el teorema del producto, razonando de la siguiente manera: para sentarse en la 1ª silla hay 7 opciones, en la 2ª silla hay 6 opciones, en la 3ª -5, en la 4ª -4 y en la 5- -3. Entonces, el número de formas de sentar a 7 personas en 5 sillas es . Las soluciones por ambos métodos son consistentes, ya que

b) La solución es obvia -

V) - número de elecciones de escaños ocupados.

- el número de asientos para tres personas en tres sillas seleccionadas.

El número total de elecciones es .

No es difícil comprobar las fórmulas.
;

;

El número de todos los subconjuntos de un conjunto que consta de norte elementos.

Repetir ubicaciones

Colocando con repetición denorte elementos pormetro todo subconjunto ordenado de un conjunto se llamanorte, que consiste enmetro elementos para que cualquier elemento pueda incluirse en este subconjunto del 1 almetroveces, o estar ausente por completo.

El número de colocaciones con repetición se denota por y calculado mediante la fórmula, que es consecuencia del teorema de la multiplicación:

Ejemplo 2. Sea N = (a, b, c) un conjunto de tres letras. Llamemos palabra a cualquier conjunto de letras incluidas en este conjunto. Encontremos el número de palabras de longitud 2 que se pueden formar con estas letras:
.

Comentario: Evidentemente, también se pueden considerar colocaciones con repetición cuando
.

Ejemplo 3. Necesitas usar las letras (a, b) para crear todas las palabras posibles de longitud 3. ¿De cuántas maneras se puede hacer esto?

Respuesta:

El primer lugar de una fila puede ser cualquiera de N elementos, por lo tanto, hay N opciones. En segundo lugar, cualquiera, excepto el que ya se ha utilizado para el primer lugar. Por lo tanto, para cada una de las N opciones ya encontradas, hay (N - 1) opciones de segundo lugar, y el número total de combinaciones se convierte en N*(N - 1).
Lo mismo se puede repetir para el resto de elementos de la serie. Para el último lugar sólo queda una opción: el último elemento restante. Para el penúltimo hay dos opciones, y así sucesivamente.
Por lo tanto, para una serie de N elementos que no se repiten, las posibles permutaciones son iguales al producto de todos los números enteros de 1 a N. ¡Este producto se llama N y N! (léase “en factorial”).

En el caso anterior, el número de elementos posibles y el número de lugares en la fila coincidían, y su número era igual a N. Pero es posible una situación en la que en la fila menos lugares que elementos posibles. En otras palabras, el número de elementos de la muestra es igual a un cierto número M, y M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
Primero, es posible que tengas que contar el número total formas posibles, que se puede utilizar para alinear M elementos de N. Dichos métodos de colocación.
En segundo lugar, el investigador puede estar interesado en la cantidad de formas en que se pueden seleccionar M elementos de N. En este caso, el orden de los elementos ya no es importante, pero dos opciones cualesquiera deben diferir entre sí en al menos un elemento. . Estos métodos se denominan combinaciones.

Para encontrar el número de ubicaciones de M elementos a partir de N, se puede recurrir al mismo método de razonamiento que en el caso de las permutaciones. Todavía puede haber N elementos en primer lugar, N - 1 en segundo lugar, y así sucesivamente. Pero para el último lugar la cantidad opciones posibles no es igual a uno, sino (N - M + 1), ya que cuando se complete la colocación, todavía quedarán (N - M) elementos no utilizados.
Así, el número de colocaciones de M elementos de N es igual al producto de todos los números enteros de (N - M + 1) a N, o, lo que es lo mismo, el cociente N!/(N - M)!.

Obviamente, el número de combinaciones de M elementos de N será menor que el número de ubicaciones. ¡Para cada combinación posible hay una M! posibles colocaciones dependiendo del orden de los elementos de esta combinación. Por lo tanto, para encontrar esta cantidad, necesitas dividir el número de ubicaciones de M elementos de N por N!. En otras palabras, el número de combinaciones de M elementos de N es igual a N!/(M!*(N - M)!).

Fuentes:

• número de combinaciones

Factorial número natural es el producto de todos los números naturales anteriores, incluido el número mismo. Factorial cero es igual a uno. Parece que calcular el factorial de un número es muy sencillo: basta con multiplicar todos los números naturales que no excedan el dado. Sin embargo, el valor del factorial aumenta tan rápidamente que algunas calculadoras no pueden realizar esta tarea.

Necesitará

• calculadora, computadora

Instrucciones

Para calcular el factorial de un número natural se multiplica todo, sin exceder el dado. Cada número se cuenta solo una vez. En forma de fórmula, esto se puede escribir de la siguiente manera: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, donde n es un número natural cuyo factorial debe calcularse.
0! se toma igual a uno (0!=1 A medida que aumenta el argumento, el valor del factorial aumenta muy rápidamente, por lo que el habitual (contable), ya para un factorial de 15, puede dar un error en lugar de un. resultado.

Para calcular el factorial de un número natural grande, utilice una calculadora de ingeniería. Es decir, dicha calculadora en el teclado tiene símbolos de funciones matemáticas (cos, sin, √). Escriba el número original en la calculadora y luego haga clic en el botón factorial. Por lo general, un botón como "n!" o de manera similar (en lugar de “n” puede haber “N” o “x”, pero en cualquier caso debe estar presente el signo de exclamación “!” en la designación del factorial).
Para valores grandes del argumento, los resultados del cálculo comienzan a mostrarse en forma "exponencial" (exponencial). Así, por ejemplo, un factorial de 50 se representaría de la forma: 3.0414093201713378043612608166065e+64 (o similar). Para obtener el resultado de los cálculos en la forma habitual, agregue tantos ceros al número mostrado antes del símbolo “e” como se indican después de “e+” (si, por supuesto, hay suficiente espacio).

A veces elegimos entre muchos sin importar el orden. Esta elección se llama combinación . Si juegas a las cartas, por ejemplo, sabrás que en la mayoría de las situaciones el orden en el que tienes las cartas no importa.

Ejemplo 1 Encuentra todas las combinaciones de 3 letras tomadas de un conjunto de 5 letras (A, B, C, D, E).

Solución Estas combinaciones son las siguientes:
(A, B, C), (A, B, D),
(A, B, E), (A, C, D),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B,D,E), (C,D,E).
Hay 10 combinaciones de tres letras elegidas entre cinco letras.

Cuando encontramos todas las combinaciones de un conjunto con 5 objetos, si tomamos 3 objetos a la vez, encontramos todos los subconjuntos de 3 elementos. En este caso no se tiene en cuenta el orden de los objetos. Entonces,
(A, C, B) se llama el mismo conjunto que (A, B, C).

Subconjunto
Un conjunto A es un subconjunto de B, lo que significa que A es un subconjunto de B y/o es igual a B si cada elemento de A es un elemento de B.

Los elementos del subconjunto no están ordenados. Cuando se consideran combinaciones, ¡no se considera el orden!

Combinación
Combinación, que contiene k objetos es un subconjunto que consta de k objetos.

Queremos escribir una fórmula para calcular el número de combinaciones de n objetos si se toman k objetos al mismo tiempo.

Designaciones combinadas
El número de combinaciones de n objetos, si se toman k objetos simultáneamente, se denota n C k .

Llamamos n C k número de combinaciones . Queremos escribir una fórmula general para n C k para cualquier k ≤ n. Primero, es cierto que n C n = 1, porque un conjunto con n elementos tiene sólo un subconjunto con n elementos, que es el conjunto mismo. En segundo lugar, n C 1 = n porque un conjunto con n elementos tiene sólo n subconjuntos con 1 elemento cada uno. Finalmente, n C 0 = 1 porque un conjunto con n elementos tiene solo un subconjunto con 0 elementos, es decir, el conjunto vacío ∅. Para ver otras combinaciones, volvamos al Ejemplo 1 y comparemos el número de combinaciones con el número de permutaciones.

Tenga en cuenta que cada combinación de 3 elementos tiene 6, ¡o 3!, permutaciones.
3! . 5 C 3 = 60 = 5 P 3 = 5. 4 . 3,
entonces
.
En general, el número de combinaciones de k elementos seleccionados entre n objetos, n C k veces las permutaciones de estos elementos k!, debe ser igual al número de permutaciones de n elementos por k elementos:
k!. norte C k = norte P k
norte C k = norte P k /k!
nCk = (1/k!). norte P k
norte C k =

Combinaciones de k objetos de n objetos
El número total de combinaciones de k elementos de n objetos se denota por n C k , determinado por
(1) norte C k = ,
o
(2) norte C k =

Otro tipo de notación para n C k es coeficiente binomial . La razón de esta terminología quedará clara a continuación.

Coeficiente binomial

Ejemplo 2 Calcule usando las fórmulas (1) y (2).

Solución
a) Según (1),
.
b) Según (2),

Tenga en cuenta que n/k no significa.

Ejemplo 3 Calcula y .

Solución Usamos la fórmula (1) para la primera expresión y la fórmula (2) para la segunda. Entonces
,
usando (1), y
,
usando la fórmula (2).

tenga en cuenta que
,
y usando el resultado del ejemplo 2 nos da
.
De ello se deduce que el número de un subconjunto de 5 elementos de un conjunto de 7 elementos es el mismo que el número de un subconjunto de 2 elementos de un conjunto de 7 elementos. Cuando se seleccionan 5 elementos de un conjunto, no incluyen 2 elementos. Para ver esto, considere el conjunto (A, B, C, D, E, F, G):


En general tenemos lo siguiente. Este resultado da forma alternativa Cálculos combinados.

Subconjuntos de tamaño k y tamaño
y n C k = n C n-k
El número de subconjuntos de tamaño k de un conjunto con n objetos es el mismo que el número de subconjuntos de tamaño n - k. El número de combinaciones de k objetos de un conjunto de n objetos es el mismo que el número de combinaciones de n. objetos tomados al mismo tiempo.

Ahora resolveremos problemas con combinaciones.

Ejemplo 4 Lotería de Michigan. La lotería WINFALL de Michigan, que se realiza dos veces por semana, tiene un premio mayor de al menos 2 millones de dólares. Por un dólar, un jugador puede tachar 6 números cualesquiera del 1 al 49. Si estos números coinciden con los sorteados en la lotería, el jugador gana. (