O tema principal que desenvolveremos nesta Sala, Números de Stirling do primeiro tipo, não é um assunto abordado no Ensino Médio. Entretanto, é um tema muito conveniente para o Projeto dos Clubes de Matemática, por se tratar de um problema geral de contagem que, quando considerado em um caso particular, incide no conceito de Permutação Circular. Pelo fato de envolver contagem de configurações discretas e tratar-se de um problema de contagem, é possível trabalhar esse tema no
Ensino Médio, mais especificamente no segundo ano, quando for abordado o estudo de sequências numéricas e análise combinatória ou quando da apresentação da definição de permutação circular. Show Quem foi Stirling? James Stirling foi um matemático escocês que contribuiu com
avanços importantes na teoria das séries infinitas e no cálculo infinitesimal. Ele nasceu em 11 de maio de 1692 em Garden, Reino Unido. Pouco se sabe sobre sua formação acadêmica além de que em 1710 ele viajou para Oxford e se matriculou no Balliol College Oxford, no início de 1711. A família de Stirling apoiava fortemente a causa jacobita (Veja a referência [13].) e isso teria uma influência significativa na sua vida.
Imagens extraídas de Wikipedia Para saber mais sobre a vida do matemático James Stirling, clique AQUI e acesse um texto do site do MacTutor, um recurso on-line que contém biografias de quase 3000 matemáticos! Permutação Circular Uma permutação de [tex]n[/tex] objetos é uma sequência ordenada desses [tex]n[/tex] objetos, na qual cada um deles aparece uma única vez. Vejamos um exemplo. Exemplo 1: Considere o conjunto formado pelos [tex]4[/tex] símbolos mostrados na imagem a seguir.
Figura 1: Contas para formar uma pulseira ► De quantas maneiras podemos permutar os símbolos exibidos na Figura 1?
Figura 2: Contas associadas às letras [tex]A[/tex], [tex]B[/tex], [tex]C[/tex] e [tex] D[/tex]. As [tex]24[/tex] permutações escritas na forma de sequências são: [tex](A, B, C, D)\,;\,(B, C, D, A)\,;\,(C, D, A, B)\,;\,(D, A, B, C);[/tex] Agora vamos considerar a seguinte questão: Exemplo 2:
Figura 3: As seis pulseiras distintas formadas pelas [tex]4[/tex] contas. Vamos considerar a primeira pulseira mostrada na Figura 3 e vamos girá-la no sentido anti-horário, de forma que a conta verde ocupe o lugar da conta azul. A seguir, giramos novamente no sentido anti-horário (segundo giro), mudando novamente a posição da conta verde para a nova posição da conta azul, e assim sucessivamente. Note que a pulseira é a mesma e que as posições das contas voltarão para a posição inicial, se fizermos o quarto giro.
Figura 4: Giros da pulseira no sentido anti-horário. Observe que podemos associar cada uma das seis pulseiras da Figura 3 a um círculo no qual são dispostas as letras [tex] A, B, C[/tex] e [tex]D[/tex] que correspondem às contas com que formamos as pulseiras. Na figura a seguir, descrevemos o círculo associado à primeira pulseira.
Figura 5: Pulseira associada a uma distribuição circular das letras [tex]A,B,C,D[/tex]. Vamos reescrever o problema das pulseiras… ► Queremos distribuir quatro contas [tex]A, B, C[/tex] e [tex]D[/tex] ao longo de uma pulseira. De quantas formas podemos fazer isso?
Figura 6: Distribuição das permutações de quatro objetos em torno do círculo. Assim, podemos distribuir as quatro contas [tex]A, B, C[/tex] e [tex]D[/tex] ao longo de uma pulseira de [tex]24[/tex] maneiras; no entanto, essas [tex]24[/tex] distribuições definem apenas [tex]6[/tex] pulseiras, digamos, diferentes. Olhando o problema das pulseiras numa perspectiva mais geral, o que pretendemos agora é contar o número de maneiras de se ordenar [tex]n[/tex] objetos em torno de um círculo. Uma permutação circular de [tex]n[/tex] objetos é cada uma das disposições possíveis quando
dispomos os [tex]n[/tex] objetos ao redor de um círculo, considerando disposições idênticas aquelas que coincidem por rotação. Uma outra alternativa para estabelecer a quantidade de permutações circulares de [tex]n[/tex] objetos é observar que, em uma mesa circular com [tex]n[/tex] assentos com pessoas sentadas, não sabemos quem é o primeiro ou o último nessa configuração. Dessa forma, fixada uma pessoa nessa mesa para ser a primeira, podemos formar [tex](n-1)![/tex] filas com as pessoas restantes. Assim, da mesma forma, concluímos que [tex] PC_{n}=(n-1)![/tex]. Antes de apresentarmos os Números de Stirling, Atividade 1: De quantas formas [tex]12[/tex] crianças podem formar uma roda? Atividade 2: De quantas formas oito casais fixos podem se sentar em uma roda gigante com oito bancos de dois lugares cada um, sentando cada casal em um banco? Atividade 3: De quantos modos podemos pintar as faces de uma pirâmide pentagonal regular usando seis cores diferentes, sendo cada face pintada de uma cor? Atividade 4: Atividade 5: De quantas maneiras [tex] 7[/tex] pessoas podem sentar-se em torno de uma mesa circular, sendo que [tex]2[/tex] determinadas pessoas não devem ficar juntas? Atividade 6: De quantas maneiras [tex]8[/tex] meninas e [tex] 8[/tex] meninos podem sentar-se em uma mesa circular, de forma que as meninas sempre fiquem juntas? Atividade 7: De quantas maneiras [tex]8[/tex] meninos e [tex]8[/tex] meninas podem sentar-se em uma mesa circular, de tal forma que sempre crianças do mesmo sexo não fiquem juntas? Atividade 8: De quantas maneiras [tex] 7 [/tex] casais podem se sentar em torno de uma mesa circular contendo [tex]14[/tex] lugares, de modo que não sentem juntos [tex]2[/tex] homens e que cada homem sente ao lado da sua esposa? Atividade 9: Paulo e Marta fazem parte de um grupo de [tex] 8 [/tex] pessoas. De quantas maneiras o grupo de [tex]8[/tex] pessoas pode se sentar em uma mesa circular, de forma que fiquem [tex]3[/tex] pessoas entre Marta e Paulo? Atividade 10: De quantas maneiras podemos colorir as faces de um tronco de uma pirâmide, cujas bases são pentagonais e regulares, usando [tex]7[/tex] cores diferentes? Atividade 11: De quantos modos podemos colorir as faces de um prisma, cujas bases são pentagonais e regulares, usando [tex]7[/tex] cores diferentes? Números de Stirling do primeiro tipo Considere o seguinte problema de contagem: Questão 1: De quantas maneiras quatro pessoas podem se sentar em volta de duas mesas circulares indistinguíveis, sem que nenhuma mesa fique vazia? A ideia inicial para resolvermos a questão é listar as possíveis distribuições das pessoas nas duas mesas, de forma que as mesas estejam sempre ocupadas. Para isso, vamos considerar o conjunto formado pelas [tex]4[/tex] pessoas, a saber [tex] A,B,C [/tex] e [tex] D[/tex], e representar as maneiras de organizarmos esta distribuição:
Figura 7: Ilustração da primeira distribuição nas mesas. Observe que essa nova distribuição é simétrica à anterior.
Figura 8:Ilustração da segunda distribuição nas mesas. Para os casos listados a seguir a ilustração por meio dos desenhos são análogas às figuras [tex]7[/tex] e [tex] 8 [/tex]: Logo, há [tex] 11[/tex] maneiras de distribuirmos as quatro pessoas em duas mesas circulares de forma que não fiquem mesas vazias. Queremos agora observar a Questão 1 numa perspectiva mais geral, distribuindo [tex]n[/tex] pessoas em [tex]k[/tex] mesas circulares. Questão 2: De quantas maneiras [tex]n[/tex] pessoas podem se sentar em volta de [tex]k[/tex] mesas circulares indistinguíveis, sem que nenhuma mesa fique vazia? Para responder essa questão geral, vamos estabelecer uma relação de recorrência para o problema. Para isso, vamos denotar por [tex]\qquad \textcolor{#4178a1}{(ii)}[/tex][tex] {\left[ \begin{array}{c} n \\ k \end{array} \right]} [/tex] o número de elementos do conjunto [tex]D(n,k)[/tex]. (Da Questão 1 segue, por exemplo, que [tex] {\left[ \begin{array}{c} 4 \\2 \end{array} \right]} =11 \,.[/tex]) Vamos fazer algumas análises iniciais de casos particulares da questão:
Estabelecidas essas condições iniciais, a ideia agora é analisar o problema para [tex]n \gt k \gt 1[/tex] e estabelecer uma relação de recorrência. Para isso, vamos dividir o conjunto [tex] D(n,k)[/tex] em dois subconjuntos disjuntos. Assim, sejam [tex]p_{1}, p_{2} , \dots, p_{n}[/tex] as [tex] n[/tex] pessoas que iremos distribuir para sentarem-se nas [tex]k[/tex] mesas circulares idênticas, sem que não fiquem mesas vazias, e consideremos os seguintes conjuntos:
Para determinarmos a quantidade de distribuições do Caso 2, vamos distribuir inicialmente as pessoas [tex] p_{1}, p_{2}, \dots, p_{n-1}[/tex] nas [tex]k[/tex] mesas, de modo que não fiquem mesas vazias, e, em seguida, vamos colocar a pessoa [tex] p_{n}[/tex] em uma das mesas. Dessa forma, segue do Princípio Multiplicativo que há [tex](n-1)\cdot {\left[ \begin{array}{c} n -1\\ k \end{array} \right]} [/tex] maneiras de distribuirmos as pessoas [tex] p_{1}, p_{2}, \dots, p_{n} [/tex] nas [tex]k[/tex] mesas circulares idênticas de forma que a pessoa [tex]p_{n}[/tex] não fique sozinha na mesa. Segue desses dois casos que o total de elementos de [tex]D(n,k)[/tex] é igual a [tex](n-1) {\left[ \begin{array}{c} n -1\\ k \end{array} \right]} + {\left[ \begin{array}{c} n -1\\ k-1 \end{array} \right]} [/tex], ou seja, [tex] \fcolorbox{black}{#b8c7d9}{$ {\left[ \begin{array}{c} n \\ k \end{array} \right]} ={\left[ \begin{array}{c} n -1\\ k-1 \end{array} \right]} + (n-1) {\left[ \begin{array}{c} n -1\\ k \end{array} \right]} $}\, [/tex], se [tex]1 \lt k \lt n[/tex]. Os números que denotamos por [tex] {\left[ \begin{array}{c} n \\ k \end{array} \right]} [/tex] para resolvermos a Questão 2 é o que se define na Matemática como Números de Stirling do primeiro tipo. Definição:
Se [tex]n[/tex] e [tex]k[/tex] são números naturais, designa-se por Números de Stirling do primeiro tipo, e denota-se por [tex] {\left[ \begin{array}{c} n \\ k \end{array} \right]} [/tex], os números inteiros não negativos que determinam a quantidade de maneiras de distribuirmos, respectivamente, [tex]n[/tex] pessoas em [tex]k[/tex] mesas circulares idênticas de modo que tenhamos pelo menos uma pessoa em cada mesa. Vejamos algumas propriedades importantes desse tipo de números. Algumas delas apareceram nas análises iniciais que fizemos ao resolver a Questão 2 e vamos repetir as respectivas justificativas. Sejam [tex]n[/tex] e [tex]k[/tex] números naturais. Propriedade
1: [tex]\fcolorbox{black}{#e8e8e8}{${\left[ \begin{array}{c} n \\ 0 \end{array} \right]} =0$}\,[/tex], para [tex]n \gt 0\,[/tex]. Propriedade 2: [tex]\fcolorbox{black}{#e8e8e8}{$ {\left[ \begin{array}{c} n \\ k \end{array} \right]} =0$}\,[/tex], para [tex]0 \lt n \lt k\,[/tex]. Propriedade 3: [tex]\fcolorbox{black}{#e8e8e8}{$ {\left[ \begin{array}{c} n \\ n \end{array} \right]} =1 $}\,[/tex], para [tex]n \geqslant 0 \,[/tex]. Propriedade 4: [tex]\fcolorbox{black}{#e8e8e8}{$\left[ \begin{array}{c} n \\ 1 \end{array} \right] =PC_{n} = (n-1)! $}\,[/tex], para [tex]n \gt 0[/tex]. Propriedade 5:
Assim, se [tex]n=2[/tex], também vale a igualdade [tex] {\left[ \begin{array}{c} n \\ n-1 \end{array} \right]} ={\left( \begin{array}{c} n\\ 2 \end{array} \right)} [/tex] e, portanto: [tex]\fcolorbox{black}{#e8e8e8}{${\left[ \begin{array}{c} n \\ n-1 \end{array} \right]} ={\left( \begin{array}{c} n\\ 2 \end{array} \right)} $}\,[/tex], para [tex]n \gt 1[/tex]. Propriedade 6: [tex]\fcolorbox{black}{#e8e8e8}{${\left[ \begin{array}{c} n \\ k \end{array} \right]} ={\left[ \begin{array}{c} n -1\\ k-1 \end{array} \right]} + (n-1) {\left[ \begin{array}{c} n -1\\ k \end{array} \right]}\,$}\,[/tex], para [tex] 1\lt k \lt n\,[/tex]. Para finalizar, Atividade 12: Calcule os seguintes números de Stirling: Atividade 13: Use as propriedades para calcular: Atividade 14: Liste as possibilidades de três pessoas, [tex]p_{1}, p_{2}, p_3[/tex], sentarem-se em duas mesas circulares idênticas, de modo que nenhuma das mesas fique vazia. Atividade 15: Use o conceito de número de Stirling do primeiro tipo para responder a seguinte pergunta:
Uma atividade extra: Você conseguiu calcular de quantas maneiras podemos distribuir quatro objetos distintos em duas caixas idênticas, sem que nenhuma caixa fique vazia? O que é o que é que dá muitas voltas e não sai do lugar?Dá muitas voltas e não sai do lugar? Resposta: o relógio.
O que é que quanto maior é menos se vê?19- O que é, o que é que quanto maior é, menos se vê? Resposta: A escuridão.
O que é o que é todo mundo leva todo mundo tem porque a cada um é dado quando ao mundo vem?Todo mundo leva, Todo mundo tem, Porque a todos lhes dão um Quando ao... Charada. Quando ao mundo vem. Resposta: Nome.
O que é que está no meio do começo No começo do meio e no fim do fim?O que é que está no meio do começo, no começo do meio, e no final do fim? Resposta: A letra M.
|