O número de colocações diferentes de a3 5 é igual. Resumo de fórmulas para todos os tipos de conexões combinatórias - permutações e colocações com e sem repetições com exemplos

Neste artigo falaremos sobre um ramo especial da matemática chamado combinatória. Fórmulas, regras, exemplos de resolução de problemas - você pode encontrar tudo isso aqui lendo o artigo até o final.

Então, o que é esta seção? A combinatória trata da questão da contagem de quaisquer objetos. Mas neste caso, os objetos não são ameixas, peras ou maçãs, mas outra coisa. A combinatória nos ajuda a encontrar a probabilidade de um evento. Por exemplo, ao jogar cartas - qual é a probabilidade de o oponente ter um trunfo? Ou este exemplo: qual é a probabilidade de você obter uma bola branca de um saco com vinte bolinhas de gude? É para este tipo de problema que precisamos conhecer pelo menos o básico deste ramo da matemática.

Configurações combinatórias

Considerando a questão dos conceitos básicos e fórmulas da combinatória, não podemos deixar de prestar atenção às configurações combinatórias. Eles são usados ​​não apenas para formular, mas também para resolver vários exemplos tais modelos são:

• alojamento;
• rearranjo;
• combinação;
• composição numérica;
• divisão de um número.

Falaremos sobre os três primeiros com mais detalhes posteriormente, mas prestaremos atenção à composição e particionamento nesta seção. Quando falam sobre a composição de um determinado número (por exemplo, a), querem dizer representar o número a como uma soma ordenada de certos números positivos. E uma partição é uma soma não ordenada.

Seções

Antes de passarmos diretamente às fórmulas combinatórias e à consideração de problemas, vale a pena prestar atenção ao fato de que a combinatória, como outros ramos da matemática, possui suas próprias subseções. Estes incluem:

• enumerativo;
• estrutural;
• extremo;
• Teoria de Ramsey;
• probabilístico;
• topológico;
• infinitário.

No primeiro caso estamos falando sobre no caso da combinatória calculativa, os problemas consideram a enumeração ou contagem das diferentes configurações que são formadas pelos elementos dos conjuntos. Via de regra, algumas restrições são impostas a esses conjuntos (distintividade, indistinguibilidade, possibilidade de repetição, etc.). E o número dessas configurações é calculado usando as regras de adição ou multiplicação, das quais falaremos um pouco mais tarde. A combinatória estrutural inclui as teorias de grafos e matróides. Um exemplo de problema combinatório extremo - qual é a maior dimensão de um gráfico que satisfaz as seguintes propriedades... No quarto parágrafo mencionamos a teoria de Ramsey, que estuda a presença de estruturas regulares em configurações aleatórias. A combinatória probabilística é capaz de responder à pergunta - qual é a probabilidade de um determinado conjunto ter uma determinada propriedade. Como você pode imaginar, a combinatória topológica aplica métodos em topologia. E por fim, o sétimo ponto - a combinatória infinitária estuda a aplicação de métodos combinatórios a conjuntos infinitos.

Regra de adição

Entre as fórmulas combinatórias você encontra algumas bastante simples, com as quais estamos familiarizados há bastante tempo. Um exemplo é a regra da soma. Suponha que recebamos duas ações (C e E), se elas forem mutuamente exclusivas, a ação C pode ser executada de várias maneiras (por exemplo, a) e a ação E pode ser executada de maneiras b, então qualquer uma delas ( C ou E) podem ser executadas de maneira a+b.

Em teoria, isso é bastante difícil de entender. Tentaremos transmitir toda a questão usando um exemplo simples. Vamos pegar número médio alunos de uma turma - digamos que são vinte e cinco. Entre eles estão quinze meninas e dez meninos. Uma pessoa de plantão é designada para cada classe todos os dias. Quantas maneiras existem hoje para nomear um monitor de turma? A solução do problema é bastante simples; recorreremos à regra da adição. O texto do problema não diz que só meninos ou só meninas podem estar de plantão. Portanto, poderia ser qualquer uma das quinze meninas ou qualquer um dos dez meninos. Aplicando a regra da soma, obtemos um exemplo bastante simples que um aluno pode facilmente lidar classes primárias: 15 + 10. Após contar, obtemos a resposta: vinte e cinco. Ou seja, existem apenas vinte e cinco maneiras de atribuir uma turma de plantão para hoje.

Regra de multiplicação

As fórmulas básicas da combinatória também incluem a regra da multiplicação. Vamos começar com a teoria. Digamos que precisamos realizar várias ações (a): a primeira ação é realizada de 1 maneira, a segunda - de 2 maneiras, a terceira - de 3 maneiras, e assim sucessivamente até a última ação a, realizada de 3 maneiras. Então todas essas ações (das quais temos um total) podem ser realizadas de N maneiras. Como calcular N desconhecido? A fórmula nos ajudará nisso: N = c1 * c2 * c3 *…* ca.

Novamente, nada está claro na teoria, vamos passar à consideração exemplo simples para aplicar a regra da multiplicação. Vamos pegar a mesma turma de vinte e cinco pessoas, na qual há quinze meninas e dez meninos. Só que desta vez precisamos escolher duas pessoas de plantão. Eles podem ser apenas meninos ou meninas, ou um menino e uma menina. Passemos à solução elementar do problema. Escolhemos o primeiro plantonista, conforme decidimos no último parágrafo, temos vinte e cinco opções possíveis. A segunda pessoa de plantão pode ser qualquer uma das demais pessoas. Tínhamos vinte e cinco alunos, escolhemos um, o que significa que o segundo plantonista poderia ser qualquer um dos vinte e quatro restantes. Finalmente, aplicamos a regra da multiplicação e descobrimos que dois oficiais em serviço podem ser eleitos de seiscentas maneiras. Obtivemos esse número multiplicando vinte e cinco por vinte e quatro.

Rearranjo

Agora veremos outra fórmula combinatória. Nesta seção do artigo falaremos sobre permutações. Propomos considerar imediatamente o problema usando um exemplo. Vamos pegar bolas de bilhar, temos o enésimo número delas. Precisamos contar quantas opções existem para organizá-los em fila, ou seja, para criar um conjunto ordenado.

Vamos começar, se não tivermos bolas, também não teremos nenhuma opção de posicionamento. E se tivermos uma bola, então o arranjo também é o mesmo (matematicamente isso pode ser escrito da seguinte forma: P1 = 1). Duas bolas podem ser colocadas em dois de maneiras diferentes: 1.2 e 2.1. Portanto, P2 = 2. Três bolas podem ser dispostas de seis maneiras (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. E se não houver três dessas bolas, mas dez ou quinze? Demoraria muito para listar todas as opções possíveis, então a combinatória vem em nosso auxílio. A fórmula de permutação nos ajudará a encontrar a resposta para a questão que nos interessa. Pn = n *P(n-1). Se tentarmos simplificar a fórmula, obtemos: Pn = n* (n - 1) *…* 2 * 1. E este é o produto do primeiro números naturais. Este número é chamado fatorial e é denotado como n!

Vamos considerar o problema. Todas as manhãs o conselheiro alinha seu plantel (vinte pessoas). Há três no elenco melhor amigo- Kostya, Sasha e Lesha. Qual é a probabilidade de eles ficarem próximos um do outro? Para encontrar a resposta à pergunta, você precisa dividir a probabilidade de um resultado “bom” pelo número total de resultados. Número total Existem 20 permutações! = 2,5 quintilhões. Como contar o número de resultados “bons”? Vamos supor que Kostya, Sasha e Lesha sejam um super-homem. Então temos apenas dezoito disciplinas. O número de permutações neste caso é 18 = 6,5 quatrilhões. Com tudo isso, Kostya, Sasha e Lesha podem mover-se arbitrariamente entre si em seus três indivisíveis, e são mais 3! = 6 opções. Isso significa que temos 18 arranjos “bons” no total! *3! Tudo o que precisamos fazer é encontrar a probabilidade desejada: (18! * 3!) / 20! O que equivale a aproximadamente 0,016. Se convertido em percentagens, resulta em apenas 1,6%.

Alojamento

Agora veremos outra fórmula combinatória muito importante e necessária. A colocação é a nossa próxima questão, que convidamos você a considerar nesta seção do artigo. Vamos para complicações. Suponha que queiramos considerar permutações possíveis, não do conjunto inteiro (n), mas de um conjunto menor (m). Ou seja, estamos considerando permutações de n itens por m.

As fórmulas básicas da combinatória não devem apenas ser memorizadas, mas compreendidas. Mesmo que se tornem mais complicados, pois não temos um parâmetro, mas dois. Suponha que m = 1, então A = 1, m = 2, então A = n * (n - 1). Se simplificarmos ainda mais a fórmula e mudarmos para a notação usando fatoriais, obteremos uma fórmula completamente lacônica: A = n! / (n-m)!

Combinação

Revisamos quase todas as fórmulas combinatórias básicas com exemplos. Agora vamos passar para fase final consideração do curso básico de combinatória - introdução à combinação. Agora escolheremos m itens dos n que temos e escolheremos todos maneiras possíveis. Como então isso é diferente da colocação? Não levaremos em consideração o pedido. Este conjunto não ordenado será a combinação.

Introduzamos imediatamente a notação: C. Tomamos a colocação de m bolas em n. Deixamos de prestar atenção à ordem e acabamos repetindo combinações. Para obter o número de combinações precisamos dividir o número de colocações por m! (m fatorial). Ou seja, C=A/m! Assim, existem apenas algumas maneiras de selecionar n bolas, o que é aproximadamente igual ao número de maneiras de selecionar quase todas elas. Isso tem expressão lógica: escolher um pouco é o mesmo que jogar fora quase tudo. Também é importante mencionar neste ponto que o número máximo de combinações pode ser alcançado ao tentar selecionar metade dos itens.

Como escolher uma fórmula para resolver um problema?

Examinamos detalhadamente as fórmulas básicas da combinatória: colocação, permutação e combinação. Agora nossa tarefa é facilitar a seleção da fórmula necessária para resolver um problema de combinatória. Você pode usar o seguinte esquema bastante simples:

1. Pergunte-se: a ordem em que os elementos são colocados é levada em consideração no texto do problema?
2. Se a resposta for não, use a fórmula combinada (C = n! / (m! * (n - m)!)).
3. Se a resposta for não, então outra questão precisa ser respondida: todos os elementos estão incluídos na combinação?
4. Se a resposta for sim, use a fórmula de permutação (P = n!).
5. Se a resposta for não, use a fórmula de posicionamento (A = n! / (n - m)!).

Exemplo

Examinamos elementos de combinatória, fórmulas e algumas outras questões. Agora vamos considerar o problema real. Imagine que você tem um kiwi, uma laranja e uma banana na sua frente.

Pergunta um: de quantas maneiras eles podem ser reorganizados? Para fazer isso, usaremos a fórmula de permutação: P = 3! = 6 maneiras.

Pergunta dois: de quantas maneiras você pode escolher uma fruta? Isso é óbvio, temos apenas três opções - escolha kiwi, laranja ou banana, mas vamos aplicar a fórmula da combinação: C = 3! / (2! * 1!) = 3.

Pergunta três: de quantas maneiras você pode escolher duas frutas? Que opções temos? Kiwi e laranja; kiwi e banana; laranja e banana. Ou seja, existem três opções, mas isso é fácil de verificar usando a fórmula de combinação: C = 3! / (1! * 2!) = 3

Pergunta quatro: de quantas maneiras você pode escolher três frutas? Como você pode ver, só existe uma maneira de escolher três frutas: levar kiwi, laranja e banana. C = 3! / (0! * 3!) = 1.

Pergunta cinco: de quantas maneiras você pode escolher pelo menos uma fruta? Esta condição significa que podemos colher uma, duas ou todas as três frutas. Portanto, somamos C1 + C2 + C3 = 3 + 3 + 1 = 7. Ou seja, temos sete maneiras de tirar pelo menos uma fruta da mesa.

Combinatória é o ramo da matemática que estuda a questão de quantas combinações existem certo tipo podem ser compostos a partir desses objetos (elementos).

Regra de multiplicação (fórmula básica de combinatória)

O número total de maneiras pelas quais se pode selecionar um elemento de cada grupo e organizá-los em uma determinada ordem (ou seja, obter um conjunto ordenado) é igual a:

Exemplo 1

A moeda foi lançada 3 vezes. Quantos resultados de lançamento diferentes você pode esperar?

Solução

A primeira moeda tem alternativas - cara ou coroa. Para a segunda moeda também existem alternativas, etc., ou seja, .

Número necessário de maneiras:

Regra de adição

Se houver dois grupos e não tiver elementos comuns, então a seleção de um elemento from , ou from , ...ou from pode ser feita de várias maneiras.

Exemplo 2

São 30 livros na estante, sendo 20 de matemática, 6 de técnica e 4 de economia. Quantas maneiras existem de escolher um livro de matemática ou de economia?

Solução

Um livro de matemática pode ser selecionado de várias maneiras, um livro de economia de várias maneiras.

De acordo com a regra da soma, existe uma maneira de escolher um livro de matemática ou economia.

Posicionamentos e rearranjos

Canais- São coleções ordenadas de elementos que diferem entre si na composição ou na ordem dos elementos.

Colocações sem repetições, quando o elemento selecionado não é retornado à população antes de selecionar o próximo. Tal seleção é chamada de seleção sequencial sem repetição, e seu resultado é um posicionamento sem repetição de elementos por .

O número de maneiras diferentes pelas quais uma seleção sequencial pode ser feita sem retornar elementos da população do volume é igual a:

Exemplo 3

A programação diária consiste em 5 aulas diferentes. Determine a quantidade de opções de agendamento ao escolher entre 11 disciplinas.

Solução

Cada opção de horário representa um conjunto de 5 disciplinas de 11, diferenciando-se das demais opções tanto na composição quanto na ordem. É por isso:

Reorganizações são coleções ordenadas que diferem entre si apenas na ordem de seus elementos. O número de todas as permutações de um conjunto de elementos é igual a

Exemplo 4

De quantas maneiras quatro pessoas podem sentar-se em uma mesa?

Solução

Cada opção de assento difere apenas na ordem dos participantes, ou seja, é uma permutação de 4 elementos:

Colocações com repetições, quando o elemento selecionado é retornado à população antes de selecionar o próximo. Essa seleção é chamada de seleção sequencial com retorno, e seu resultado é chamado de posicionamento com repetições de elementos por .

O número total de maneiras diferentes pelas quais uma seleção pode ser feita para retornar elementos da população de volume é igual a

Exemplo 5

O elevador para no 7º andar. De quantas maneiras 6 passageiros em uma cabine de elevador podem sair por esses andares?

Para garantir que a solução para um problema na teoria das probabilidades seja tão precisa e correta quanto possível, muitos solicitam trabalhos de teste neste site de maneira barata. Você pode ler detalhadamente (como enviar uma candidatura, preços, prazos, formas de pagamento) na página Compre um teste de teoria das probabilidades...

Solução

Cada um dos métodos de distribuição de passageiros pelos andares é uma combinação de 6 passageiros em 7 andares, diferindo das demais combinações tanto na composição quanto na ordem. Como um ou vários passageiros podem sair no mesmo andar, os mesmos passageiros podem repetir-se. Portanto, o número de tais combinações é igual ao número de colocações com repetições de 7 elementos de 6:

Combinações

Combinações de n elementos por k são chamadas de coleções não ordenadas que diferem entre si em pelo menos um elemento.

Deixe vários elementos serem retirados da população geral de uma só vez (ou os elementos são retirados sequencialmente, mas a ordem de seu aparecimento não é levada em consideração). Como resultado dessa seleção simultânea e não ordenada de elementos da população geral do volume, são obtidas combinações que são chamadas combinações sem repetições de elementos por .

O número de combinações de elementos é igual a:

Exemplo 6

Existem 9 maçãs em uma caixa. De quantas maneiras você pode selecionar 3 maçãs de uma caixa?

Solução

Cada escolha é composta por 3 maçãs e difere das demais apenas na composição, ou seja, são combinações sem repetição de 9 elementos:

Número de maneiras pelas quais você pode escolher 3 maçãs entre 9:

Deixe os elementos serem selecionados da população geral do volume, um após o outro, e cada elemento selecionado é retornado à população geral antes de selecionar o próximo. Registra quais elementos apareceram e quantas vezes, mas não leva em consideração a ordem em que apareceram. Os agregados resultantes são chamados combinações com repetições de elementos por .

Número de combinações com repetições de elementos por:

Exemplo 7

Os correios vendem 3 tipos de cartões postais. De quantas maneiras você pode comprar 6 cartões postais?

Esta é uma tarefa para encontrar o número de combinações com repetições de 3 a 6:

Particionando um conjunto em grupos

Deixe o conjunto de vários elementosé dividido em grupos como este, então o primeiro grupo inclui elementos, o segundo - elementos, o décimo grupo - elementos e. Esta situação é chamada de particionamento do conjunto em grupos.

O número de partições em grupos quando os elementos caem no primeiro, os elementos no segundo, os elementos no k-ésimo grupo- elementos, é igual a:

Exemplo 8

Um grupo de 16 pessoas precisa ser dividido em três subgrupos, sendo que o primeiro deve ter 5 pessoas, o segundo - 7 pessoas, o terceiro - 4 pessoas. De quantas maneiras isso pode ser feito?

Solução

Aqui

Número de divisões em 3 subgrupos:

O conceito de lei geométrica de distribuição de uma variável aleatória discreta é apresentado e um exemplo de resolução do problema é considerado. São fornecidas fórmulas para a expectativa matemática e dispersão de uma variável aleatória distribuída de acordo com uma lei geométrica.

Plano:

1. Elementos de combinatória.

2. Regras gerais de combinatória.

4. Aplicação de gráficos (esquemas) na resolução de problemas combinatórios.

1. Combinatória e suas origens.

Combinatóriaé um ramo da matemática que estuda questões sobre quantos várias combinações, sujeito a certas condições, pode ser composto por elementos pertencentes a um determinado conjunto.

A combinatória teve origem no século XVI. Os jogos de azar (cartas, dados) ocupavam um lugar importante na vida das camadas privilegiadas da sociedade da época. As loterias eram generalizadas. Inicialmente, os problemas combinatórios diziam respeito principalmente jogatina: de quantas maneiras você pode obter um determinado número de pontos jogando 2 ou 3 dados ou de quantas maneiras você pode obter 2 reis em algum jogo de cartas. Estes e outros problemas de jogo foram força motriz no desenvolvimento da combinatória e posteriormente no desenvolvimento da teoria das probabilidades.

Um dos primeiros a contar o número de combinações diferentes ao jogar dados foi o matemático italiano Tartaglia. Ele compilou tabelas (o número de maneiras pelas quais k pontos poderiam aparecer em r dados). Porém, ele não levou em consideração que a mesma quantidade de pontos pode aparecer de várias maneiras, então suas tabelas continham grande número erros.

O estudo teórico de questões combinatórias foi realizado no século XVII pelos matemáticos franceses Blaise Pascal e Fermat. O ponto de partida da sua investigação foram também os problemas do jogo.

O desenvolvimento adicional da combinatória está associado aos nomes de J. Bernoulli, G. Leibniz, L. Euler. No entanto, em seu trabalho, as aplicações para vários jogos desempenharam um papel importante.

Hoje, os métodos combinatórios são utilizados para resolver problemas de transporte, em particular problemas de escalonamento, para elaborar planos de produção e vendas de produtos, etc.

2. Regras gerais de combinatória.

Regra de soma: Se algum objeto A pode ser escolhido de m maneiras, e um objeto B de k maneiras, então o objeto “ou A ou B” pode ser escolhido de m + k maneiras.

Exemplos:

1. Suponhamos que existam n bolas de cores diferentes em uma caixa. 1 bola é retirada aleatoriamente. De quantas maneiras isso pode ser feito?

Responder: n maneiras.

Vamos distribuir essas n bolas em duas caixas: a primeira contém m bolas, a segunda contém k bolas. 1 bola é sorteada aleatoriamente de uma caixa selecionada aleatoriamente. De quantas maneiras isso pode ser feito?

Solução: A bola pode ser removida da primeira caixa de m maneiras e da segunda de k maneiras. Então o número total de maneiras é m+k=n.

2. Semáforo marinho.

No semáforo marítimo, cada letra do alfabeto corresponde a uma determinada posição de duas bandeiras em relação ao corpo do sinaleiro. Quantos desses sinais podem existir?

Solução: O número total é a soma das posições quando ambas as bandeiras estão localizadas em lados opostos do corpo do sinaleiro e das posições quando estão localizadas no mesmo lado do corpo do sinaleiro. Ao contar o número de posições possíveis, aplica-se a regra da soma.

Regra do produto: Se o objeto A pode ser selecionado de m maneiras, e após cada escolha outro objeto B pode ser selecionado (independentemente da escolha do objeto A) de k maneiras, então pares de objetos “A e B” podem ser selecionados de m * k caminhos.

Exemplos:

1. Quantos números de dois dígitos existem?

Solução: O número de dezenas pode ser denotado por qualquer número de 1 a 9. O número de unidades pode ser denotado por qualquer número de 0 a 9. Se o número de dezenas for 1, então o número de unidades pode ser qualquer número (de 0 a 9). Assim, existem 10 números de dois algarismos, sendo o número de dezenas 1. Raciocinamos de forma semelhante para qualquer outro número de dezenas. Então podemos calcular que existem 9 *10 = 90 números de dois dígitos.

2. São 2 gavetas. Um contém m cubos multicoloridos e o outro contém k bolas multicoloridas. De quantas maneiras você pode escolher o par “Cube-Ball”?

Solução: A escolha da bola não depende da escolha do cubo e vice-versa. Portanto, o número de maneiras pelas quais um determinado par pode ser selecionado é m *k .

3. População sem repetição e amostra sem repetição.

População sem repetiçõesé um conjunto de algum número finito de elementos diferentes a 1, a 2, a 3, ..., a n.

Exemplo: Conjunto de n pedaços multicoloridos.

Volume de amostragemk (kn)é um grupo de m elementos de uma determinada população.

Exemplo: Uma fita variegada costurada a partir de m retalhos multicoloridos selecionados de um determinado n .

Postagens den elementos cadak tais amostras são chamadas aquelas que contêm k elementos cada, selecionados entre os n elementos dados da população geral sem repetição, e diferem entre si na composição dos elementos ou na ordem de sua disposição.

- número de veiculações de n por k.

Número de canais de n por k pode ser determinado da seguinte maneira: o primeiro objeto de seleção pode ser selecionado n maneiras, então o segundo objeto pode ser selecionado n -1 caminho, etc.

Transformando esta fórmula, temos:

Deve ser lembrado que 0!=1.

Exemplos:

1. São 17 times participantes do grupo primeira classe A do campeonato de futebol. São concedidas medalhas: ouro, prata e bronze. De quantas maneiras eles podem ser jogados?

Solução:As combinações da equipe vencedora diferem entre si na composição e ordem dos elementos, ou seja, são colocações de 17 a 3.

2. A sociedade científica é composta por 25 pessoas. É necessário eleger presidente, vice-presidente, secretário científico e tesoureiro da sociedade. De quantas maneiras isso pode ser feito?

Solução: As combinações da equipa de gestão de uma empresa diferem entre si na composição e ordem dos elementos, ou seja, são colocações de 25 a 4.

Permutações sem repetições de nelementossão chamados de posicionamentos sem repetições de n elementos de n , ou seja os posicionamentos diferem entre si apenas na ordem dos elementos.

Número de permutações.

Exemplos:

1. Quantos números diferentes de cinco dígitos podem ser formados a partir dos dígitos 1, 2, 3, 4, 5, desde que sejam compostos por dígitos diferentes?

Solução:Temos permutações de 5 elementos.2. De quantas maneiras você pode montar 6 retalhos multicoloridos em uma fita colorida?
Solução:Temos permutações de 6 elementos.

Combinações sem repetições de nelementos pork tais amostras são chamadas aquelas que contêm k elementos cada, selecionados entre os n elementos dados da população geral sem repetição, e diferem entre si apenas na composição dos elementos.

- número de combinações de n por k

Elementos de cadacombinações podem ser organizadascaminhos. EntãoExemplos:

1. Se 20 pessoas participam da semifinal de um campeonato de xadrez e apenas três chegam à final, então de quantas maneiras essas três podem ser determinadas?

Solução:Neste caso, a ordem em que este triplo está localizado não é significativa. Portanto, os trigêmeos que chegaram às finais são combinações de 20 por 3.

2. De quantas maneiras você pode selecionar três delegados entre dez pessoas para uma conferência?

Solução:Neste caso, a ordem em que este triplo está localizado não é significativa. Portanto, trigêmeos de delegados são combinações de 10 por 3.

Resumo:

4.Utilização de gráficos (esquemas) na resolução de problemas combinatórios.

No caso em que o número de escolhas possíveis em cada etapa depende de quais elementos foram selecionados anteriormente, o processo de composição de combinações pode ser representado como uma “árvore”. Primeiro, desenhe tantos segmentos de um ponto quanto várias eleições pode ser feito na primeira etapa. A partir do final de cada segmento, desenhe tantos segmentos quantos puderem ser selecionados na segunda etapa, se este elemento foi selecionado na primeira etapa, etc.

Tarefa:

Ao compor equipes nave espacial A questão da compatibilidade psicológica dos participantes da viagem também é levada em consideração. É necessária uma tripulação de 3 pessoas: um comandante, um engenheiro e um médico. Existem 4 candidatos para o cargo de comandante: um 1, um 2, um 3, um 4 .No lugar do engenheiro 3:b 1, b 2, b 3. Para consultório médico - 3: c 1, c 2, c 3. A inspeção mostrou que o comandantea 1 é psicologicamente compatível com os engenheiros b 1 e b 3 e médicos c 1 e c 3. Comandante a 2 - com engenheiros b 1 e b 2. e todos os médicos. Comandantea 3 - com engenheirosb 1 e b 2 e médicosc 1 e c 3. Comandante a 4 - com todos os engenheiros e o médico c2. Além disso, engenheirob 1 não compatível com médico c 3, b 2 - com médico c 1 e b 3 - com médico c 2. De quantas maneiras a tripulação do navio pode ser composta nessas condições?

Solução:

Vamos criar a “árvore” correspondente.

Responder: 10 combinações.

Essa árvore é um gráfico e é usada para resolver problemas combinatórios.

Vamos contar o número de permutações de n elementos no MS EXCEL. Usando fórmulas, exibimos na planilha todas as opções de permutações ( Tradução para inglês termo: permutação).

Uma permutação de um conjunto de n elementos é a disposição dos elementos em uma determinada ordem.

Os elementos de um conjunto podem ser números, letras e quaisquer objetos em geral. O principal é que esses elementos são diferentes. Porque Qualquer objeto pode ser associado a um número, então para Permutações geralmente é usado um conjunto finito de inteiros, por exemplo, (1; 2; 3; 4; 5). Embora conjuntos de letras também possam ser encontrados frequentemente na literatura. Por exemplo, todas as permutações diferentes de um conjunto de três elementos (a, b, c) são abc, bateria, voltar, bca, táxi, cba.

O número de permutações de n elementos é n! (fatorial).

Para calcular o fatorial no MS EXCEL existe uma função =FACT(), a versão em inglês de FACT(). É claro que o número de permutações cresce muito rapidamente com n: para n=7 o número de permutações é 5040. Para ser justo, deve-se notar que muitas vezes as próprias opções de permutação não precisam ser encontradas, o principal é encontre o número deles.

Observação: As permutações podem ser consideradas um caso especial de posicionamentos para n=k (ver artigo). Portanto, você pode usar a função REST() para calcular o número de permutações. Para n = 7, o número de permutações é calculado usando a fórmula = PERMANENTE (7,7)

Observação: Você pode ler sobre Permutações com repetições (com retorno dos elementos ao conjunto do qual foram retirados após selecionar cada elemento).

Criado no arquivo de exemplo fórmula universal para exibir todas as permutações para um determinado n. Por exemplo, para n=3.

Tarefa

6 carros diferente marcas participam de corridas de sobrevivência: LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo. Determine o número de opções possíveis para distribuição de assentos entre todos os participantes.

Precisamos determinar o número de permutações de 6 carros em 6 lugares. Aqueles. n=6. Acontece que existem 720 dessas permutações: =PREST(6,6) ou 6! =FATO(6)

Vamos usar o arquivo de exemplo para encontrar todas as permutações.

Vamos comparar aleatoriamente valores numéricos com marcas de automóveis e fazer abreviações para nomes de marcas: LADA Granta (LG=1), Hyundai Solaris (HS=2), ...

Digitando em uma célula B5 valor 6, determinaremos todas as opções de colocação dos carros nos lugares que ocuparam na corrida.

Observação: você pode ler sobre canais no artigo e sobre combinações no artigo.

A enumeração de todas as permutações possíveis pode ser necessária para resolver vários problemas (ver artigo e).

Inversões de permutações

Para cada permutação um 1, um 2, um 3,..., um n de n inteiros 1, 2, 3, ..., n, a inversão é o par ( um eu, um j) se para eu< j выполняется um eu> um j. O número inverso em uma permutação mostra quão "desordenada" é a permutação em ordem crescente.

Por exemplo, o número de inversões na permutação 1, 2, 3, 4 é 0 (uma permutação de 4 inteiros é classificada em ordem crescente de 1 a 4) e o número de inversões na permutação 4, 3, 1, 2 é 5, porque.:

• o primeiro elemento (i=1) é 4 e é maior 3 números (com j=2, 3, 4), que estão localizados à direita (4>3, 4>1, 4>2), ou seja, temos 3 inversões;
• o segundo elemento (i=2) é 3 e é maior 2 números (com j=3, 4) que estão localizados à direita (3>1, 3>2), ou seja, temos mais 2 inversões;
• então o terceiro elemento (i=3) é igual a 1 e menos número com j=4, que está localizado à direita (1<2), то эта пара не является инверсией. Т.е. у перестановки 4, 3, 1, 2 число инверсий равно 3+2+0=5.

No arquivo de exemplo, para cada Permutação, o número é calculado por inversão.

Para facilitar a navegação no material, acrescentarei o conteúdo deste tópico:

Introdução. Conjuntos e seleções.

Neste tópico veremos os conceitos básicos da combinatória: permutações, combinações e posicionamentos. Vamos descobrir sua essência e fórmulas pelas quais você pode descobrir sua quantidade.

Para funcionar, precisamos de algumas informações auxiliares. Vamos começar com um conceito matemático fundamental como conjunto. O conceito de conjunto foi discutido detalhadamente no tópico “O conceito de conjunto. Métodos de definição de conjuntos”.

Uma breve história sobre as multidões: mostrar\ocultar

Resumindo: um conjunto é uma coleção de objetos. Escreva conjuntos entre chaves. A ordem em que os elementos são escritos não importa; não são permitidas repetições de elementos. Por exemplo, o conjunto de dígitos do número 11115555999 será: $\(1,5,9\)$. O conjunto de consoantes na palavra "filhote de tigre" é: $\(t, g, r, n, k\)$. A notação $5\in A$ significa que o elemento 5 pertence ao conjunto $A=\(1,5,9 \)$. O número de elementos de um conjunto finito é chamado poder deste conjunto e denota $|A|$. Por exemplo, para um conjunto $A=\(1,5,9 \)$ contendo 3 elementos, temos: $|A|=3$.

Considere um certo conjunto finito não vazio $U$, cuja cardinalidade é $n$, $|U|=n$ (ou seja, o conjunto $U$ possui $n$ elementos). Vamos apresentar um conceito como amostra(alguns autores chamam isso de tupla). Por uma amostra de volume $k$ de $n$ elementos (abreviado como $(n,k)$-sample) queremos dizer um conjunto de elementos $(a_1, a_2,\ldots, a_k)$, onde $a_i\in U$. Uma seleção é chamada ordenada se a ordem de seus elementos for especificada. Duas amostras ordenadas que diferem apenas na ordem dos elementos são diferentes. Se a ordem dos elementos da amostra não for significativa, a amostra é chamada de não ordenada.

Observe que a definição de seleção não diz nada sobre repetições de elementos. Ao contrário dos elementos de conjunto, os elementos de seleção podem ser repetidos.

Por exemplo, considere o conjunto $U=\(a,b,c,d,e\)$. O conjunto $U$ contém 5 elementos, ou seja, $|U|=5$. Uma amostra sem repetições poderia ser: $(a,b,c)$. Esta seleção contém 3 elementos, ou seja, o tamanho desta amostra é 3. Em outras palavras, é uma amostra $(5,3)$.

Uma amostra com repetições pode ser assim: $(a,a,a,a,a,c,c,d)$. Ele contém 8 elementos, ou seja, seu volume é 8. Em outras palavras, esta é uma amostra $(5,8)$.

Vamos considerar mais duas amostras $(5,3)$: $(a,b,b)$ e $(b,a,b)$. Se assumirmos que nossas amostras não são ordenadas, então a amostra $(a,b,b)$ é igual à amostra $(b,a,b)$, ou seja, $(a,b,b)=(b,a,b)$. Se assumirmos que nossas amostras estão ordenadas, então $(a,b,b)\neq(b,a,b)$.

Vejamos outro exemplo, um pouco menos abstrato:) Suponha que haja seis doces em uma cesta e sejam todos diferentes. Se associarmos o primeiro doce ao número 1, o segundo doce ao número 2 e assim por diante, então o seguinte conjunto pode ser associado aos doces da cesta: $U=\(1,2,3,4, 5,6\)$. Imagine que colocamos aleatoriamente a mão em uma cesta para retirar três doces. Os doces retirados são a seleção. Como pegamos 3 doces de 6, obtemos uma amostra (6,3). A ordem em que os doces são colocados na palma da mão é completamente irrelevante, portanto esta amostra está desordenada. Pois bem, e como todos os doces são diferentes, a seleção é sem repetição. Portanto, nesta situação estamos falando de uma amostra (6,3) não ordenada sem repetições.

Agora vamos abordar do outro lado. Vamos imaginar que estamos em uma fábrica de produção de doces, e nesta fábrica são produzidos quatro tipos de doces. O conjunto $U$ nesta situação é o seguinte: $U=\(1,2,3,4 \)$ (cada número é responsável pelo seu tipo de doce). Agora vamos imaginar que todos os doces são colocados em uma única calha, perto da qual estamos. E, colocando as palmas das mãos, selecionamos 20 doces desse fluxo. Um punhado de doces é uma amostra. A ordem em que os doces são colocados em um punhado é importante? Naturalmente, não, então a amostra não está ordenada. Existem apenas 4 variedades de doces, e selecionamos vinte peças do fluxo geral - a repetição de variedades é inevitável. Ao mesmo tempo, as amostras podem ser muito diferentes: podemos até ter todos os doces do mesmo tipo. Portanto, nesta situação estamos lidando com uma amostra (4,20) não ordenada com repetições.

Vejamos mais alguns exemplos. Deixe que 7 letras diferentes sejam escritas nos cubos: k, o, n, f, e, t, a. Essas letras formam o conjunto $U=\(k,o,n,f,e,t,a\)$. Digamos que a partir destes cubos queremos fazer “palavras” de 5 letras. As letras dessas palavras (por exemplo, “konfe”, “tenko” e assim por diante) formam seleções (7,5): $(k,o,n,f,e)$, $(t,e,n ,k ,o)$, etc. Obviamente, a ordem das letras nessa amostra é importante. Por exemplo, as palavras “nokft” e “kfton” são diferentes (embora consistam nas mesmas letras), porque a ordem das letras nelas não corresponde. Não há repetições de letras nessas “palavras”, pois existem apenas sete cubos. Portanto, o conjunto de letras de cada palavra é uma amostra ordenada (7,5) sem repetições.

Outro exemplo: fazemos todos os tipos de números de oito dígitos a partir de quatro dígitos 1, 5, 7, 8. Por exemplo, 11111111, 15518877, 88881111 e assim por diante. O conjunto $U$ é: $U=\(1,5,7,8\)$. Os dígitos de cada número composto formam uma amostra (4,8). A ordem dos dígitos em um número é importante, ou seja, a amostra é solicitada. Repetições são permitidas, então aqui estamos lidando com uma amostra ordenada (4,8) com repetições.

Posicionamentos sem repetições de elementos $n$ por $k$

Colocação sem repetições de elementos $n$ por $k$ - seleção $(n,k)$ ordenada sem repetições.

Como os elementos da amostra em consideração não podem ser repetidos, não podemos selecionar mais elementos na amostra do que os do conjunto original. Portanto, para tais amostras a seguinte desigualdade é verdadeira: $n≥ k$. O número de colocações sem repetições de elementos $n$ por $k$ é determinado pela seguinte fórmula:

\begin(equação)A_(n)^(k)=\frac(n{(n-k)!} \end{equation} !}

O que significa o sinal "!": mostrar\ocultar

Gravando "n!" (leia-se "en factorial") denota o produto de todos os números de 1 a n, ou seja,

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

Por definição, assume-se que $0!=1!=1$. Por exemplo, vamos encontrar 5!:

$$ 5!=1\cponto 2\cponto 3\cponto 4\cponto 5=120. $$

Exemplo nº 1

O alfabeto consiste em um conjunto de símbolos $E=\(+,*,0,1,f\)$. Vamos determinar o número dessas palavras de três caracteres neste alfabeto que não contêm letras repetidas.

Por palavras de três caracteres queremos dizer expressões como “+*0” ou “0f1”. O conjunto $E$ tem cinco elementos, então as letras das palavras de três caracteres formam seleções (5,3). A primeira pergunta é: essas amostras são encomendadas ou não? Palavras que diferem apenas na ordem das letras são consideradas diferentes, portanto a ordem dos elementos da amostra é importante. Isso significa que a amostra está ordenada. Segunda pergunta: as repetições são permitidas ou não? A resposta a esta pergunta é dada pela condição: as palavras não devem conter letras repetidas. Resumindo: as letras de cada palavra que satisfazem as condições do problema formam uma amostra ordenada (5,3) sem repetições. Em outras palavras, as letras de cada palavra formam um posicionamento sem repetição de 5 elementos de 3. Aqui estão alguns exemplos de tais posicionamentos:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Estamos interessados ​​no número total dessas colocações. De acordo com a fórmula (1), o número de colocações sem repetições de 5 elementos de 3 será o seguinte:

$$A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

Aqueles. você pode formar 60 palavras de três caracteres, cujas letras não serão repetidas.

Responder: 60.

Canais com repetições de $n$ elementos de $k$

Alocação com repetições de elementos $n$ por $k$ - $(n,k)$-seleção ordenada com repetições.

O número de colocações com repetições de $n$ elementos de $k$ é determinado pela seguinte fórmula:

\begin(equação)\bar(A)_(n)^(k)=n^k \end(equação)

Exemplo nº 2

Quantos números de cinco dígitos podem ser formados a partir do conjunto de dígitos $\(5,7,2\)$?

A partir desse conjunto de números, você pode formar números de cinco dígitos 55555, 75222 e assim por diante. Os dígitos de cada um desses números formam uma amostra (3,5): $(5,5,5,5,5)$, $(7,5,2,2,2)$. Perguntemo-nos: que tipo de amostras são estas? Primeiro, os dígitos dos números podem ser repetidos, por isso estamos lidando com amostras com repetições. Em segundo lugar, a ordem dos dígitos de um número é importante. Por exemplo, 27755 e 77255 são números diferentes. Conseqüentemente, estamos lidando com amostras ordenadas (3,5) com repetições. Encontramos o número total de tais amostras (ou seja, o número total de números necessários de cinco dígitos) usando a fórmula (2):

$$\bar(A)_(3)^(5)=3^5=243. $$

Portanto, 243 números de cinco dígitos podem ser formados a partir dos dígitos fornecidos.

Responder: 243.

Permutações sem repetições de elementos $n$

Uma permutação sem repetições de $n$ elementos é uma seleção $(n,n)$ ordenada sem repetições.

Em essência, a permutação sem repetição é um caso especial de colocação sem repetição, quando o tamanho da amostra é igual à cardinalidade do conjunto original. O número de permutações sem repetição de $n$ elementos é determinado pela seguinte fórmula:

\begin(equação)P_(n)=n! \fim(equação)

A propósito, esta fórmula é fácil de obter se você considerar que $P_n=A_(n)^(n)$. Então obtemos:

$$P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Exemplo nº 3

Há cinco porções de sorvete de diferentes empresas no freezer. De quantas maneiras você pode escolher a ordem em que serão consumidos?

Deixe o número 1 corresponder ao primeiro sorvete, o número 2 ao segundo e assim por diante. Obteremos o conjunto $U=\(1,2,3,4,5\)$, que representará o conteúdo do freezer. A ordem de alimentação pode ser a seguinte: $(2,1,3,5,4)$ ou a seguinte: $(5,4,3,1,2)$. Cada um desses conjuntos é uma amostra (5,5). Será ordenado e sem repetição. Em outras palavras, cada amostra é uma permutação de 5 elementos do conjunto original. De acordo com a fórmula (3), o número total dessas permutações é o seguinte:

$$P_5=5!=120. $$

Conseqüentemente, são 120 pedidos para escolha da ordem de alimentação.

Responder: 120.

Permutações com repetições

A permutação com repetições é uma amostra $(n,k)$ ordenada com repetições, na qual o elemento $a_1$ é repetido $k_1$ vezes, $a_2$ é repetido $k_2$ vezes, e assim por diante, até o último elemento $ a_r$, que é repetido $k_r$ vezes. Neste caso, $k_1+k_2+\ldots+k_r=k$.

O número total de permutações com repetições é determinado pela fórmula:

\begin(equação)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Exemplo nº 4

As palavras são compostas com base no alfabeto $U=\(a,b,d\)$. Quantas palavras diferentes podem ser compostas por sete caracteres se nestas palavras a letra “a” deve ser repetida 2 vezes; a letra “b” - 1 vez, e a letra “d” - 4 vezes?

Aqui estão alguns exemplos de palavras de pesquisa: “aabdddd”, “daddabd” e assim por diante. As letras de cada palavra formam uma amostra (3,7) com repetições: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ e etc Cada seleção consiste em dois elementos "a", um elemento "b" e quatro elementos "d". Em outras palavras, $k_1=2$, $k_2=1$, $k_3=4$. O número total de repetições de todos os símbolos, naturalmente, é igual ao tamanho da amostra, ou seja, $k=k_1+k_2+k_3=7$. Substituindo esses dados na fórmula (4), teremos:

$$P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105. $$ !}

Portanto, o número total de palavras pesquisadas é 105.

Responder: 105.

Combinações sem repetições de $n$ elementos de $k$ cada

Uma combinação sem repetições de $n$ elementos por $k$ é uma amostra $(n,k)$ não ordenada sem repetições.

O número total de combinações sem repetições de $n$ elementos de $k$ é determinado pela fórmula:

\begin(equação)C_(n)^(k)=\frac(n{(n-k)!\cdot k!} \end{equation} !}

Exemplo nº 5

A cesta contém cartões com números inteiros de 1 a 10 escritos. 4 cartas são retiradas da cesta e os números escritos nelas são somados. Quantos conjuntos diferentes de cartas podem ser retirados da cesta?

Portanto, neste problema o conjunto inicial é: $U=\(1,2,3,4,5,6,7,8,9,10\)$. Deste conjunto selecionamos quatro elementos (ou seja, quatro cartas da cesta). Os números dos elementos retirados formam uma seleção (10,4). Não são permitidas repetições nesta seleção, pois os números de todas as cartas são diferentes. A questão é: a ordem em que as cartas são selecionadas importa ou não? Ou seja, por exemplo, as amostras $(1,2,7,10)$ e $(10,2,1,7)$ são iguais ou não iguais? Aqui você precisa consultar as condições do problema. As cartas são retiradas para posteriormente encontrar a soma dos elementos. Isso significa que a ordem das cartas não é importante, pois a alteração dos locais dos termos não alterará a soma. Por exemplo, a amostra $(1,2,7,10)$ e a amostra $(10,2,1,7)$ corresponderão ao mesmo número $1+2+7+10=10+2+1+ 7 = $ 20. Conclusão: pelas condições do problema segue-se que se trata de amostras não ordenadas. Aqueles. precisamos encontrar o número total de amostras não ordenadas (10,4) sem repetições. Em outras palavras, precisamos encontrar o número de combinações de 10 elementos de 4. Usamos a fórmula (5) para isso:

$$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Portanto, o número total de conjuntos pesquisados ​​é 210.

Responder: 210.

Combinações com repetições de $n$ elementos de $k$ cada

Uma combinação com repetições de $n$ elementos de $k$ é uma amostra $(n,k)$ não ordenada com repetições.

O número total de combinações com repetições de $n$ elementos de $k$ é determinado pela fórmula:

\begin(equação)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!} \end{equation} !}

Exemplo nº 6

Imagine que estamos em uma fábrica de doces, bem ao lado de uma esteira por onde se movem quatro tipos de doces. Colocamos nossas mãos neste fluxo e retiramos vinte peças. Quantas “combinações de doces” diferentes podem existir em um punhado?

Se assumirmos que o primeiro tipo corresponde ao número 1, o segundo tipo - o número 2 e assim por diante, então o conjunto inicial em nosso problema é o seguinte: $U=\(1,2,3,4\) $. Deste conjunto selecionamos 20 elementos (ou seja, esses mesmos 20 doces da linha de montagem). Um punhado de doces forma uma amostra (4,20). Naturalmente, haverá repetições de variedades. A questão é: a ordem dos elementos na amostra é importante ou não? Das condições do problema segue-se que a ordem em que os elementos estão dispostos não importa. Não faz diferença para nós se o punhado contém primeiro 15 pirulitos e depois 4 bombons de chocolate, ou primeiro 4 bombons de chocolate e só depois 15 pirulitos. Portanto, estamos lidando com uma amostra não ordenada (4,20) com repetições. Para encontrar o número total dessas amostras usamos a fórmula (6):

$$\bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Portanto, o número total de combinações pesquisadas é 1771.