UFRPE-DM Permutações Caóticas com Repetições

Seção 2.3 Permutações Caóticas com Repetições

Subseção 2.3.1 Permutações Caóticas com Repetições

Definição 2.3.1.

Uma permutação caótica com repetição é uma permutação, na qual, os elementos nem podem ocupar suas posições originais, nem as posições de seus elementos repetidos.

Por exemplo, MARAAEL é uma permutação caótica (com repetição) das letras da palavra AMARELA. Note que as letras A’s não podem ocupar as posições 1, 3 ou 7.

Exemplo 2.3.2.

Quantos são os anagramas da palavra AMARELA, sem que as letras fiquem nas posições originais?

Tecnologia 2.3.3.

Usando o Sage, podemos obter a resposta desse problema sem dificuldade alguma. Com o código abaixo, basta clicar em "Evaluate (Sage)" para obter a resposta.

Ao longo dessa seção, esse problema está resolvido sem depender do uso de um computador/software. Porém, alguns códigos estão disponíveis, apenas para facilitar/conferir contas que podem ser feitas à mão. A solução foi desenvolvida de forma que a mesma ideia se aplique em casos mais gerais, no qual, mais de uma letra distinta se repete.

Para resolver o Exemplo 2.3.2, observe que o número de soluções para a palavra AMARELA é o mesmo que o número de soluções para a "palavra" AAAMREL, pois uma palavra é um anagrama da outra, então para cada permutação caótica de AAAMREL, podemos obter uma única permutação caótica da palavra AMARELA, apenas aplicando a mesma permutação que leva AAAMREL em AMARELA.

Vamos contar o número de permutações caóticas de AAAMREL para facilitar a explicação. Inicialmente troque AAAMREL por A\(_1\)A\(_2\)A\(_3\)MREL, pois assim todas as letras ficam diferentes, depois resolvemos o problema das permutações das letras A. Em seguida colocamos a palavra em um tabuleiro e usamos torres para representar as permutações. Cada permutação da palavra é representada por uma única forma de colocar \(7\) torres em um tabuleiro \(7\times 7\text{,}\) de forma que uma torre não possa atacar a outra, ou seja, em linhas e colunas diferentes. Por exemplo

fica com a seguinte configuração no tabuleiro:

Figura 2.3.5. Tabuleiro da permutação MRELA\(_1\)A\(_2\)A\(_3\text{.}\)

Para uma permutação simples, as torres podem ocupar qualquer quadrado, desde que uma não possa atacar a outra. No nosso caso, os quadrados cinzas são os lugares que não queremos colocar as torres, pois assim estamos evitando os casos em que alguma letra fica em seu lugar original. Chamaremos de subtabuleiro proibido, o subtabuleiro que não queremos colocar as torres.

Defina \(B_k = \) colocações de torres, na qual, a torre da linha \(k\) está em um subtabuleiro proibido.

A resposta do nosso problema será dado por

\begin{equation*} \frac{\#(B_1\cup B_2\cup \cdots \cup B_7)^c}{3!}, \end{equation*}

ou seja, o número de elementos do complementar de \((B_1\cup B_2\cup \cdots \cup B_7)\text{,}\) dividido pelo número de maneiras de permutar as letras \(A_1, A_2, A_3\text{.}\)

Pelo princípio da Inclusão-Exclusão, isso pode ser calculado da seguinte maneira:

\begin{equation} 7! - \sum_{i=1}^7 \#B_i + \sum_{0\lt i \lt j\leq 7}\#(B_i\cap B_j)+\cdots+(-1)^{7}\#(B_1\cap \cdots\cap B_7).\tag{2.3.1} \end{equation}

A seguir, será mostrado que cada somatório da equação (2.3.1) envolvendo interseções de \(k\) conjuntos, pode ser calculado pelo produto de um valor \(r_k\text{,}\) a ser determinado, pelo fatorial de \((7-k)\text{.}\) Observe que

\begin{equation*} \sum_{i=1}^7 \#B_i = r_1\cdot (7-1)! \end{equation*}

com \(r_1=13\text{,}\) pois se \(i\in \{1 ,2, 3\}\) temos 3 opções para colocar a torre na linha \(i\text{,}\) sobrando 6 torres para colocar cada uma em uma linha, logo \(\#B_i = 3\cdot 6!\text{.}\) Para \(j\in \{4, 5, 6, 7\}\text{,}\) \(\#B_j = 6!\text{,}\) pois temos apenas um lugar para colocar a torre na linha \(j\text{,}\) sobrando 6 torres para colocar cada uma em uma linha. Portanto, o valor do somatório é dado por

\begin{equation*} 3\cdot 6!+3\cdot 6!+3\cdot 6!+6!+6!+6!+6! = 13\cdot 6!. \end{equation*}

Seguindo com esse raciocínio, temos

\begin{equation*} \sum_{0\lt i\lt j\leq 7} \#(B_i\cap B_j) = r_2\cdot (7-2)! \end{equation*}

\begin{equation*} \vdots \end{equation*}

\begin{equation*} \#(B_1\cap \cdots \cap B_7) = r_7\cdot (7-7)! \end{equation*}

O problema agora é determinar os valores de cada \(r_i\text{.}\) Uma forma prática de fazer isso é usando o polinômio de torre:

Definição 2.3.6.

Seja \(T\) um tabuleiro qualquer. O polinômio de torre de \(T\) é definido como

\begin{equation*} R(x, T) = \sum_{k=0}^n r_k(T)x^k, \end{equation*}

no qual, \(r_k(T)\) é o número de maneiras de colocar \(k\) torres em \(T\text{,}\) de forma que uma torre não possa atacar a outra e \(n\) é o número máximo de torres que é possível colocar em \(T\text{,}\) de forma que uma torre não possa atacar a outra. Em inglês esse polinômio é chamado de Rook Polynomial, para mais informações veja [6.9].

Note que na Definição 2.3.6, o tabuleiro não precisa ser quadrado nem retangular, pode inclusive ser um tabuleiro formado apenas pela parte cinza do tabuleiro da Figura 2.3.5.

Teorema 2.3.7.

Seja \(T\) um tabuleiro \(n\times n\text{,}\) sem subtabuleiros proibidos. O polinômio de torre de \(T\) é dado por:

\begin{equation*} R(x, T) = \sum_{k=0}^n\left(C_n^k\right)^2\cdot k!\cdot x^k. \end{equation*}

Demonstração.

Precisamos escolher \(k\) linhas e \(k\) colunas no tabuleiro \(T\text{,}\) \(n\times n\text{,}\) para colocar as torres, de modo que uma torre não possa atacar a outra, isto pode ser feito de \(\left(C_n^k\right)^2\) maneiras. Agora precisamos escolher a posição da linha 1 na qual será colocada a primeira torre, isso pode ser feito de \(k\) maneiras, em seguida, precisamos escolher a posição da linha 2 na qual será colocada a segunda torre, o que pode ser feito de \((k-1)\) maneiras, e assim por diante, até ficarmos com uma maneira de escolher a \(k\)-ésima torre.

Assim, pelo princípio multiplicativo, o número de maneiras de colocar \(k\) torres em \(T\text{,}\) de modo que uma torre não possa atacar a outra é

\begin{equation*} \left(C_n^k\right)^2\cdot k!. \end{equation*}

Exemplo 2.3.8.

Sejam \(T^i\text{,}\) tabuleiros \(i\times i\text{,}\) \(i = 1, 2, 3\text{,}\) então

\begin{align*} R(x, T^1)= \amp ~ x+1. \\ R(x, T^2)= \amp ~ 2x^2 + 4x +1. \\ R(x, T^3)= \amp ~ 6x^3 + 18x^2 + 9x +1. \end{align*}

Tecnologia 2.3.9.

A seguir, temos os códigos para gerar o polinômio de torre de um tabuleiro \(n\times n\text{.}\) Na linha 1, definimos uma matriz \(4\times 4\) de uns e guardamos na variável B. Para obter o polinômio de torre de um tabuleiro quadrado diferente, troque o número 4 da linha 1 pelo valor desejado e clique em "Evaluate (Sage)".

Definição 2.3.10.

Dizemos que a união de dois tabuleiros \(T_1\) e \(T_2\) é uma união disjunta, quando nenhum quadrado de \(T_1\) está na mesma linha ou mesma coluna de \(T_2\text{.}\)

Exemplo 2.3.11.

Sejam \(T^i\text{,}\) tabuleiros \(i\times i\text{,}\) \(i = 1, 2\text{,}\) então o polinômio de torre da união disjunta \(T^2\cup T^1\) é o produto dos polinômios de torre de \(T^2\) e \(T^1\text{.}\)

Solução.

O polinômio de torre \(R(x, T^2\cup T^1)\) pode ser obtido fazendo todas as figuras, da seguinte forma:

Figura 2.3.12. Polinômio de Torre do tabuleiro \(T^2\cup T^1\text{.}\)

Calculando o produto dos polinômios de torre de \(T^2\) e \(T^1\text{,}\) obtemos

\begin{align*} R(x, T^2)\cdot R(x, T^1)= \amp ~ (2x^2+4x+1)(x+1) \\ = \amp ~ 2x^3+6x^2+5x+1. \end{align*}

Portanto,

\begin{equation*} R(x, T^2\cup T^1) = R(x, T^2)\cdot R(x, T^1). \end{equation*}

Proposição 2.3.13.

O polinômio de torre da união disjunta de dois tabuleiros é dado pelo produto dos polinômios de torre de cada um dos tabuleiros.

Demonstração.

Seja \(T\) um tabuleiro obtido pela união disjunta de dois tabuleiros \(T_1\) e \(T_2\text{.}\)

Para colocar \(k\) torres em \(T\text{,}\) de forma que uma torre não possa atacar a outra, podemos colocar \(r_{k-i}(T_1)\text{,}\) \(0\leq i \leq k\text{,}\) torres em \(T_1\text{,}\) de forma que uma não possa atacar a outra, e \(r_{i}(T_2)\) torres em \(T_2\text{,}\) de forma que uma não possa atacar a outra. Dessa forma, dados duas torres quaisquer em \(T\text{,}\) na configuração obtida anteriormente, uma não pode atacar a outra. Portanto, o número de maneiras de colocarmos \(k\) torres em \(T\) é dado por

\begin{equation*} r_k(T) = \sum_{i=0}^k r_{k-i}(T_1)r_i(T_2). \end{equation*}

Logo,

\begin{align*} R(x, T) = \amp ~ \sum_{k=0}^nr_k(T)x^k \\ = \amp ~ \sum_{k=0}^n\sum_{i=0}^kr_{k-i}(T_1)r_i(T_2)x^k \\ = \amp ~ \left( \sum_{s=0}^pr_s(T_1)x^s \right)\left( \sum_{t=0}^qr_t(T_2)x^t \right) \\ = \amp ~ R(x, T_1)\cdot R(x, T_2). \end{align*}

Tecnologia 2.3.14.

Aqui temos uma implementação para obter o produto de polinômios de torre. Usamos a ideia apresentada na Tecnologia 2.3.9 para gerar cada polinômio e definimos a função \(\verb|produto_polinomios_torre|\) que multiplica cada um dos polinômios de torre. As entradas da função \(\verb|produto_polinomios_torre|\) são os tamanhos dos tabuleiros. Na linha 8 a função está sendo "chamada" para gerar a polinômio de torre da união disjunta de um tabuleiro \(3\times 3\) e 4 tabuleiros \(1\times 1\text{.}\)

Voltando a solução do Exemplo 2.3.2. Pela Proposição 2.3.13 o polinômio de torre do tabuleiro da palavra AAAMREL é dado por

\begin{equation} R(x, T) = ~ (6x^3 + 18x^2 + 9x +1)(x+1)^4.\tag{2.3.2} \end{equation}

Fazendo as contas, obtemos

\begin{equation} R(x, T) = 6x^{7} + 42x^{6} + 117x^{5} + 169x^{4} + 136x^{3} + 60x^{2} + 13x^1 + 1x^0. \tag{2.3.3} \end{equation}

Observe que eram exatamente os coeficientes desse polinômio que estavam faltando para resolvermos o problema pelo princípio da Inclusão-Exclusão dado pela equação (2.3.1). Então a solução do Exemplo 2.3.2 é dada pelo polinômio de torre dado pela equação (2.3.3), com \(x^k\) substituído por \((-1)^k\cdot(7-k)!\text{,}\) dividido por \(3!\text{,}\) pois temos que descontar o número de formas de ordenar as três letras A. Fazendo as substituições, obtemos:

\begin{equation} 7! -13\cdot6! + 60\cdot5! - 136\cdot4! + 169\cdot 3! - 117\cdot 2! + 42\cdot 1! -6\cdot 0!\tag{2.3.4} \end{equation}

Calculando (2.3.4) e dividido por \(3!\text{,}\) resulta em

\begin{equation*} \frac{432}{6} = 72 \text{ soluções}. \end{equation*}

Tecnologia 2.3.15.

A implementação de uma função que substitui \(x^k\) por \((-1)^k\cdot(n-k)!\) em um polinômio de grau \(n\text{.}\) Na linha 14 a função está sendo "chamada" com o polinômio: \(6x^7 + 42x^6 + 117x^5 + 169x^4 + 136x^3 + 60x^2 + 13x + 1\text{.}\)

Exemplo 2.3.16.

Quantos são os anagramas da palavra MATEMÁTICA, sem que as letras fiquem nas posições originais? (Supondo que A e Á são letras iguais)

Solução.

O polinômio de torre desse caso é dado por

\begin{equation*} (6x^3+18x^2+9x+1)(2x^2+4x+1)^2(x+1)^3. \end{equation*}

Expandindo o polinômio obtemos

\begin{equation*} 1x^0 + 20x^1 + 164x^{2}+ 728x^{3} + 1941x^{4}+ 3260x^{5} + 3514x^{6}+ 2416x^{7}+ 1020x^{8}+ 240x^{9}+24x^{10}. \end{equation*}

Trocando \(x^k\) por \((-1)^k\cdot(10-k)!\) obtemos:

\begin{equation*} 10! - 20\cdot9! + 164\cdot8! - 728\cdot7! + 1941\cdot6! - 3260\cdot5! + 3514\cdot4! - 2416\cdot3! + 1020\cdot2!- 240\cdot1!+24\cdot0! \end{equation*}

Fazendo esse cálculo e dividindo por \(3!\times 2!\times 2!\) chegamos na resposta:

\begin{equation*} \frac{392544}{3!\times 2!\times 2!} = 16356 \text{ soluções}. \end{equation*}

Tecnologia 2.3.17.

A resposta do Exemplo 2.3.16 junto com o polinômio de torre associado está disponível aqui. Troque as informações da lista para obter o número de permutações caóticas de outra palavra desejada.

Obs. Para que o sistema atualize a resposta, basta clicar fora do campo de preenchimento, depois de atualizar os dados.

Figura 2.3.18.

Subseção 2.3.2 Teorema das Permutações Caóticas com Repetições

Na matemática, os polinômios de Laguerre, nomeados em homenagem a Edmond Laguerre (1834-1886), são soluções da equação de Laguerre:

\begin{equation*} xy''+ (1-x)y' + ny = 0 \end{equation*}

que é uma equação diferencial linear de segunda ordem. Esses polinômios surgiram na mecânica quântica, na parte radial da solução da equação de Schrödinger para um átomo de um elétron. Eles também descrevem as funções de Wigner estáticas de sistemas osciladores em mecânica quântica no espaço de fase.

Fonte: en.wikipedia.org/wiki/Laguerre_polynomials

en.wikipedia.org/wiki/Laguerre_polynomials

Os polinômios de torre, em combinatória, são mais ou menos os mesmos que os polinômios de Laguerre, a menos de mudanças elementares de variáveis. Usaremos os polinômios de Laguerre para enunciar um Teorema com uma fórmula para calcular permutações caóticas com repetições usando integrais.

Definição 2.3.19.

Usando recursividade é possível chegar na seguinte forma fechada para os polinômios de Laguerre:

\begin{equation*} L_n(x) = \sum_{k=0}^nC_n^k \frac{(-1)^k}{k!}x^k \end{equation*}

Tecnologia 2.3.20.

Obtendo o polinômio de Laguerre \(L_3(x)\) no Sage.

Teorema 2.3.21.

O número de permutações caóticas, \(DR_n^{r_1, r_2, \ldots, r_k}\text{,}\) de uma lista com \(n\) objetos, com um objeto repetido \(r_1\) vezes, outro objeto repetido \(r_2\) vezes, até o "último" objeto repetido \(r_k\) vezes, tal que \(r_1+r_2+\cdots +r_k = n\text{,}\) pode ser calculado da seguinte maneira:

\begin{equation*} DR_n^{r_1, r_2, \ldots, r_k} = \left|\int_0^\infty e^{-x} L_{r_1}(x)L_{r_2}(x)\cdots L_{r_k}(x) ~dx \right| \end{equation*}

Demonstração.

Como

\begin{equation*} \int_0^\infty e^{-x}x^k~ dx = k! \end{equation*}

o resultado segue.

Mais detalhes em breve.

Tecnologia 2.3.22.

Usando o Teorema 2.3.21 para calcular o número de soluções do Exemplo 2.3.16. Foram usados os métodos abs e integral que calculam o valor absoluto e a integral, respectivamente.

Tecnologia 2.3.23.

A implementação da função DR (derangement with repetition) usando o Teorema 2.3.21. Os parâmetros são as quantidades que cada elemento figura na lista. Por exemplo, para a palavra MATEMATICA usamos a entrada 3, 2, 2, 1, 1, 1, pois são 3 letras A, 2 letras T, 2 letras M, 1 letras E, 1 letra I e 1 letra C.

Exercícios 2.3.3 Exercícios

1.

(PRMO 2019) Diremos que um rearranjo das letras de uma palavra não tem letras fixas, quando o rearranjo é colocado diretamente abaixo da palavra, e nenhuma coluna tem a mesma letra repetida. Por exemplo, HBRATA é um rearranjo sem letras fixas de BHARAT. Quantos rearranjos distinguíveis sem letras fixas que BHARAT tem? (As duas letras A são consideradas idênticas.)

Resposta.

Anterior Top Próximo