Este artigo se concentrará em uma seção especial da matemática chamada combinatória. Fórmulas, regras, exemplos de resolução de problemas - tudo isso você encontra aqui lendo o artigo até o final.
Então, o que é esta seção? Combinatória lida com a questão de contar 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 um exemplo - qual é a probabilidade de você obter exatamente branco de um saco de vinte bolas? É para este tipo de tarefas que precisamos conhecer pelo menos o básico desta seção de 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 formulação, mas também para resolver vários problemas combinatórios. Exemplos de tais modelos são:
- colocação;
- permutação;
- combinação;
- composição numérica;
- número dividido.
Falaremos sobre os três primeiros com mais detalhes posteriormente, mas prestaremos atenção à composição e divisão nesta seção. Quando eles falam sobre a composição de um certo número (digamos, a), eles querem dizer a representação do número a como uma soma ordenada de alguns números positivos. E uma divisão é uma soma não ordenada.
Seções
Antes de irmos diretamente às fórmulas da combinatória e à consideração dos problemas, vale a pena prestar atenção ao fato de que a combinatória, como outras seções da matemática, tem suas próprias subseções. Estes incluem:
- enumerative;
- estrutural;
- extremo;
- Teoria de Ramsey;
- probabilístico;
- topológico;
- infinito.
No primeiro caso, estamos falando de combinatória enumerativa, os problemas consideram a enumeração ou contagem de diferentes configurações que são formadas por elementos de conjuntos. Como regra, algumas restrições são impostas a esses conjuntos (distinguibilidade, indistinguibilidade, possibilidade de repetição etc.). E o número dessas configurações é calculado usando a regra de adição ou multiplicação, sobre a qual falaremos um pouco mais adiante. A combinatória estrutural inclui as teorias de grafos e matróides. Um exemplo de problema de combinatória extrema é qual é a maior dimensão de um grafo 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. probabilísticoa combinatória é 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 finalmente, 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 da combinatória, podemos encontrar algumas bastante simples, com as quais estamos familiarizados há muito tempo. Um exemplo é a regra da soma. Suponha que recebemos duas ações (C e E), se elas são mutuamente exclusivas, a ação C pode ser feita de várias maneiras (por exemplo, a), e a ação E pode ser feita de maneiras b, então qualquer uma delas (C ou E) pode ser feito de formas a + b.
Em teoria, isso é bastante difícil de entender, tentaremos transmitir todo o ponto com um exemplo simples. Vamos pegar o número médio de alunos em uma classe - digamos que é vinte e cinco. Entre eles estão quinze meninas e dez meninos. Um atendente é designado para a classe diariamente. De quantas maneiras existem hoje para designar um atendente de classe? A solução do problema é bastante simples, vamos recorrer à regra da adição. O texto da tarefa não diz que apenas meninos ou apenas 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 com o qual um aluno da escola primária pode lidar facilmente: 15 + 10. Tendo calculado, obtemos a resposta: vinte e cinco. Ou seja, existem apenas vinte e cinco maneirasatribua uma aula de serviço para hoje.
Regra de multiplicação
A regra da multiplicação também pertence às fórmulas básicas da combinatória. Comecemos pela teoria. Suponha que precisamos executar várias ações (a): a primeira ação é realizada de 1 maneiras, a segunda - de 2 maneiras, a terceira - de 3 maneiras, e assim por diante até que a última ação-a seja realizada de maneiras sa. Então todas essas ações (das quais temos um total) podem ser realizadas de N maneiras. Como calcular o desconhecido N? A fórmula nos ajudará com isso: N \u003d c1c2c3…ca.
Novamente, nada é claro na teoria, vamos passar para um exemplo simples de aplicação da regra da multiplicação. Vamos pegar a mesma classe de vinte e cinco pessoas, na qual quinze meninas e dez meninos estudam. Só que desta vez precisamos escolher dois atendentes. Eles podem ser apenas meninos ou meninas, ou um menino com uma menina. Voltamo-nos para a solução elementar do problema. Escolhemos o primeiro atendente, como decidimos no último parágrafo, temos vinte e cinco opções possíveis. A segunda pessoa de plantão pode ser qualquer uma das pessoas restantes. Tínhamos vinte e cinco alunos, escolhemos um, o que significa que qualquer uma das vinte e quatro pessoas restantes pode ser a segunda de plantão. Finalmente, aplicamos a regra da multiplicação e descobrimos que os dois atendentes podem ser escolhidos de seiscentas maneiras. Obtemos esse número multiplicando vinte e cinco por vinte e quatro.
Troca
Agora vamos considerar mais uma fórmula combinatória. Nesta seção do artigo, vamosVamos falar sobre permutações. Considere o problema imediatamente com um exemplo. Vamos pegar bolas de bilhar, temos n-ésimo número delas. Precisamos calcular: quantas opções existem para organizá-las em linha, ou seja, para formar um conjunto ordenado.
Vamos começar, se não temos bolas, então também temos zero opções de colocação. E se tivermos uma bola, o arranjo também será o mesmo (matematicamente, isso pode ser escrito da seguinte maneira: Р1=1). Duas bolas podem ser dispostas de duas maneiras diferentes: 1, 2 e 2, 1. Portanto, Р2=2. Três bolas podem ser dispostas de seis maneiras (Р3=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? Listar todas as opções possíveis é muito longo, então a combinatória vem em nosso auxílio. A fórmula de permutação nos ajudará a encontrar a resposta para nossa pergunta. Pn=nP(n-1). Se tentarmos simplificar a fórmula, obtemos: Pn=n (n - 1) … 21. E este é o produto dos primeiros números naturais. Tal número é chamado de fatorial e é denotado como n!
Vamos considerar o problema. O líder todas as manhãs constrói seu desapego em fila (vinte pessoas). Existem três melhores amigos no destacamento - Kostya, Sasha e Lesha. Qual é a probabilidade de eles ficarem um ao lado do outro? Para encontrar a resposta para a pergunta, você precisa dividir a probabilidade de um resultado “bom” pelo número total de resultados. O número total de permutações é 20!=2,5 quintilhões. Como contar o número de resultados "bons"? Suponha que Kostya, Sasha e Lesha sejam um super-homem. Então nósTemos apenas dezoito assuntos. O número de permutações neste caso é 18=6,5 quatrilhões. Com tudo isso, Kostya, Sasha e Lesha podem se mover arbitrariamente entre si em seu triplo indivisível, e são mais 3!=6 opções. Portanto, temos 18 constelações “boas” no total!3! Basta encontrar a probabilidade desejada: (18!3!) / 20! Que é aproximadamente 0,016. Se convertido em porcentagem, resulta em apenas 1,6%.
Hospedagem
Agora vamos considerar outra fórmula combinatória muito importante e necessária. A acomodação é nossa próxima edição, que sugerimos que você considere nesta seção do artigo. Nós vamos ficar mais complicados. Vamos supor que queremos considerar permutações possíveis, apenas não de todo o conjunto (n), mas de um menor (m). Ou seja, consideramos permutações de n itens por m.
As fórmulas básicas da combinatória não devem ser apenas memorizadas, mas compreendidas. Mesmo que eles se tornem mais complicados, já que não temos um parâmetro, mas dois. Suponha que m \u003d 1, depois A \u003d 1, m \u003d 2, depois A \u003d n(n - 1). Se simplificarmos ainda mais a fórmula e mudarmos para a notação usando fatoriais, obteremos uma fórmula bastante concisa: A \u003d n! / (n - m)!
Combinação
Consideramos quase todas as fórmulas básicas da combinatória com exemplos. Agora vamos passar para o estágio final de considerar o curso básico de combinatória - conhecer a combinação. Agora vamos escolher m itens dos n que temos, enquanto vamos escolher todos eles de todas as maneiras possíveis. Como, então, isso é diferente de acomodação? Não vamosconsidere a ordem. Este conjunto não ordenado será uma combinação.
Imediatamente introduza a notação: C. Tomamos colocações de m bolas de n. Deixamos de prestar atenção à ordem e ficamos com combinações repetidas. Para obter o número de combinações, precisamos dividir o número de posicionamentos por m! (m fatorial). Ou seja, C \u003d A / m! Assim, existem algumas maneiras de escolher entre n bolas, aproximadamente igual a quantas escolher quase tudo. Há uma expressão lógica para isso: 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 escolha da fórmula necessária para resolver o problema em combinatória. Você pode usar o seguinte esquema bastante simples:
- Pergunte-se: a ordem dos elementos é levada em conta no texto do problema?
- Se a resposta for não, use a fórmula de combinação (C=n! / (m!(n - m)!)).
- Se a resposta for não, então você precisa responder mais uma pergunta: todos os elementos estão incluídos na combinação?
- Se a resposta for sim, use a fórmula de permutação (P=n!).
- Se a resposta for não, use a fórmula de alocação (A=n! / (n - m)!).
Exemplo
Consideramos os elementos de combinatória, fórmulas e algumas outras questões. Agora vamos passar paraconsiderando um problema real. Imagine que você tem um kiwi, uma laranja e uma banana na sua frente.
Pergunta um: de quantas maneiras eles podem ser rearranjados? Para fazer isso, usamos a fórmula de permutação: P=3!=6 maneiras.
Pergunta dois: de quantas maneiras uma fruta pode ser escolhida? Isso é óbvio, temos apenas três opções - escolha kiwi, laranja ou banana, mas aplicamos a fórmula de combinação: C \u003d 3! / (2!1!)=3.
Pergunta três: de quantas maneiras podem ser escolhidas duas frutas? Que opções temos? Kiwi e laranja; kiwi e banana; laranja e banana. Ou seja, três opções, mas isso é fácil de verificar usando a fórmula de combinação: C \u003d 3! / (1!2!)=3
Pergunta quatro: de quantas maneiras podem ser escolhidas três frutas? Como você pode ver, só há uma maneira de escolher três frutas: pegue um kiwi, uma laranja e uma banana. C=3! / (0!3!)=1.
Pergunta cinco: de quantas maneiras você pode escolher pelo menos uma fruta? Esta condição implica que podemos colher um, dois ou todos os três frutos. Portanto, somamos C1 + C2 + C3=3 + 3 + 1=7. Ou seja, temos sete maneiras de tirar pelo menos uma fruta da mesa.
