Partição de inteiros
Na teoria dos números e na combinatória, uma partição de um inteiro não negativo n, também chamada de partição de inteiros, é uma maneira de escrever n como uma soma de inteiros positivos. Duas somas que diferem apenas na ordem de suas parcelas são consideradas a mesma partição. Por exemplo, 4 pode ser particionado de cinco maneiras distintas:4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1
Alguns autores tratam uma partição como uma sequência não crescente de parcelas, em vez de uma expressão com sinais de adição. Por exemplo, a partição 2 + 2 + 1 pode, em vez disso, ser escrita como a tupla (2, 2, 1) ou na forma ainda mais compacta (22, 1), onde o sobrescrito indica o número de repetições de uma parte. Esta notação de multiplicidade para uma partição pode ser escrita alternativamente como 1 m 1 2 m 2 3 m 3 ⋯ {\displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots } , onde m1 é o número de 1s, m2 é o número de 2s, etc. (Componentes com mi = 0 podem ser omitidos). Por exemplo, nesta notação, as partições de 5 são escritas como 5 1 , 1 1 4 1 , 2 1 3 1 , 1 2 3 1 , 1 1 2 2 , 1 3 2 1 {\displaystyle 5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1}} e 1 5 {\displaystyle 1^{5}} .
Existem dois métodos diagramáticos comuns para representar partições: como diagramas de Ferrers, em homenagem a Norman Macleod Ferrers, e como diagramas de Young, em homenagem a Alfred Young. Ambos possuem várias convenções possíveis; aqui, usamos a notação inglesa, com os diagramas alinhados no canto superior esquerdo.
Diagrama de Ferrers
A partição 6 + 4 + 3 + 1 do número 14 pode ser representada pelo seguinte diagrama: Os 14 círculos estão alinhados em 4 linhas, cada uma tendo o tamanho de uma parte da partição. Os diagramas para as 5 partições do número 4 são mostrados abaixo:
Diagrama de Young
Uma representação visual alternativa de uma partição de inteiros é o seu diagrama de Young (frequentemente também chamado de diagrama de Ferrers). Em vez de representar uma partição com pontos, como no diagrama de Ferrers, o diagrama de Young usa caixas ou quadrados. Assim, o diagrama de Young para a partição 5 + 4 + 1 é enquanto o diagrama de Ferrers para a mesma partição é Embora esta variação aparentemente trivial não pareça digna de menção separada, os diagramas de Young revelam-se extremamente úteis no estudo de funções simétricas e da teoria de representação de grupos: o preenchimento das caixas dos diagramas de Young com números (ou, por vezes, objetos mais complicados) obedecendo a várias regras leva a uma família de objetos chamados quadros de Young (Young tableaux), e esses quadros têm importância na combinatória e na teoria das representações. Como um tipo de forma composta por quadrados adjacentes unidos, os diagramas de Young são um tipo especial de poliominó.
A função de partição p ( n ) {\displaystyle p(n)} conta as partições de um inteiro não negativo n {\displaystyle n} . Por exemplo, p ( 4 ) = 5 {\displaystyle p(4)=5} porque o inteiro 4 {\displaystyle 4} tem as cinco partições 1 + 1 + 1 + 1 {\displaystyle 1+1+1+1} , 1 + 1 + 2 {\displaystyle 1+1+2} , 1 + 3 {\displaystyle 1+3} , 2 + 2 {\displaystyle 2+2} e 4 {\displaystyle 4} . Os valores desta função para n = 0 , 1 , 2 , … {\displaystyle n=0,1,2,\dots } são: A função geradora de p {\displaystyle p} é Nenhuma expressão em forma fechada para a função de partição é conhecida, mas ela possui tanto expansões assintóticas que a aproximam com precisão quanto relações de recorrência pelas quais pode ser calculada exatamente. Ela cresce como uma função exponencial da raiz quadrada do seu argumento, como se segue: Em 1937, Hans Rademacher encontrou uma maneira de representar a função de partição p ( n ) {\displaystyle p(n)} pela série convergente
Tanto na combinatória quanto na teoria dos números, famílias de partições sujeitas a várias restrições são frequentemente estudadas. Esta seção examina algumas dessas restrições.
Partições conjugadas e autoconjugadas
Se virarmos o diagrama da partição 6 + 4 + 3 + 1 ao longo de sua diagonal principal, obtemos outra partição de 14: Ao transformar as linhas em colunas, obtemos a partição 4 + 3 + 3 + 2 + 1 + 1 do número 14. Tais partições são ditas conjugadas uma da outra. No caso do número 4, as partições 4 e 1 + 1 + 1 + 1 são pares conjugados, e as partições 3 + 1 e 2 + 1 + 1 são conjugadas entre si. De particular interesse são as partições, como 2 + 2, que têm a si mesmas como conjugadas. Tais partições são chamadas de autoconjugadas. Afirmação: O número de partições autoconjugadas é o mesmo que o número de partições com partes ímpares distintas. Prova (esboço): A observação crucial é que cada parte ímpar pode ser "dobrada" no meio para formar um diagrama autoconjugado:
Partes ímpares e partes distintas
Entre as 22 partições do número 8, existem 6 que contêm apenas partes ímpares: Alternativamente, poderíamos contar as partições em que nenhum número ocorre mais de uma vez. Tal partição é chamada de partição com partes distintas. Se contarmos as partições de 8 com partes distintas, também obtemos 6: Esta é uma propriedade geral. Para cada número positivo, o número de partições com partes ímpares é igual ao número de partições com partes distintas, denotado por q(n). Este resultado foi provado por Leonhard Euler em 1748 e mais tarde foi generalizado como o Teorema de Glaisher. Para todo tipo de partição restrita existe uma função correspondente para o número de partições que satisfazem a dada restrição. Um exemplo importante é q(n) (partições em partes distintas). Os primeiros valores de q(n) são (começando com q(0)=1):
Tamanho restrito da parte ou número de partes
Tomando os conjugados, o número pk(n) de partições de n em exatamente k partes é igual ao número de partições de n em que a maior parte tem tamanho k. A função pk(n) satisfaz a recorrência com os valores iniciais p0(0) = 1 e pk(n) = 0 se n ≤ 0 ou k ≤ 0 e n e k não forem ambos zero. Uma possível função geradora para tais partições, tomando k fixo e n variável, é De forma mais geral, se T é um conjunto de inteiros positivos, então o número de partições de n, cujas partes pertencem todas a T, tem a função geradora Isso pode ser usado para resolver problemas de troco (onde o conjunto T especifica as moedas disponíveis). Como dois casos particulares, tem-se que o número de partições de n em que todas as partes são 1 ou 2 (ou, equivalentemente, o número de partições de n em 1 ou 2 partes) é
Partições num retângulo e coeficientes binomiais gaussianos
Pode-se também limitar simultaneamente o número e o tamanho das partes. Seja p(N, M; n) o número de partições de n com no máximo M partes, cada uma de tamanho no máximo N. Equivalentemente, essas são as partições cujo diagrama de Young cabe dentro de um retângulo M × N. Existe uma relação de recorrência p ( N , M ; n ) = p ( N , M − 1 ; n ) + p ( N − 1 , M ; n − M ) {\displaystyle p(N,M;n)=p(N,M-1;n)+p(N-1,M;n-M)} obtida observando que p ( N , M ; n ) − p ( N , M − 1 ; n ) {\displaystyle p(N,M;n)-p(N,M-1;n)} conta as partições de n em exatamente M partes de tamanho no máximo N, e subtrair 1 de cada parte de tal partição produz uma partição de n − M em no máximo M partes.
O posto (ou rank) de uma partição é o maior número k tal que a partição contenha pelo menos k partes de tamanho pelo menos k. Por exemplo, a partição 4 + 3 + 3 + 2 + 1 + 1 tem posto 3 porque contém 3 partes que são ≥ 3, mas não contém 4 partes que são ≥ 4. No diagrama de Ferrers ou diagrama de Young de uma partição de posto r, o quadrado r × r de entradas no canto superior esquerdo é conhecido como o quadrado de Durfee: O quadrado de Durfee tem aplicações na combinatória em provas de várias identidades de partição. Ele também tem algum significado prático na forma do índice h. Uma estatística diferente também é chamada às vezes de posto de uma partição (ou posto de Dyson), a saber, a diferença λ k − k {\displaystyle \lambda _{k}-k} para uma partição de k partes com a maior parte λ k {\displaystyle \lambda _{k}} . Essa estatística (que não tem relação com a descrita acima) aparece no estudo das congruências de Ramanujan.
Existe uma ordem parcial natural nas partições dada pela inclusão de diagramas de Young. Esse conjunto parcialmente ordenado é conhecido como reticulado de Young. O reticulado foi originalmente definido no contexto da teoria de representação, onde é usado para descrever as representações irredutíveis dos grupos simétricos Sn para todo n, juntamente com suas propriedades de ramificação, em característica zero. Ele também tem recebido um estudo significativo por suas propriedades puramente combinatórias; notavelmente, é o exemplo motivador de um poset diferencial.
Existe uma teoria profunda de partições aleatórias escolhidas de acordo com a distribuição de probabilidade uniforme sobre o grupo simétrico por meio da correspondência de Robinson-Schensted. Em 1977, Logan e Shepp, bem como Vershik e Kerov, mostraram que o diagrama de Young de uma grande partição típica torna-se assintoticamente próximo ao gráfico de uma certa função analítica minimizando um determinado funcional. Em 1988, Baik, Deift e Johansson estenderam esses resultados para determinar a distribuição da subsequência crescente mais longa de uma permutação aleatória em termos da distribuição de Tracy-Widom. Okounkov relacionou esses resultados à combinatória de superfícies de Riemann e à teoria da representação.
