Just another WordPress.com site

Partições de Inteiros

Este problema trata de partições de números inteiros, que é apenas um termo técnico significando “jeito de escrever um número como soma de outros números”. Por exemplo, 2+3 é uma partição de 5. Como a adição é comutativa, convencionamos que 3+2 e 2+3 são “a mesma” partição de 5; por exemplo, 4 tem cinco partições no total (cada linha abaixo conta como uma partição só):

1+1+1+1

2+1+1 = 1+2+1 = 1+1+2

2+2

3+1 = 1+3

4

Para cada número natural n, denotamos por P(n) o conjunto das partições de n. Um elemento típico de P(n) será denotado \pi. Algumas estatísticas de partições são estudadas em matemática, isto é, funções cujos argumentos são partições e que retornam números. Uma possível estatística seria a função \mathrm{min} : P(n) \to \mathbb{N}, que retorna o menor elemento de uma partição. Por exemplo, \mathrm{min}(1+2+1) = 1.

Há algumas estatísticas menos óbvias, mas com relações interessantes entre si. Por exemplo, se \pi \in P(n), defina

U(\pi) = número de 1s que aparecem em \pi;

D(\pi) = número de números distintos em \pi.

Por exemplo, U(1+1+1+1) = 4, e D(1+3)=2. O primeiro problema é demonstrar que

\sum_{\pi\in P(n)} U(\pi) = \sum_{\pi\in P(n)} D(\pi)

para qualquer n. Em palavras: somando o número de 1s que aparece em todas as partições possíveis de n, obtém-se o mesmo resultado que somando o número de elementos distintos em cada partição. Para n=4, estas duas somas valem 7. (Confira!)

O segundo problema é sobre estatísticas do próprio P(n). Defina I(n) como o número de partições de n que consistem apenas de números ímpares; e.g. I(4) = 2. Defina S(n) como o número de partições de n sem elementos repetidos, como 1+3 (mas não 1+1+2); e.g. S(4) = 2.

O desafio agora é demonstrar que I(n) = S(n) para qualquer n.

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s