Desvendando as Partições de um Inteiro

Imagine que você tem seis blocos de montar idênticos. De quantas maneiras diferentes você pode agrupá-los, sem se importar com a ordem dos grupos ou dos blocos dentro de cada grupo? Ou, de forma ainda mais prática: se você tem 5 balas idênticas e quer distribuí-las entre 3 crianças que você não consegue distinguir entre si (ou seja, não importa qual criança recebe qual grupo de balas), de quantas maneiras diferentes você pode fazer essa distribuição?

Essa é a essência do que chamamos de partições de um inteiro.

O que são partições?

Uma partição de um inteiro positivo n é uma forma de representá-lo como uma soma de inteiros positivos. Por exemplo, o número 5 pode ser escrito de diversas maneiras como uma soma:

  5

  4 + 1

  3 + 2

  3 + 1 + 1

  2 + 2 + 1

  2 + 1 + 1 + 1

  1 + 1 + 1 + 1 + 1

No estudo das partições, temos as partições ordenadas (também chamadas de composições) e as partições não-ordenadas. Nas partições ordenadas, a sequência das parcelas importa; assim, 3 + 2 e 2 + 3 seriam consideradas diferentes. No entanto, para a maior parte das aplicações, estamos interessados nas partições não-ordenadas, onde a ordem das parcelas não importa. Por convenção, representamos as partições não-ordenadas listando as parcelas em ordem decrescente.

Para o número 5, por exemplo, existem sete partições possíveis, conforme listado acima. A quantidade de partições de um inteiro n é denotada pela função p(n). Assim, p(5)=7. Além disso, por definição, p(0)=1.

Diagrama de Ferrers

Para tornar as partições mais concretas e facilitar sua análise, utilizamos uma ferramenta visual chamada Diagrama de Ferrers (ou Diagrama de Young). Dado uma partição [m]a_{1}+a_{2}+⋯+a_{k}[/m] de um inteiro n, o diagrama de Ferrers é construído colocando-se pontos (ou caixas quadradas) em linhas, alinhados à esquerda. Cada linha i contém ai pontos, representando a parcela ai, e as linhas são dispostas de cima para baixo.

Por exemplo, a partição 7=3+2+1+1 pode ser visualizada da seguinte forma em seu Diagrama de Ferrers:

● ● ●

● ●

●

●

Aqui, a primeira linha tem 3 pontos, a segunda 2, e a terceira e quarta têm 1 ponto cada.

Uma propriedade interessante dos Diagramas de Ferrers é a possibilidade de derivar a partição conjugada de uma partição original. A partição conjugada é obtida "lendo" as colunas do diagrama de Ferrers como se fossem novas linhas. É como "transpor" o diagrama, refletindo-o em relação à sua diagonal principal.

Continuando com o exemplo 7=3+2+1+1:

Seu Diagrama de Ferrers é:

● ● ●

● ●

●

●

Ao ler as colunas, obtemos:

• Primeira coluna: 4 pontos
• Segunda coluna: 2 pontos
• Terceira coluna: 1 ponto

Assim, a partição conjugada de 7=3+2+1+1 é 7=4+2+1. É importante notar que, se você conjugar uma partição duas vezes, você retorna à partição original.

Uma partição é chamada autoconjugada se ela é igual à sua própria partição conjugada. Isso significa que seu Diagrama de Ferrers permanece o mesmo quando refletido sobre sua diagonal principal.

Um exemplo de partição autoconjugada é 6=3+2+1.

Seu Diagrama de Ferrers é:

● ● ●

● ●

●

Ao conjugar, lendo as colunas, obtemos 3+2+1 novamente. Isso demonstra sua natureza autoconjugada. Outros exemplos incluem (4,3,2,1) para o número 10 e (5,1,1,1,1) para o número 9. Uma curiosidade é que o número de partições autoconjugadas de n é igual ao número de partições de n em partes ímpares e distintas.

Função de Partição p(n)

Como mencionado, p(n) denota o número de partições de um inteiro n. Esta sequência de números cresce rapidamente, sendo tão frequente em seu surgimento no mundo físico quanto os famosos números de Fibonacci.

Aqui estão alguns valores iniciais de p(n):

p(1)=1 (1)

p(2)=2 (2, 1+1)

p(3)=3 (3, 2+1, 1+1+1)

p(4)=5 (4, 3+1, 2+2, 2+1+1, 1+1+1+1)

p(5)=7 (conforme exemplos acima)

p(6)=11

p(7)=15

p(8)=22

Matemáticos como G.H. Hardy e Srinivasa Ramanujan desenvolveram uma fórmula assintótica que estima o valor de p(n) para grandes n. Para n tendendo ao infinito, p(n) é aproximadamente [m]\frac{1}{4n\sqrt{3}} e^{\pi\sqrt{\frac{2n}{3}}}[/m]. Essa fórmula revela que, para n=200, p(200) já é aproximadamente $3.9 \times 10^{12}$.

A Identidade de Euler sobre Partições

Leonhard Euler, um dos maiores matemáticos de todos os tempos, descobriu uma identidade notável que conecta dois tipos de partições. A Identidade de Euler afirma que, para qualquer inteiro natural n, o número de partições de n em partes distintas (onde todas as parcelas são diferentes entre si) é igual ao número de partições de n em partes ímpares (onde todas as parcelas são números ímpares).

Vamos ilustrar isso com um exemplo para n=5:

Partições de 5 em partes distintas (todas as parcelas são diferentes):

5

4 + 1

3 + 2

Portanto, o número de partições de 5 em partes distintas é 3.

Partições de 5 em partes ímpares (todas as parcelas são números ímpares):

5

3 + 1 + 1

1 + 1 + 1 + 1 + 1

Portanto, o número de partições de 5 em partes ímpares é 3.

Como podemos ver, para n=5, ambos os números são iguais a 3, confirmando a identidade de Euler.

Aplicações

As partições de inteiros têm diversas aplicações, especialmente em problemas de combinatória que envolvem a distribuição de objetos. Um exemplo direto é a conexão com a forma de arranjar objetos indistinguíveis em locais indistinguíveis. Quando você distribui bolas idênticas em caixas idênticas, o que realmente importa é apenas o número de bolas em cada caixa, não a ordem ou qual caixa é qual.

Por exemplo, o número de maneiras de colocar r bolas iguais em n caixas iguais (sem que nenhuma caixa fique vazia) é exatamente p(r, n), a função de partição de r em n partes. Se permitirmos caixas vazias e considerarmos n caixas iguais a r (ou seja, o número máximo de partes), o número de maneiras de colocar r bolas iguais é p(r).

Referências

AZENHAS, Olga. Matemática Discreta: Enumeração. Coimbra: Universidade de Coimbra, 2024.

DU SAUTOY, Marcus. A Música dos Números Primos. Rio de Janeiro: Jorge Zahar Ed., 2007.

LUCAS, George. Introdução à teoria das partições de inteiros. In: XXIII SEMANA OLÍMPICA – Nível 3.

MIÉR, Anna de. Lecture notes for “Enumerative Combinatorics”. Oxford: University of Oxford, 2006.

PELLEGRINI, Jerônimo C. Complemento para a disciplina de Matemática Discreta.