Elementos de combinatoria. Elementos de combinatoria Número de colocaciones de n elementos por m

La combinatoria es una rama de las matemáticas dedicada a resolver problemas de elección y disposición de elementos de un determinado conjunto de acuerdo con reglas dadas. La combinatoria estudia combinaciones y permutaciones de objetos, la disposición de elementos que tienen propiedades específicas. Una pregunta común en los problemas combinatorios es: ¿de cuántas maneras…?

Los problemas combinatorios también incluyen problemas de construcción de cuadrados mágicos, problemas de decodificación y codificación.

El nacimiento de la combinatoria como rama de las matemáticas está asociado con los trabajos de los grandes matemáticos franceses del siglo XVII Blaise Pascal (1623-1662) y Pierre Fermat (1601-1665) sobre la teoría del juego. Estos trabajos contenían principios para determinar el número de combinaciones de elementos de un conjunto finito. Desde los años 50 del siglo XX, el interés por la combinatoria ha revivido debido al rápido desarrollo de la cibernética.

Las reglas básicas de la combinatoria son regla de la suma Y regla obras.

Regla de la suma

Si se puede seleccionar algún elemento A norte maneras, y el elemento B se puede seleccionar metro maneras, entonces se puede elegir “A o B” norte+ metro maneras.

Por ejemplo, si hay 5 manzanas y 6 peras en un plato, entonces se puede elegir una fruta de 5 + 6 = 11 maneras.

Regla del producto

Si se puede seleccionar el elemento A norte maneras, y el elemento B se puede seleccionar metro maneras, entonces se puede seleccionar un par A y B norte metro maneras.

Por ejemplo, si hay 2 sobres diferentes y 3 sellos diferentes, entonces puedes elegir el sobre y el sello de 6 maneras (2 3 = 6).

La regla del producto también es cierta cuando se consideran elementos de varios conjuntos.

Por ejemplo, si hay 2 sobres diferentes, 3 sellos diferentes y 4 postales diferentes, entonces puedes elegir el sobre, el sello y la postal de 24 maneras (2 3 4 = 24).

Producto de todos números naturales del 1 al n inclusive se llama n - factorial y se denota con el símbolo n.

¡norte! = 1 2 3 4… norte.

Por ejemplo, ¡5! = 1 2 3 4 5 = 120.

Por ejemplo, si hay 3 bolas: roja, azul y verde, puedes ponerlas en fila de 6 maneras (3 2 1 = 3! = 6).

A veces un problema combinatorio se resuelve construyendo árbol opciones posibles.

Por ejemplo, resolvamos el problema anterior sobre 3 bolas construyendo un árbol.

Taller de resolución de problemas en combinatoria.

RETOS y soluciones

1. Hay 6 manzanas, 5 peras y 4 ciruelas en un jarrón. ¿Cuántas opciones hay para elegir una fruta?

Respuesta: 15 opciones.

2. ¿Cuántas opciones hay para comprar una rosa si venden 3 rosas escarlatas, 2 escarlatas y 4 amarillas?

Respuesta: 9 opciones.

3. Cinco caminos van de la ciudad A a la ciudad B, y tres caminos van de la ciudad B a la ciudad C. ¿Cuántos caminos a través de B conducen de A a C?

Respuesta: 15 formas.

4. ¿De cuántas maneras puedes formar un par de una vocal y una consonante de la palabra “bufanda”?

vocales: a, o – 2 uds.
consonantes: p, l, t, k – 4 piezas.

Respuesta: 8 formas.

5. ¿Cuántas parejas de baile se pueden formar con 8 niños y 6 niñas?

Respuesta: 48 pares.

6. En el comedor hay 4 primeros platos y 7 segundos platos. Cuántos varias opciones¿Puedo pedir un almuerzo de dos platos?

Respuesta: 28 opciones.

7. ¿Cuántos números diferentes de dos dígitos se pueden formar usando los números 1, 4 y 7 si los números se pueden repetir?

1 dígito – 3 formas
2 dígitos – 3 vías
3 dígitos – 3 vías

Respuesta: 9 números diferentes de dos dígitos.

8. ¿Cuántos números diferentes de tres dígitos se pueden formar usando los números 3 y 5, si los números se pueden repetir?

1 dígito – 2 vías
2do dígito – 2 vías
3er dígito – 2 vías

Respuesta: 8 números diferentes.

9. ¿Cuántos números diferentes de dos dígitos se pueden formar a partir de los dígitos 0, 1, 2, 3, si los dígitos se pueden repetir?

1 dígito – 3 formas
2 dígitos – 4 vías

Respuesta: 12 números diferentes.

10. ¿Cuántos números de tres dígitos hay en los que todos los dígitos son pares?

Números pares: 0, 2, 4, 6, 8.

1 dígito – 4 vías
2 dígitos – 5 vías
3 dígitos – 5 formas

Respuesta: Hay 100 números.

11. ¿Cuántos números pares de tres cifras hay?

1 dígito – 9 formas (1, 2, 3, 4, 5, 6, 7, 8, 9)
2do dígito – 10 formas (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
3er dígito – 5 formas (0, 2, 4, 6, 8)

9 10 5 = 450

Respuesta: Hay 450 números.

12. ¿Cuántos números diferentes de tres dígitos se pueden formar a partir de tres dígitos diferentes 4, 5, 6?

1 dígito – 3 formas
2do dígito – 2 vías
3 dígitos - 1 vía

Respuesta: 6 números diferentes.

13. ¿De cuántas maneras puedes designar los vértices de un triángulo usando las letras A, B, C, D?

1 pico - 4 vías
2 cumbre - 3 caminos
3 arriba - 2 vías

Respuesta: 24 formas.

14. ¿Cuántos números diferentes de tres dígitos se pueden formar a partir de los dígitos 1, 2, 3, 4, 5, siempre que no se repita ni un solo dígito?

1 dígito – 5 formas
2 dígitos – 4 vías
3 dígitos – 3 vías

Respuesta: 60 números diferentes.

15. ¿Cuántos números diferentes de tres dígitos menores que 400 se pueden formar a partir de los dígitos 1, 3, 5, 7, 9, si alguno de estos dígitos se puede usar solo una vez?

1 dígito – 2 vías
2 dígitos – 4 vías
3 dígitos – 3 vías

Respuesta: 24 números diferentes.

16. ¿De cuántas maneras se puede hacer una bandera, formada por tres franjas horizontales de diferentes colores, si hay material de seis colores?

1 carril – 6 vías
2 carriles – 5 vías
3 carriles – 4 vías

Respuesta: 120 formas.

17. Se seleccionan de la clase 8 personas con los mejores resultados en carrera. ¿De cuántas maneras pueden formar un equipo de tres personas para participar en una carrera de relevos?

1 persona – 8 vías
2 personas – 7 vías
3 personas – 6 vías

Respuesta: 336 formas.

18. El jueves en primer grado debería haber cuatro lecciones: escritura, lectura, matemáticas y educación física. ¿Cuántas opciones de horarios diferentes puedes crear para este día?

1 lección – 4 maneras
Lección 2 – 3 maneras
Lección 3 – 2 maneras
Lección 4 – método 1

4 3 2 1 = 24

Respuesta: 24 opciones.

19. En quinto grado se estudian 8 materias. ¿Cuántas opciones de horarios diferentes se pueden crear para el lunes, si ese día debería haber 5 lecciones y todas las lecciones son diferentes?

1 lección – 8 opciones
Lección 2 – 7 opciones
Lección 3 – 6 opciones
Lección 4 – 5 opciones
Lección 5 – 4 opciones

8 7 6 5 4 = 6720

Respuesta: 6720 opciones.

20. El código de la caja fuerte se compone de cinco números diferentes. ¿Cuántas opciones diferentes para crear un cifrado?

1 dígito – 5 formas
2 dígitos – 4 vías
3 dígitos – 3 vías
4 dígitos - 2 vías
5 dígitos - 1 vía

5 4 3 2 1 = 120

Respuesta: 120 opciones.

21. ¿De cuántas maneras se pueden sentar 6 personas en una mesa con 6 cubiertos?

6 5 4 3 2 1 = 720

Respuesta: 720 formas.

22. ¿Cuántos números de teléfono de siete dígitos se pueden crear si excluye los números que comienzan con cero y 9?

1 dígito - 8 formas
2 dígitos - 10 formas
3 dígitos - 10 formas
4 dígitos – 10 formas
5 dígitos – 10 formas
6 dígitos – 10 formas
7 dígitos – 10 formas

8 10 10 10 10 10 10 = 8.000.000

Respuesta: 8.000.000 de opciones.

23. La central telefónica atiende a suscriptores cuyos números de teléfono constan de 7 dígitos y comienzan con 394. ¿Para cuántos suscriptores está diseñada esta estación?

Número de teléfono 394

10 10 10 10 = 10.000

Respuesta: 10.000 suscriptores.

24. Hay 6 pares de guantes de diferentes tamaños. ¿De cuántas maneras se puede elegir entre ellos un guante para la mano izquierda y un guante para la mano derecha de modo que estos guantes sean de diferentes tamaños?

Guantes izquierdos - 6 formas
Guantes derechos: 5 formas (el sexto guante es del mismo tamaño que el izquierdo)

Respuesta: 30 formas.

25. Los números 1, 2, 3, 4, 5 forman números de cinco cifras en los que todas las cifras son diferentes. ¿Cuántos números pares hay?

5to dígito – 2 vías (dos dígitos pares)
4 dígitos – 4 vías
3 dígitos – 3 vías
2do dígito – 2 vías
1 dígito – 1 vía

2 4 3 2 1 = 48

Respuesta: 48 números pares.

26. ¿Cuántos números de cuatro cifras hay, formados por cifras impares y divisibles por 5?

Números impares: 1, 3, 5, 7, 9.
De estos, se dividen en 5 – 5.

4 dígitos – 1 vía (dígito 5)
3 dígitos – 4 vías
2 dígitos – 3 vías
1 dígito – 2 vías

1 4 3 2 = 24

Respuesta: 24.

27. ¿Cuántos números de cinco cifras hay en los que la tercera cifra es 7 y la última cifra es par?

1 dígito – 9 formas (todas excepto 0)
2 dígitos - 10 formas
3 dígitos – 1 vía (dígito 7)
4 dígitos – 10 formas
5 dígitos – 5 formas (0, 2, 4, 6, 8)

9 10 1 10 5 = 4500

Respuesta: 4500 números.

28. ¿Cuántos números de seis cifras hay en los que la segunda cifra es 2, la cuarta es 4, la sexta es 6 y todos los demás son impares?

1 dígito – 5 opciones (de 1, 3, 5, 7, 9)
2 dígitos – 1 opción (dígito 2)
3er dígito – 5 opciones
4 dígitos – 1 opción (dígito 4)
5 dígitos – 5 opciones
6 dígitos – 1 opción (dígito 6)

5 1 5 1 5 1 = 125

Respuesta: 125 números.

29. ¿Cuántos números diferentes menores que un millón se pueden escribir usando los números 8 y 9?

Un solo dígito – 2
Dos dígitos – 2 2 = 4
Números de tres dígitos – 2 2 2 = 8
Números de cuatro dígitos – 2 2 2 2 =16
Cinco dígitos – 2 2 2 2 2 = 32
Números de seis dígitos – 2 2 2 2 2 2 = 64

Total: 2 + 4 + 8 + 16 + 32 + 64 = 126

Respuesta: 126 números.

30. Hay 11 personas en el equipo de fútbol. Debes elegir un capitán y su adjunto. ¿De cuántas maneras se puede hacer esto?

Capitán - 11 formas
Diputado - 10 formas

Respuesta: 110 formas.

31.Hay 30 personas en la clase. ¿De cuántas maneras se puede elegir al jefe y al responsable de los billetes de viaje?

Jefe - 30 maneras
Respuesta. para billetes - 29 vías

Respuesta: 870 formas.

32. En la caminata participan 12 niños, 10 niñas y 2 profesores. ¿Cuántas opciones para grupos de tres personas de turno (1 niño, 1 niña, 1 profesora) se pueden formar?

12 10 2 = 240

Respuesta: 240 formas.

33. ¿Cuántas combinaciones de cuatro letras del alfabeto ruso (solo hay 33 letras en el alfabeto) se pueden hacer, siempre que 2 letras adyacentes sean diferentes?

Respuesta: 24 .

Sin embargo, muchos problemas se pueden resolver de forma más rápida y sencilla. Para hacer esto, necesita conocer las combinaciones más simples que se pueden hacer a partir de elementos de un conjunto finito.

Y una de las primeras combinaciones de este tipo es permutaciones.

Consideremos ejemplo.

Hay tres libros. Designémoslos con letras. a , b Y C .Estos libros deben colocarse en el estante de diferentes maneras:

Abcon y conb, bcomo,bcon un, con unb, ConbA.

Cada una de estas disposiciones se denomina permutación de tres elementos.

Una permutación de n elementos es cada disposición de estos elementos en un orden específico.

Designado: R norte = norte ! ( norte factorial).

¡norte! =.

Por ejemplo: 3! =
, 1! = 1.

Por tanto, el problema con los libros se puede solucionar así:

P 3 =
.

Tarea número 1.

¿De cuántas maneras caben 4 personas en un banco de cuatro plazas?

P 4 =

Tarea número 2.

¿Cuántos números diferentes de cuatro dígitos en los que los dígitos no se repiten se pueden formar a partir de los números 0,2, 4,6?

Solución: a partir de los números 0,2.4.6 puedes hacer permutaciones de P 4. De este número es necesario excluir aquellas permutaciones que comienzan desde 0.

El número de tales permutaciones es P 3. Esto significa que el número requerido de números de cuatro dígitos que se pueden componer a partir de los números 0,2,4,6 es igual a:

P 4 - P 3 = 4!-3! = Respuesta: 18.

Tarea número 3.

Hay 9 libros diferentes, cuatro de los cuales son libros de texto.

¿De cuántas maneras se pueden ordenar los libros en un estante para que todos los libros de texto estén uno al lado del otro?

Solución: Primero, consideraremos los libros de texto como un solo libro. Entonces necesitas colocar no 9, sino 6 libros en el estante. Esto se puede hacer de 6 maneras.

Y en cada una de las combinaciones resultantes se pueden realizar permutaciones P 4 de libros de texto. Esto significa que el número requerido de formas de ordenar los libros es igual al producto: P 6 * P 4 =

Tarea número 4.

El horario del lunes tiene seis lecciones: álgebra, geometría, biología, historia, educación física, química.

¿De cuántas maneras se puede organizar el horario de lecciones de este día de modo que dos lecciones de matemáticas estén una al lado de la otra?

Solución: P6 *P2=

Respuesta: 1440.

El segundo tipo de combinaciones son colocación.

Que haya 4 bolas y 3 celdas vacías. Designemos las bolas con letras. a , b , C , d .

Tres bolas de este juego se pueden colocar en celdas vacías de diferentes maneras. .

etc. Cada triplete ordenado que puede estar compuesto por cuatro elementos se llama disposición de cuatro elementos de tres en tres y se denota como A.

De la tabla compilada se puede ver que existen 24 combinaciones de este tipo.

Alojamiento desde norte elementos por k ( norte k ) es cualquier conjunto formado por k elementos tomados en un orden específico de los datos norte elementos y se denota A .

Y no es necesario crear diagramas o tablas cada vez. Basta conocer la fórmula:

Si las ubicaciones se componen de n elementos por n, entonces A

La combinatoria es una rama de las matemáticas que estudia cuestiones sobre cuántas combinaciones diferentes, sujetas a ciertas condiciones, se pueden hacer a partir de objetos determinados. Los conceptos básicos de la combinatoria son muy importantes para estimar las probabilidades de eventos aleatorios, porque Son ellos los que nos permiten calcular el número fundamentalmente posible de escenarios diferentes para el desarrollo de eventos.

Fórmula básica de combinatoria.

Sean k grupos de elementos, y i-ésimo grupo consta de n i elementos. Seleccionemos un elemento de cada grupo. Entonces, el número total N de formas en que se puede hacer tal elección está determinado por la relación N=n 1 *n 2 *n 3 *...*n k .

Ejemplo 1. Expliquemos esta regla con un ejemplo sencillo. Sean dos grupos de elementos, y el primer grupo consta de n 1 elementos y el segundo, de n 2 elementos. ¿Cuántos pares diferentes de elementos se pueden formar a partir de estos dos grupos, de modo que el par contenga un elemento de cada grupo? Digamos que tomamos el primer elemento del primer grupo y, sin cambiarlo, pasamos por todos los pares posibles, cambiando solo los elementos del segundo grupo. Puede haber n 2 pares de este tipo para este elemento. Luego tomamos el segundo elemento del primer grupo y también le hacemos todos los pares posibles. También habrá n 2 de esos pares. Dado que solo hay n 1 elementos en el primer grupo, el total de opciones posibles será n 1 *n 2.

Ejemplo 2.¿Cuántos números pares de tres cifras se pueden formar con los dígitos 0, 1, 2, 3, 4, 5, 6, si los dígitos se pueden repetir?
Solución: n 1 =6 (porque puedes tomar cualquier número de 1, 2, 3, 4, 5, 6 como primer dígito), n 2 =7 (porque puedes tomar cualquier número de 0 como segundo dígito, 1, 2 , 3, 4, 5, 6), n 3 =4 (ya que cualquier número entre 0, 2, 4, 6 se puede tomar como tercer dígito).
Entonces, N=n 1 *n 2 *n 3 =6*7*4=168.

En el caso de que todos los grupos estén formados por el mismo numero elementos, es decir n 1 =n 2 =...n k =n podemos suponer que cada selección se realiza del mismo grupo y que el elemento después de la selección se devuelve al grupo. Entonces el número de todos los métodos de selección es n k . Este método de selección en combinatoria se llama muestras con devolución.

Ejemplo 3.¿Cuántos números de cuatro cifras se pueden formar con los dígitos 1, 5, 6, 7, 8?
Solución. Para cada dígito de un número de cuatro cifras hay cinco posibilidades, lo que significa N=5*5*5*5=5 4 =625.

Considere un conjunto que consta de n elementos. En combinatoria este conjunto se llama población general.

Número de colocaciones de n elementos por m

Definición 1. Alojamiento desde norte elementos por metro en combinatoria cualquier conjunto ordenado de metro diversos elementos seleccionados de la población en norte elementos.

Ejemplo 4. Diferentes disposiciones de tres elementos (1, 2, 3) por dos serán los conjuntos (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2 ). Las ubicaciones pueden diferir entre sí tanto en elementos como en su orden.

El número de ubicaciones en combinatoria se denota por A n m y se calcula mediante la fórmula:

Comentario: n!=1*2*3*...*n (léase: “en factorial”), además, se supone que 0!=1.

Ejemplo 5. ¿Cuántos números de dos cifras hay en los que la cifra de las decenas y la de las unidades son distintas e impares?
Solución: porque Si hay cinco dígitos impares, es decir, 1, 3, 5, 7, 9, entonces esta tarea se reduce a seleccionar y colocar dos de los cinco dígitos diferentes en dos posiciones diferentes, es decir. los números dados serán:

Definición 2. Combinación de norte elementos por metro en combinatoria se llama cualquier conjunto desordenado de metro diversos elementos seleccionados de la población general en norte elementos.

Ejemplo 6. Para el conjunto (1, 2, 3), las combinaciones son (1, 2), (1, 3), (2, 3).

Número de combinaciones de n elementos por m

El número de combinaciones se denota por C n m y se calcula mediante la fórmula:

Ejemplo 7.¿De cuántas maneras puede un lector elegir dos libros de seis disponibles?

Solución: El número de métodos es igual al número de combinaciones de seis libros de dos, es decir es igual a:

Permutaciones de n elementos

Definición 3. Permutación de norte Los elementos se llaman cualquiera. conjunto ordenado estos elementos.

Ejemplo 7a. Todas las permutaciones posibles de un conjunto formado por tres elementos (1, 2, 3) son: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2).

El número de permutaciones diferentes de n elementos se denota por P n y se calcula mediante la fórmula P n =n!.

Ejemplo 8.¿De cuántas maneras se pueden ordenar siete libros de diferentes autores en una fila en un estante?

Solución: Este problema trata sobre el número de permutaciones de siete libros diferentes. Hay P 7 =7!=1*2*3*4*5*6*7=5040 formas de organizar los libros.

Discusión. Vemos que el número de combinaciones posibles se puede calcular según diferentes reglas (permutaciones, combinaciones, ubicaciones) y el resultado será diferente, porque El principio de cálculo y las fórmulas mismas son diferentes. Si observa detenidamente las definiciones, notará que el resultado depende de varios factores simultáneamente.

En primer lugar, de cuántos elementos podemos combinar sus conjuntos (qué tan grandes población elementos).

En segundo lugar, el resultado depende del tamaño de los conjuntos de elementos que necesitamos.

Finalmente, es importante saber si el orden de los elementos del conjunto es significativo para nosotros. Expliquemos el último factor usando el siguiente ejemplo.

Ejemplo 9. Hay 20 personas presentes en la reunión de padres. ¿Cuántas opciones diferentes hay para la composición del comité de padres si debe incluir 5 personas?
Solución: En este ejemplo, no nos interesa el orden de los nombres en la lista del comité. Si, como resultado, las mismas personas resultan ser parte de él, entonces, en significado, para nosotros esta es la misma opción. Por lo tanto, podemos usar la fórmula para calcular el número. combinaciones de 20 elementos 5 cada uno.

Las cosas serán diferentes si cada miembro del comité es inicialmente responsable de un área de trabajo específica. Entonces, con la misma composición de lista del comité, ¡posiblemente haya 5 dentro de él! opciones permutaciones ese asunto. El número de opciones diferentes (tanto en composición como en área de responsabilidad) está determinado en este caso por el número colocaciones De 20 elementos, 5.

Tareas de autoevaluación
1. ¿Cuántos números pares de tres dígitos se pueden formar a partir de los dígitos 0, 1, 2, 3, 4, 5, 6, si los dígitos se pueden repetir?

2. ¿Cuántos números de cinco cifras hay que se leen igual de izquierda a derecha y de derecha a izquierda?

3. Hay diez materias en la clase y cinco lecciones al día. ¿De cuántas maneras puedes crear un horario para un día?

4. ¿De cuántas maneras se pueden seleccionar 4 delegados para una conferencia si hay 20 personas en el grupo?

5. ¿De cuántas maneras se pueden colocar ocho letras diferentes en ocho sobres diferentes, si solo se coloca una letra en cada sobre?