Partição de inteiros

thumb|right|300px|Diagramas de Young associados às partições dos inteiros positivos de 1 a 8. Eles estão organizados de modo que as imagens sob a reflexão sobre a diagonal principal do quadrado sejam partições conjugadas. thumb|right|300px|Partições de com a maior parte sendo

Na teoria dos números e na combinatória, uma partição de um inteiro não negativo , também chamada de partição de inteiros, é uma maneira de escrever como uma soma de inteiros positivos. Duas somas que diferem apenas na ordem de suas parcelas são consideradas a mesma partição. (Se a ordem importar, a soma se torna uma composição.) Por exemplo, pode ser particionado de cinco maneiras distintas:

A única partição de zero é a soma vazia, que não possui partes.

A composição dependente da ordem é a mesma partição que , e as duas composições distintas e representam a mesma partição que .

Uma parcela individual em uma partição é chamada de parte. O número de partições de é dado pela função de partição . Portanto, . A notação significa que é uma partição de .

As partições podem ser visualizadas graficamente com diagramas de Young ou diagramas de Ferrers. Elas ocorrem em vários ramos da matemática e da física, incluindo o estudo de polinômios simétricos e do grupo simétrico, bem como na teoria de representação de grupos em geral.

Exemplos As sete partições de 5 são: 5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 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 ou na forma ainda mais compacta , 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 , onde é o número de 1s, é o número de 2s, etc. (Componentes com podem ser omitidos). Por exemplo, nesta notação, as partições de 5 são escritas como e .

Representações diagramáticas de partições 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:

16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*

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:

16px|*16px|*16px|*16px|* 16px|*16px|*16px|*16px|* 16px|*16px|*16px|*16px|* 16px|*16px|*16px|*16px|* 16px|*16px|*16px|*16px|* 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1

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 é 100px enquanto o diagrama de Ferrers para a mesma partição é {| |- style="vertical-align:top; text-align:left;" | 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|* |- style="vertical-align:top; text-align:center;"

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ó..

Função de partição thumb|upright|link=|Usando o método de Euler para encontrar p(40): Uma régua com sinais de mais e menos (caixa cinza) é deslizada para baixo, e as partes relevantes são somadas ou subtraídas. As posições dos sinais são dadas por diferenças de números naturais (azul) e ímpares (laranja) alternados. No [ arquivo SVG,] passe o mouse sobre a imagem para mover a régua.

A função de partição conta as partições de um inteiro não negativo . Por exemplo, porque o inteiro tem as cinco partições , , , e . Os valores desta função para são: 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... .

A função geradora de é

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:

conforme

Em 1937, Hans Rademacher encontrou uma maneira de representar a função de partição pela série convergente

onde

e é a soma de Dedekind.

O inverso multiplicativo de sua função geradora é a função de Euler; pelo teorema dos números pentagonais de Euler, esta função é uma soma alternada de potências de números pentagonais de seu argumento.

Srinivasa Ramanujan descobriu que a função de partição tem padrões não triviais na aritmética modular, hoje conhecidos como as congruências de Ramanujan. Por exemplo, sempre que a representação decimal de terminar no dígito 4 ou 9, o número de partições de será divisível por 5.

Partições restritas 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:

16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|* ↔ 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|* 6 + 4 + 3 + 1 = 4 + 3 + 3 + 2 + 1 + 1

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:

16px|*16px|*16px|*16px|*16px|*   ↔   16px|*16px|*16px|*16px|*16px|*

Pode-se então obter uma bijeção entre o conjunto de partições com partes ímpares distintas e o conjunto de partições autoconjugadas, como ilustrado pelo seguinte exemplo:

16px|o16px|o16px|o16px|o16px|o16px|o16px|o16px|o16px|o

16px|*16px|*16px|*16px|*16px|*16px|*16px|*

16px|x16px|x16px|x ↔ 16px|o16px|o16px|o16px|o16px|o16px|o16px|*16px|*16px|*16px|*16px|o16px|*16px|x16px|x16px|o16px|*16px|x16px|o16px|* 9 + 7 + 3 = 5 + 5 + 4 + 3 + 2 Ímpares dist. autoconjugada

Partes ímpares e partes distintas Entre as 22 partições do número 8, existem 6 que contêm apenas partes ímpares: 7 + 1 5 + 3 5 + 1 + 1 + 1 3 + 3 + 1 + 1 3 + 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

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: 8 7 + 1 6 + 2 5 + 3 5 + 2 + 1 4 + 3 + 1

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).A notação segue 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): 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... .

A função geradora de q(n) é dada por, 24.2.2 eq. I(B)

O teorema dos números pentagonais dá uma recorrência para q:, 24.2.2 eq. II(A) q(k) = ak + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22) − ... onde ak é (−1)m se k = 3m2 − m para algum inteiro m e é 0 caso contrário.

Tamanho restrito da parte ou número de partes

Tomando os conjugados, o número de partições de em exatamente k partes é igual ao número de partições de em que a maior parte tem tamanho . A função satisfaz a recorrência

com os valores iniciais e se ou e e não forem ambos zero.Richard Stanley, Enumerative Combinatorics, volume 1, second edition. Cambridge University Press, 2012. Chapter 1, section 1.7.

Recupera-se a função p(n) através de

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) é

e o número de partições de n em que todas as partes são 1, 2 ou 3 (ou, equivalentemente, o número de partições de n em no máximo três partes) é o inteiro mais próximo a (n + 3)2 / 12.

Partições num retângulo e coeficientes binomiais gaussianos

Pode-se também limitar simultaneamente o número e o tamanho das partes. Seja o número de partições de com no máximo partes, cada uma de tamanho no máximo . Equivalentemente, essas são as partições cujo diagrama de Young cabe dentro de um retângulo . Existe uma relação de recorrência

obtida observando que conta as partições de em exatamente partes de tamanho no máximo , e subtrair 1 de cada parte de tal partição produz uma partição de em no máximo partes.

O coeficiente binomial gaussiano é definido como:

O coeficiente binomial gaussiano está relacionado à função geradora de pela igualdade

Posto e quadrado de Durfee

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:

|- style="vertical-align:top; text-align:left;" | 16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*16px|*

O quadrado de Durfee tem aplicações na combinatória em provas de várias identidades de partição.veja, p. ex., 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 para uma partição de k partes com a maior parte . Essa estatística (que não tem relação com a descrita acima) aparece no estudo das congruências de Ramanujan.

Reticulado de Young