
Leonardo Tambellini

Sistemas Dinâmicos Finitos: Paciência Búlgara
(Shift em Partições e Composições ćıclicas)

São José do Rio Preto

2013


Leonardo Tambellini

Sistemas Dinâmicos Finitos: Paciência Búlgara
(Shift em Partições e Composições ćıclicas)

Dissertação apresentada como parte dos requisitos para

obtenção do t́ıtulo de Mestre em Matemática, junto ao

Programa de Pós-Graduação em Matemática, do Insti-

tuto de Biociências, Letras e Ciências Exatas da Uni-

versidade Estadual Paulista “Júlio de Mesquita Filho”,

Câmpus de São José do Rio Preto.

Orientador: Prof. Dr. Vanderlei Minori Horita

São José do Rio Preto

2013


Tambellini, Leonardo. 
Sistemas dinâmicos finitos : paciência búlgara (Shift em partições e 

composições cíclicas) / Leonardo Tambellini. - São José do Rio Preto : 
[s.n.], 2013. 

80 f. : il. ; 30 cm. 

Orientador: Vanderlei Minori Horita 
Dissertação (mestrado) - Universidade Estadual Paulista “Júlio de 

Mesquita Filho”, Instituto de Biociências, Letras e Ciências Exatas 
            

1. Sistemas dinâmicos diferenciais.  2. Teoria dos números.  3. 
Partições (Matemática)  4. Paciência búlgara.  I. Horita, Vanderlei 
Minori.  II. Universidade Estadual Paulista “Júlio de Mesquita Filho”, 
Instituto de Biociências, Letras e Ciências Exatas.  III. Título.

                CDU - 517.93 

                                 Ficha catalográfica elaborada pela Biblioteca do IBILCE 
                                         Campus de São José do Rio Preto - UNESP

     
Leonardo Tambellini

Sistemas Dinâmicos Finitos: Paciência Búlgara
(Shift em Partições e Composições ćıclicas)

Dissertação apresentada como parte dos requisitos para

obtenção do t́ıtulo de Mestre em Matemática, junto ao

Programa de Pós-Graduação em Matemática, do Insti-

tuto de Biociências, Letras e Ciências Exatas da Uni-

versidade Estadual Paulista “Júlio de Mesquita Filho”,

Câmpus de São José do Rio Preto.

Comissão Examinadora

Prof. Dr. Vanderlei Minori Horita

Orientador

UNESP - IBILCE

Prof. Dr. Carlos Gustavo T. de A. Moreira

IMPA - RJ

Prof. Dr. Claudio Aguinaldo Buzzi

UNESP - IBILCE

São José do Rio Preto

26 de junho de 2013


À minha famı́lia.

Dedico.


AGRADECIMENTOS

Ao concluir este trabalho, deixo meus sinceros agradecimentos:

Aos meus pais, Domingos e Angélica, e à minha irmã Natália, por todo o apoio.

À minha companheira de longa data, Jeanne, pelo amor, paciência e motivação durante

todos esses anos.

À todos os agregados, moradores e frequentadores da república Kurupi, pelos bons momentos

que passamos nos inúmeros churrascos, almoços, cervejadas...

Aos meus amigos e colegas de trabalho do Departamento de Matemática do IBILCE.

Aos professores que fizeram parte da banca examinadora, Vanderlei, Claudio Buzzi e Gugu.

Aos meus amigos de graduação e pós-graduação.

À CNPq, pelo aux́ılio financeiro.

E à todos que de alguma forma contribúıram para a conclusão deste trabalho.


“A Matemática é o alfabeto com o qual Deus escreveu o Universo.”

(Galileo Galilei)


Resumo

Neste trabalho abordamos um tema introdutório na interseção de duas áreas da Matemáticas,

Sistemas Dinâmicos e Teoria dos Números. Através de um jogo aparentemente ingênuo, a

Paciência Búlgara, estudamos dinâmicas em conjuntos finitos. Devido à finitude do domı́nio,

todos os pontos do sistema convergem para uma órbita periódica, mas interessante é saber

quantas órbitas distintas o sistema apresenta em função da quantidade de elementos do domı́nio.

Outra pergunta natural é sobre o tempo de convergência a estas órbitas. Estudamos também

uma variação deste jogo, a Paciência Carolina.

Palavras-chave: Paciência Búlgara. Partições de Inteiros. Aplicação Shift. Paciência

Carolina.


Abstract

This work refers to a introductory topic in the intersection of two areas in Mathematics, Dynam-

ical Systems and Number Theory. Motivated to a game seemingly naive, Bulgarian Solitaire,

we study dynamics in finite sets. Due to the finiteness of the domain, all points of the sys-

tem converge to a periodic orbit, but it is interesting to know how many distinct orbits the

system displays depending on the size of the domain. Another natural question is about the

convergence time of these orbits. We also study a variation of this game, Carolina Solitaire.

Keywords: Bulgarian Solitaire. Integer Partitions. Shift application. Carolina Solitaire.


Sumário

Introdução 10

1 Conceitos Inicias 13

2 Paciência Búlgara 15

2.1 Partições e aplicação B-shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Partições ćıclicas, dB(λ) e DB(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3 Plotando diagramas através do software “Wolfram Mathematica” . . . . . . . . 20

2.4 Caracterização das Partições Ćıclicas . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5 Quantidade de Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.6 Partição raiz, gerada, pré-ćıclica e caracterizações . . . . . . . . . . . . . . . . . 34

2.7 Cálculo de DB(n) para números triangulares . . . . . . . . . . . . . . . . . . . . 38

2.8 Cálculo de Limites de DB(n) para números não triangulares . . . . . . . . . . . 49

2.9 Conjectura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3 Paciência Carolina: Uma variação da Paciência Búlgara 60

3.1 Composições e aplicação C-shift . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.2 Composições ćıclicas, dC(λ) e DC(n) . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.3 Caracterização das Composições Ćıclicas . . . . . . . . . . . . . . . . . . . . . . 64

3.4 Cálculo de DC(n) para números triangulares . . . . . . . . . . . . . . . . . . . . 68

3.5 Cálculo de Limites de DC(n) para números não triangulares . . . . . . . . . . . 70

3.6 Conjectura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79


Introdução

Antes de começarmos com a matemática, vamos a um breve histórico do surgimento do pro-

blema que será estudado.

Em meados de 1980, em uma viagem de trem de Moscou à São Petersburgo:

− Olá, para você que é um matemático deixe-me mostrar uma coisa interessante - disse o

estranho sem nome no trem.

Mas eu estou tentando trabalhar na minha palestra, pensei. Enquanto o trem percorria os

trilhos, o homem sentado à minha frente me olhava ansioso. OK, vamos acabar logo com isso.

− Aqui temos 15 cartas de um baralho, divida-as em quantas pilhas quiser, e em cada pilha

coloque quantas cartas quiser.

E eu as dividi em pilhas de tamanho 3, 1, 4, 1, 6.

− Agora retire uma carta de cada pilha e forme uma nova pilha com estas cartas.

A operação me deixou com pilhas de 3−1 = 2 cartas, 4−1 = 3 cartas, 6−1 = 5 cartas, duas

pilhas vazias e uma nova pilha de 5 cartas. Eu percebi que a ordem das pilhas não importava,

então por convenção, as coloquei em ordem não crescente, 5, 5, 3, 2.

− Agora repita isso de novo e de novo. Eu sei o que vai acontecer − e assim o homem olhou

para o outro lado, onde não estavam as cartas.

Ele já conseguiu pensar através das iterações? Quanto tempo isso levará?. Eu estava curioso

agora. Assim obtive a seguinte sequência do tamanho das pilhas:

(6, 4, 3, 1, 1)→ (5, 5, 3, 2)→ (4, 4, 4, 2, 1)→ (5, 3, 3, 3, 1)→ (5, 4, 2, 2, 2)→

→ (5, 4, 3, 1, 1, 1)→ (6, 4, 3, 2)

Nossa! É quase como eu comecei. Quando isso irá terminar? E então, de repente, terminou:

(6, 4, 3, 2)→ (5, 4, 3, 2, 1)→ (5, 4, 3, 2, 1) de novo.

− Hmm − eu disse.

− Você terminou com uma pilha com 5 cartas, outra com 4 cartas, outra com 3 cartas,

outra com 2 cartas e por fim uma com 1 carta, não foi? − e assim o homem voltou os olhos

para as cartas.

10


− Isso é o que sempre ocorre. Tente novamente!

Eu comecei com uma única pilha com 15 cartas. Levou mais movimentos, mas chegou no

padrão 5,4,3,2,1. Então eu comecei com 3 pilhas de 5 cartas. Demorou um pouco mais, mas

novamente chegou na mesma configuração.

Três exemplos não é uma prova, mas o fato é razoável. Sempre será alcançada a mesma

configuração? Quanto tempo demora para alcançar a configuração padrão? O que acontece com

outro números de cartas?

− Isso é interessante − admiti.

Esse “quebra-cabeça” foi popularizado por Martin Gardner em 1983 [3], com um nome pe-

culiar “Paciência Búlgara”.

Antes de Gardner:

Por volta de 1980, Kostantin Oskolkov do Steklov Mathematical Institute de Moscou viajou

em um trem para dar uma palestra em Leningrad, agora São Petersburgo. Um homem no trem

lhe explicou sobre o problema, no entanto os detalhes do diálogo acima é fict́ıcio, Oskolkov

compartilhou isso com seus colegas no instituto. Dizem que quando um matémático da área

de teoria dos números soube sobre o problema, “o seu rosto assumiu uma expressão satânica,

correu para seu escritório, trancou a porta e não saiu de lá até resolver o problema”.

O “quebra-cabeça” chegou a Victor Gutenmacher, editor do jornal Kvant. O problema

apareceu por lá em 1980, no contexto de pilhas de livros. Andrei Toom, um cientista na Uni-

versidade Estadual de Moscou, publicou uma solução em 1981. O material foi também inclúıdo

em um livro de olimṕıadas de matemática em 1981 no qual os autores incluem Gutenmacher e

Toom.

No fim de 1980, Anatolii Alexeevich Karatsuba viajou de Steklov para o Instituto de

Matemática da Academia de Ciências da Bulgária em Sofia. Depois de uma palestra de teoria

de aproximação, ele compartilhou a história de Oskolkov e do quebra-cabeça. Novamente, ele

capturou a atenção de muitos matemáticos, e Milko Petkov o publicou na seção de “competição

de problemas” de um jornal de uma escola de ńıvel médio em 1980, no contexto de monte de

bolas. Nenhum estudante conseguiu resolver o problema, e então a solução de Borislav Bojanov,

colega do instituto de Petkov, foi publicada em 1981.

Gert Almkvist da Universidade Lund, estava visitando a cidade de Sofia enquanto Karatsuba

estava lá. Quando Almkvist retornou para a Suécia, ele compartilhou o quebra-cabeça com seus

colegas, incluindo Henrik Erikisson da KTH Royal Institute of Technoloy, que publicou uma

solução também em 1981, com o nome “Bulgarisk patiens”, no contexto de pilha de cartas.

11


Jørgen Brandt, terminou seu mestrado na Universidade de Aarhus, e de algum modo apren-

deu o quebra-cabeça também (sem nenhum nome). “O problema pareceu tão puro, que eu não

pensei muito de onde ele possa ter vindo”, explicou recentemente. Sua solução, no cenário de

partições de inteiros, foi submetida para Proceedings of the American Mathematical Society em

1981 e publicada em 1982.

Enquanto isso, Eriksson viajou de Estocolmo para a Califórnia, onde ele chamou o quebra-

cabeça de Bulgarian Solitaire, na tradução literal, Paciência Búlgara. Ele explicou recente-

mente, “O nome bobo foi minha invenção, bobo porque não é nem Búlgaro e nem é jogo de

paciência”. Donald Knuth começou em 1982 seminários de programação e solução problema

com a Paciência Búlgara. Ron Graham passou isso à Gardner que em 1983 popularizou com o

mesmo nome dado por Erikisson, que até hoje perdurou.

Após isso, outras variações da Paciência Búlgara foram criadas. O intuito deste trabalho é

estudar a versão original e uma variação chamada Paciência Carolina [4]. Vamos transformar

a Paciência Búlgara no cenário de Sistemas Dinâmicos, trocando cartas por números inteiros

positivos, o conjunto de pilhas por partição desses números e o movimento do jogo por uma

aplicação shift bem definida no conjunto das partições.

12


Caṕıtulo 1

Conceitos Inicias

Um sistema dinâmico é uma função f definida em um certo conjunto X, ou seja,

f : X −→ X

A dinâmica, isto é, a passagem do tempo, é visto como sendo a iteração dessa função.

Desta forma, se começamos com um ponto x ∈ X (que corresponde ao instante zero) depois ele

estará em f(x) (instante 1), depois f(f(x)) (instante 2) e assim sucessivamente. Para evitarmos

escrever expressões como

f(f(f(f(f(x))))) (1.1)

usaremos a seguinte convenção, padrão nessa área:

f 0(x) := x f 1(x) := f(x) fn(x) := f(fn−1(x)) para n ≥ 1

Desta maneira a expressão (1.1) pode ser reescrita simplesmente f 5
(x) significando que f

foi iterada 5 vezes. Não se deve confundir isso com com elevar f(x) a potência 5, até porque

essa operação algébrica pode não fazer o menor sentido no conjunto X. Nessa nova notação,

então, o que se pretende estudar é a evolução do tempo de um ponto x, ou seja, x, f(x), f 2(x),

f 3(x), . . .. Este conjunto é conhecido como a órbita do ponto x:

O(x) :=
⋃
n∈N

fn
(x)

.

Dizemos que x é um ponto periódico ou ćıclico de peŕıodo p se p é o menor inteiro tal

que f p(x) = x. Quando p = 1, ou seja, temos f(x) = x, então dizemos simplesmente que x é

um ponto fixo para f .

Quando x é periódico então sua órbita x, f(x), f 2
(x), f 3

(x), . . ., f p−1
é um conjunto finito

conhecido como órbita periódica ou ćıclica.

13


Definição 1.0.1 Seja n um inteiro positivo, dizemos que n é um número triangular se

n = 1 + 2 + . . .+ k = Tk =
(k)(k + 1)

2
para algum k ∈ Z+.

Exemplo 1.0.1 Os números 1, 3, 6, 10, 15, 21, 28 são os 7 primeiros números triangulares.

Definição 1.0.2 Seja x um número natural, a função totiente, às vezes chamada de to-

ciente, ou função fi de Euler, representada por ϕ(x), é definida como sendo igual à quanti-

dade de números naturais menores ou iguais à x coprimos com respeito à ele, ou seja,

ϕ(x) = �{n ∈ N | (n ≤ x) ∧ (mdc(n, x) = 1)}

Exemplo 1.0.2 ϕ(8) = 4, uma vez que os números 1, 3, 5 e 7 são coprimos de 8. ϕ(1) = 1,

já que mdc(1, 1) = 1.

14


Caṕıtulo 2

Paciência Búlgara

2.1 Partições e aplicação B-shift

Definição 2.1.1 (Partição) Seja n um inteiro positivo, dizemos que λ = (λ1, λ2, . . . , λs) ∈ Zs,

s = 1, . . . , n, é uma partição de n, e escrevemos λ � n, se λi > 0, ∀i = 1, . . . , s,

λ1 ≥ λ2 ≥ . . . ≥ λs e
s∑

i=1

λi = n. Nesse caso chamamos cada λi, i = 1, . . . , s de i-ésima

parte da partição. O número de partes da partição definimos como sendo o seu comprimento

(tamanho), e escrevemos |λ| = s.

Exemplo 2.1.1 λ = (1, 1, 1, 1, 1, 1) e μ = (4, 2) são partições do número 6. λ possui 6 partes

iguais, ou seja, |λ| = 6 e μ possui 2 partes distintas, |μ| = 2.

Definição 2.1.2 Seja n um inteiro positivo, definimos Λn = {λ | λ � n} o conjunto de todas

as partições de n.

Em Teoria dos Números, a cardinalidade de Λn (�Λn) é a Função Partição p(n) que

calcula a quantidade de partições posśıveis de n. Quando precisarmos calcular a quantidade de

partições de um determinado inteiro n, utilizaremos o comando “Lenght[IntegerPartitions[n]]”

do software “Wolfram Mathematica”.

Exemplo 2.1.2 Seja n = 4. No software “Wolfram Mathematica” utilizando o comando

“IntegerPartitions[4]” obtemos as partições de 4, que são: (4), (3, 1), (2, 2), (2, 1, 1), (1, 1, 1, 1).

Utilizando o comando “Lenght[IntegerPartitions[4]]” obtemos o valor 5 que é a quantidade

de partições de 4 que, em teoria dos números, é p(4), e pela definição anterior é também a

cardinalidade de Λ4 (�Λ4 = 5).

15


Definição 2.1.3 Sejam n um inteiro positivo e λ = (λ1, λ2, . . . , λs) � n. Definimos por

B-shift a aplicação, B : Λn −→ Λn, que associa λ à uma nova partição de n denotada por

B(λ), obtida da seguinte maneira:

1) diminui-se uma unidade de cada parte λi, i = 1, . . . , s.

2) Descarta(m)-se a(s) parte(s) nula(s), caso houver.

3) Insere-se uma parte de tamanho s de forma que B(λ) seja uma partição de n.

Observação 2.1.1 Se |λ| = s então, pela definição, |B(λ)| ≤ s+ 1.

Exemplo 2.1.3 Sejam λ = (2, 2, 2, 1, 1), θ = (7, 1) e γ = (2, 2, 2, 2) partições de 8.

B(λ) = (5, 1, 1, 1), B(θ) = (6, 2) e B(γ) = (4, 1, 1, 1, 1).

Geometricamente podemos ver a aplicação B-shift da seguinte maneira:

Suponha que o número inteiro dado seja uma quantidade de blocos, como ilustrado na

Figura 2.1.

Figura 2.1: 8 blocos

Uma partição desse número pode ser representada por uma pilha desses blocos dispostos de

maneira não crescente. Por exemplo a partição λ = (2, 2, 2, 1, 1) é representada como mostra a

Figura 2.2.

Figura 2.2: Uma partição de n = 8

16


A aplicação B-shift retira um bloco de cada pilha (por convenção pode-se supor que o bloco

retirado é o do topo da pilha), e com esses blocos retirados forma-se uma nova pilha que é

colocada de maneira que os blocos continuem organizados de forma não crescente, conforme a

Figura 2.3.

Figura 2.3: B-shift

Com base nos conceitos do Caṕıtulo 1, dado n um inteiro positivo vamos estudar a dinâmica

do conjunto Λn pela aplicação B-shift.

Definição 2.1.4 Dada uma partição λ de um inteiro positivo n, descrevemos a “Paciência

Búlgara” de λ como sendo a sequência:

λ,B(λ),B(2)
(λ), . . .

tal que B(i)(λ), i ∈ Z+, representa a partição de n, obtida através de sucessivas aplicações de

B-shift em λ, no total de i vezes. Nesse caso dizemos que B(i)(λ) é a i-ésima iterada de λ pela

aplicação B-shift.

Ou seja, a “Paciência Búlgara” de uma partição λ � n, pensando como um sistema dinâmico

no conjunto Λn com a aplicação B-shift, nada mais é do que a sua órbita.

Observação 2.1.2 Como o número de partições de um número inteiro é finito, então as

partições da sequência da Paciência Búlgara começam a repetir em algum momento.

Exemplo 2.1.4 Seja λ = (2, 1, 1, 1, 1) � 6, então temos B(λ) = (5, 1), B(2)(λ) = (4, 2),

B(3)(λ) = (3, 2, 1), B(4)(λ) = (3, 2, 1), . . ..

17


Figura 2.4:

Figura 2.5:

Exemplo 2.1.5 Seja μ = (6, 1) � 7, assim temos B(μ) = (5, 2), B(2)(μ) = (4, 2, 1), B(3)(μ) =

(3, 3, 1), B(4)(μ) = (3, 2, 2), B(5)(μ) = (3, 2, 1, 1), B(6)(μ) = (4, 2, 1), B(7)(μ) = (3, 3, 1), . . . .

Observe que no Exemplo 2.1.4 após 4 iteradas de B em λ chegamos em uma partição que

não se modifica através de B. Já no Exemplo 2.1.5, as partições começaram a se repetir após

6 iteradas de B em μ.

2.2 Partições ćıclicas, dB(λ) e DB(n)

Sejam n um inteiro positivo, λ � n e B : Λn −→ Λn.

Definição 2.2.1 Dizemos que λ é B-ćıclica, ou simplesmente ćıclica, de peŕıodo i, se i é o

menor inteiro positivo tal que B(i)(λ) = λ. Assim o conjunto O(λ) = {λ,B(λ),B(2)(λ), . . . ,B(i−1)(λ)}

é a sua órbita periódica, ou ciclo, e o seu peŕıodo é i. Nesse caso também podemos dizer que λ

é periódica de peŕıodo i.

Observação 2.2.1 (1) Se i = 1 dizemos que λ é uma partição fixa.

(2) Se λ é ćıclica de peŕıodo i, então O(λ) = O(B(λ)) = . . . = O(B(i−1)(λ))

No Exemplo 2.1.4, a partição (3, 2, 1) é uma partição fixa, ou seja, uma partição B-ćıclica de

peŕıodo 1, enquanto no Exemplo 2.1.5 as partições (4, 2, 1), (3, 3, 1), (3, 2, 2), (3, 2, 1, 1) também

são periódicas, todas de peŕıodo 4.

Definição 2.2.2 Definimos dB(λ) como sendo o menor inteiro i ≥ 0 tal que B(i)(λ) é B-ćıclica

e DB(n) := max{dB(λ) | λ � n}.

18


Observação 2.2.2 Nesse caso i é o menor tempo necessário (número de iteradas) para a

partição λ alcançar um ciclo. Pode-se falar também que λ levou i iteradas para alcançar um

ciclo ou uma partição B-ćıclica. DB(n) é o maior valor de dB(λ), λ � n.

Exemplo 2.2.1 Seja λ = (4, 1) � 5. Fazendo as iterações em λ obtemos:

Figura 2.6:

Assim dB(λ) = 1 pois a partição μ = B(λ) = (3, 2) é B-ćıclica, já que B(3)(μ) = μ.

Exemplo 2.2.2 DB(4) = 2, pois as partições de 4 são λ = (1, 1, 1, 1), α = (4), γ = (3, 1),

δ = (2, 2), β = (2, 1, 1) e, dB(λ) = 2, dB(α) = 1, dB(γ) = dB(δ) = dB(β) = 0.

Figura 2.7:

Os valores de DB(n), 4 ≤ n ≤ 36, são mostrados na tabela a seguir, calculados computa-

cionalmente. A representação de n é da forma n = 1 + 2 + 3 + . . .+ (k − 1) + r, 1 ≤ r ≤ k.

Um dos objetivos principais deste trabalho é encontrarmos o valor de DB(n) e para isso

precisaremos introduzir vários conceitos, para assim termos ferramentas necessárias para de-

terminá-lo. Para n triangular DB(n) é um valor exato, quando n não for triangular vamos

encontrar um limite superior e um limite inferior, que é conjecturado como sendo o valor exato.

19


Tabela 2.1: Valores de DB(n), n = 4, . . . , 36

k = 3 k = 4 k = 5 k = 6 k = 7 k = 8

r = 1 DB(4) = 2 DB(7) = 4 DB(11) = 8 DB(16) = 15 DB(22) = 24 DB(29) = 35

r = 2 DB(5) = 3 DB(8) = 5 DB(12) = 8 DB(17) = 12 DB(23) = 18 DB(30) = 28

r = 3 DB(6) = 6 DB(9) = 7 DB(13) = 9 DB(18) = 13 DB(24) = 18 DB(31) = 24

r = 4 DB(10) = 12 DB(14) = 14 DB(19) = 16 DB(25) = 19 DB(32) = 25

r = 5 DB(15) = 20 DB(20) = 23 DB(26) = 26 DB(33) = 29

r = 6 DB(21) = 30 DB(27) = 34 DB(34) = 38

r = 7 DB(28) = 42 DB(35) = 47

r = 8 DB(36) = 56

2.3 Plotando diagramas através do software “Wolfram

Mathematica”

O software “Wolfram Mathematica” será muito útil neste trabalho pois dado n um inteiro

positivo, é posśıvel plotar a “Paciência Búlgara”, ou seja, um diagrama contendo a dinâmica

de todas as suas partições através da aplicação B-shift, o qual daremos o nome de Diagrama

B-shift de n. Nesse diagrama os śımbolos “•” representam as partições de n e as flechas, re-

presentam as aplicações B-shift. As partições ćıclicas em especial, serão coloridas em vermelho.

A única diferença de notação é que no texto definimos as partições entre parênteses “( )” e nos

diagramas as partições aparecem entre chaves “{ }”

O diagrama nos ajudará a entender melhor as definições deste trabalho, assim como nos

ajudará no entendimento de demonstrações de resultados.

O código utilizado, feito por Ken Levasseur, disponibilizado em seu blog:

http://applieddiscretestructures.blogspot.com.br/2011/01/bulgarian-solitaire-follow-up.html, é

composto de 3 linhas, onde a primeira linha define a iteração que usamos, a segunda linha é

usada para para definir a plotagem do diagrama e a terceira linha é para executar o comando:

1a Linha: Bulgaria[pile List] := Sort[Select[Prepend[pile −1, Length[pile]], # > 0

&], #1 > #2 &]

2a Linha: BulgariaGraphLabeled[n ] := Graph[Map[# -> Bulgaria[#] &, Inte-

gerPartitions[n]], VertexLabels -> “Name”, PlotRange -> All, VertexSize -> Nor-

20


mal, PlotRangePadding -> 1, ImagePadding -> 1, GraphStyle -> “BasicBlack”,

GraphLayout -> “SpringElectricalEmbedding”]

3a Linha: BulgariaGraphLabeled[n]

onde n é um inteiro positivo.

Na 2
a
linha é posśıvel fazer várias alterações, como por exemplo, caso não for interessante

a rotulação da partição basta trocar VertexLabels -> “Name” por VertexLabels -> None. É

importante observar que neste software há o chamado Case sensitive que é a diferenciação de

letra maiúscula de minúscula.

Se for interessante também é posśıvel rotular a partição com o respectivo tamanho, bastando

substituir na segunda linha, VertexLabels -> “Name” por VertexLabels -> Map[# -> Length[#]

&, IntegerPartitions[n]].

Há várias opções paraGraphStyle (Cores) e GraphLayout (Estilo de disposição das partições)

que estão elencadas no próprio Help do software.

Exemplo 2.3.1 A Figura 2.8 representa a dinâmica das partições de n = 7. Pelo diagrama

conseguimos encontrar o valor de dB(λ) para qualquer λ partição de n, assim como o valor de

DB(n).

�
�
�

�
� � �
�

�
� � �
�

�
� � � � �

�

�
� � � � �

�

�
� � �
�

�
� � � � �

�

�
� � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � �

��
� � � � � � � � �

� �
� � � � � � � � � � �

�

�
� � � � � � � � � � � � �

�

Figura 2.8: Diagrama B-shift de n = 7, estilo LayeredDrawing

21


A Figura 2.9 também representa a dinâmica das partições de n = 7, a diferença é apenas o

GraphLayout.

�
�
�

� � � � �

� � � � �
�

�
� � � � �

� � � � � � �

�
� � � � � � � � � � �

� � � � � � �

�
� � � � � � � �

� � � � � � � � �

� � � � � � � � � � �

�� � � � � � � �

�� � � � � � � � � �

�� � � � � � � � � � � �

� � � � � � � � � � � � � � �

Figura 2.9: Diagrama B-shift de n=7, estilo SpringElectricalEmbedding

22


2.4 Caracterização das Partições Ćıclicas

Nesta seção introduziremos alguns elementos e conceitos para encontrar uma caracterização

para partições ćıclicas.

A prinćıpio vamos definir uma matriz formada apenas por entradas com valores 0 ou 1 que

represente uma dada partição, afim de conseguirmos encontrar um padrão de comportamento

desses 0’s e 1’s ao longo das iteradas da aplicação B em λ. Veremos que podemos obter B(λ),

B(2)(λ), . . . a partir de um certo processo de shift nas entradas da matriz.

Definição 2.4.1 Dada uma partição λ = (λ1, λ2, . . . , λs) � n definimos por Mλ a sua matriz

associada, de forma que:

Mλ = [mij ]
∞
i,j=1, onde mij =

⎧⎨
⎩

1, se j ≤ s e i ≤ λj ;

0, c.c.

Exemplo 2.4.1 Seja λ = (5, 3, 2, 1, 1) � 12, então:

Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 1 1 0 · · ·

1 1 1 0 0 0 · · ·

1 1 0 0 0 0 · · ·

1 0 0 0 0 0 · · ·

1 0 0 0 0 0 · · ·

0 0 0 0 0 0 · · ·
...

...
...

...
...

...
. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

ou seja, o número de 1’s de cada coluna corresponde à respectiva parte da partição.

Vamos mostrar que MB(λ) pode ser obtida a partir de Mλ através de um processo de

“shifting” ou “deslocamento” dos 0’s e 1’s da matriz. Com isso obtemos as partições B(λ),

B2(λ), B3(λ), . . . a partir da matriz.

Definição 2.4.2 Dada uma matriz M = [mij ] definimos, para cada w ∈ Z+, como a w-ésima

diagonal, ou diagonal w de M , como sendo a w-upla formada pelas entradas mij tal que

i+ j − 1 = w, ou seja, a diagonal w é dada por:

DM(w) = (mw,1, mw−1,2, mw−2,3, . . . , mw−i,i+1, . . . , m2,w−1, m1,w︸ ︷︷ ︸
w elementos

)

23


Figura 2.10: Diagonais de Mλ

Exemplo 2.4.2 Sejam λ uma partição e Mλ = [mij ] a sua matriz associada. Assim, a 1a

diagonal consiste apenas da entrada m11, a 2a diagonal é formada pelas entradas m12 e m21,

já a 3a diagonal é formada pelas entradas m31, m22 e m13. Logo, DMλ
(1) = (m11), DMλ

(2) =

(m12, m21) e DMλ
(3) = (m31, m22, m13), conforme ilustra a Figura 2.10.

Definição 2.4.3 (Processo B-shifting) Sejam λ = (λ1, λ2, . . . , λs) � n e Mλ = [mij ] a sua

matriz associada. O processo de obtenção de MB(λ) a partir de Mλ, chamado de

Processo B-shifting é composto de no máximo 2 passos:

Passo 1: Shifting Circular Diagonal: Nesse passo vamos criar uma matriz M ′
λ = [m′

ij ]

tal que m′
i,j = mi+1,j−1 se j ≥ 2 e m′

i,j = mj,i se j = 1, ou seja, para cada diagonal de Mλ, por

exemplo, DMλ
(w) = (v1, v2, . . . , vw), reordenamos as suas entradas e escrevemos

DM ′

λ
(w) = (vw, v1, v2, . . . , vw−1). Note que o número de 1’s nas colunas de M ′

λ são s, λ1 − 1,

λ2 − 1, . . . , λs − 1, 0, 0, 0, . . ..

Se s ≥ λ1 − 1, ou seja, se houver mais 1’s na primeira coluna do que na segunda coluna,

então M ′
λ = MB(λ). Se s < λ1 − 1 então precisamos de um passo a mais para obter MB(λ).

Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

· · · · · · · · · · · · · · · · · · vw · · ·

· · · · · · · · · · · · · · · vw−1 · · · · · ·

· · · · · · · · · · · · . .
.
· · · · · · · · ·

...
...

... . .
. ...

...
... · · ·

...
... v3 · · · · · · · · · · · · · · ·

... v2 · · · · · · · · · · · · · · · · · ·

v1 · · · · · · · · · · · · · · · · · · · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

24


Figura 2.11: Representação do Passo 1

M ′
λ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

· · · · · · · · · · · · · · · · · · vw−1 · · ·

· · · · · · · · · · · · · · · vw−2 · · · · · ·

· · · · · · · · · · · · . .
.
· · · · · · · · ·

...
...

... . .
. ...

...
... · · ·

...
... v2 · · · · · · · · · · · · · · ·

... v1 · · · · · · · · · · · · · · · · · ·

vw · · · · · · · · · · · · · · · · · · · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo 2: Shifting pela esquerda: Removemos todos as entradas nulas da primeira coluna

da matriz M ′
λ e deslocamos cada entrada da posição (i, j) tal que i ≥ s + 1 e j ≥ 2 para a

posição (i, j − 1) . A nova matriz é a matriz MB(λ).

M ′
λ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

m′
11 m′

12 m′
13 m′

14 · · ·

m′
21 m′

22 m′
23 m′

24 · · ·

0 m′
32 m′

33 m′
34 · · ·

0 m′
42 m′

43 m′
44 · · ·

...
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo2
−→ MB(λ) =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

m′
11 m′

12 m′
13 m′

14 · · ·

m′
21 m′

22 m′
23 m′

24 · · ·

m′
32 m′

33 m′
34 m′

35 · · ·

m′
42 m′

43 m′
44 m′

45 · · ·
...

...
...

...
. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Observação 2.4.1 Note que o Passo 1 do processo faz com as colunas de Mλ o equivalente

com o que a definição da aplicação B-shift faz com as partes da partição, a menos de ordem.

25


Por isso as vezes é necessário o Passo 2, para poder manter a ordem não crescente das partes

da partição (respectivamente colunas da matriz).

Observação 2.4.2 Com a definição do processo B-shifting, a partir de Mλ obtemos MB(k)(λ),

∀k ∈ Z+ e portanto, obtemos a partição B(k)(λ). Ou seja, sempre que conveniente, ao invés de

trabalharmos com a aplicação B-shift em λ, iremos trabalhar com o processo B-shifting em

Mλ.

Exemplo 2.4.3 Seja λ = (2, 2, 1, 1). Pela definição da aplicação B-shift sabe-se que

B(λ) = (4, 1, 1). Aplicando o processo B-shifting em Mλ obtemos:

Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 1 · · ·

1 1 0 0 · · ·

0 0 0 0 · · ·

0 0 0 0 · · ·
...

...
...

...
. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo1
−→ M ′

λ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 0 · · ·

1 0 0 0 · · ·

1 0 0 0 · · ·

1 0 0 0 · · ·
...

...
...

...
. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Como há mais 1’s na primeira coluna de M ′
λ do que na segunda então M ′

λ = MB(λ).

Exemplo 2.4.4 Seja λ = (4, 2), então aplicando o processo B-shifting:

Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 0 · · ·

1 1 0 · · ·

1 0 0 · · ·

1 0 0 · · ·
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo1
−→ M ′

λ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 · · ·

1 1 0 · · ·

0 1 0 · · ·

0 0 0 · · ·
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo2
−→ MB(λ) =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 · · ·

1 1 0 · · ·

1 0 0 · · ·

0 0 0 · · ·
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Agora temos as ferramentas necessárias para encontrar a caracteŕıstica de uma partição

B-ćıclica.

Teorema 2.4.1 Seja n = 1 + 2 + 3 + . . .+ (k − 1) + r, 1 ≤ r ≤ k, k ∈ Z+.

λ � n é B-ćıclica se, e somente se, λ tem a forma, chamada de forma ćıclica:

(k − 1 + δk−1, k − 2 + δk−2, . . . , 2 + δ2, 1 + δ1, δ0)

tal que δi ∈ {0, 1}, para todo i = 0, . . . , k − 1, e

k−1∑
i=0

δi = r.

26


Demonstração:

(⇐) Suponha que λ = (k − 1 + δk−1, k − 2 + δk−2, . . . , 2 + δ2, 1 + δ1, δ0), tal que δi ∈ {0, 1},

para todo i = 0, . . . , k− 1, e

k−1∑
i=0

δi = r. A matriz associada de λ, Mλ, é formada apenas de 1’s

nas (k − 1) primeiras diagonais, a diagonal k é formada por (δk−1, δk−2, . . . , δ2, δ1, δ0), ou seja,

DMλ
(k) = (δk−1, δk−2, . . . , δ2, δ1, δ0), e as diagonais abaixo da diagonal k são formadas apenas

de 0’s.

Desta forma a cada aplicação do processo B-shifting em Mλ, apenas a diagonal k é alterada.

Como DMλ
(k) possui k elementos, depois de utilizados k vezes o processo B-shifting, a matriz

MB(k)(λ) = Mλ. Logo, B
(k)(λ) = λ e, portanto, λ é B-ćıclica.

1alinha
−→

2alinha
−→

k−2alinha
−→

k−1alinha
−→

kalinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 δ0 0 · · ·

1 1 · · · 1 δ1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 δk−3 0 0 0 0 · · ·

1 δk−2 0 0 0 0 0 · · ·

δk−1 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mλ

(⇒)No processo B-shifting, notamos que o Passo 1 mantém todas as entradas da matriz na

mesma diagonal, enquanto que o Passo 2 sempre traz a entrada 1 da posição (s + 1, 2) para

uma diagonal de ı́ndice menor. Assim, para qualquer partição μ que é B-ćıclica o processo de

obtenção de MB(μ) através de Mμ pelo processo B-shifting, deve envolver apenas o Passo 1.

Sejam λ uma partição B-ćıclica e Mλ a sua matriz associada. Suponha que λ não possua a

forma ćıclica. Então para algum w ∈ Z+, há um 0 na w-ésima diagonal e um 1 na (w+1)-ésima

diagonal da matriz Mλ. Como a série de processos B-shifting de Mλ para MB(λ) para MB(2)(λ),

e assim por diante, apenas envolve o Passo 1 (Shifting Circular Diagonal) então iremos chegar

em uma matriz Mμ em que a entrada (1, w) é 0 e a entrada (w + 1, 1) é 1. Assim o processo

B-shifting de Mμ para MB(μ) envolve o Passo 2, o que é uma contradição.

27


walinha
−→

w+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 1 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mλ

walinha
−→

w+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 0 0 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mμ

Corolário 2.4.1 Seja n = Tk = 1+2+3+ . . .+ k, k ∈ Z+, então (k, k− 1, . . . , 2, 1) é a única

partição de n que é B-ćıclica.

Demonstração: Seja λ � n uma partição B-ćıclica, assim pelo Teorema 2.4.1

λ = (k − 1 + δk−1, k − 2 + δk−2, . . . , 2 + δ2, 1 + δ1, δ0), onde cada δi é 0 ou 1, i = 0, . . . , k − 1, e
k−1∑
i=0

δi = k. Logo δi = 1 ∀i, i = 1, . . . , k − 1, e portanto, λ é escrita de maneira única.

Exemplo 2.4.5 Seja n = 1+2+3 = 6. Assim pelo Corolário 2.4.1, (3, 2, 1) é a única partição

B-ćıclica, como ilustra a Figura 2.12.

Exemplo 2.4.6 Já para n = 1 + 2 + 3 + 4 = 10, pelo Corolário 2.4.1, (4, 3, 2, 1) é a única

partição B-ćıclica, como mostra a Figura 2.13.

28


�
�
�

�
� � �
�

�
� � �
�

�
� � � � �

�

�
� � � � �

�

�
� � �
�

�
� � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � � � �

�

Figura 2.12: Diagrama B-shift de n=6, estilo LayerredDrawing

Observação 2.4.3 Dado n = 1 + 2 + . . . + (k − 1) + r = Tk−1 + r, 1 ≤ r ≤ k, com a forma

de uma partição λ � n, B-ćıclica já caracterizada, teremos também uma caracterização de sua

matriz associada Mλ, que é de que as suas diagonais de 1 a (k − 1) são sempre formadas

apenas de 1’s e as diagonais abaixo da diagonal k são todas nulas, ou seja, quando aplicarmos

sucessivamente o processo B-shifting em Mλ apenas a diagonal k se modifica e assim sempre

será utilizado apenas o Passo 1 do processo (Shifting Circular Diagonal).

29


�
� �
�

�
� � �
�

�
� � �
�

�
� � � � �

��
� � � � �

�

�
� � �
�

�
	 � � � �

�

�
	 � � � �

�

�
� � � � � � �

�

�
	 � 

�

�
� � � � �

�

�
� � � � � � �

�

�
	 � � � � � �

�

�
� � 
 � �

�

�
	 � � � � � � � �

�

�
� � �
�

�

 � 
 � �

�

�

 � � � �

�

�

 � � � � � �

�

�
� � � � � � �

�

�

 � 
 � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�

 � � � � � � � �

�

�

 � � � � � �

�

�

 � � � � � � � �

�

�

 � � � � � � � � � �

��

 � � � � � � � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � � � �

�

�
� � � � � � � � �

��
� � � � � � � � � � �

�

�
� � � � � � � � � � � � �

�

�
� � � � � � � � � � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � � � �

�

�
� � � � � � � � � � � � �

��
� � � � � � � � � � � � � � �

�

�
� � � � � � � � � � � � � � � � �

�

�
� � � � � � � � � � � � � � � � � � �

�

Figura 2.13: Diagrama B-shift de n=10, estilo LayerredDrawing

2.5 Quantidade de Ciclos

Dado n = 1+ 2 + 3 + . . .+ (k − 1) + r, 1 ≤ r ≤ k, k ∈ Z+, podemos ver pelo Teorema 2.4.1

que se r = k, k − 1 ou 1, começando por qualquer partição de n, após repetidas aplicações de

B-shift sempre chegamos em um único ciclo de partições de n. Se 2 ≤ r ≤ k − 2 dependendo

da partição de n podemos chegar em diferentes ciclos.

Exemplo 2.5.1 Para n = 1+ 2+ 2 = 5, qualquer que seja a partição de 5 sempre chegaremos

em um único ciclo conforme mostra a Figura 2.14. Note que esse ciclo tem peŕıodo 3.

Exemplo 2.5.2 Para n = 1 + 2 + 3 + 2 = 8 podemos chegar nos ciclos conforme a Figura

2.15. Note que o ciclo da esquerda, na Figura 2.15, tem peŕıodo 4 e que o ciclo da direita tem

peŕıodo 2.

30


� � �

� � � � �

� � � � �

� � � � � � �

� � � � � � �

� � � � � � � � �

� � � � � � � � � � �

Figura 2.14: Diagrama B-shift de n=5, estilo SpringElectricalEmbedding

� � �

� � � � �

� 	 � � �

� � � � � � � � 	 � � � � �

� � � � �

� � � � � � �

� � � � � � �

� � � � � � � � �

� � � � �

� � � � � � �

� � � � � � � � �

� � � � � � � � � � � � � � � � � � � �

� � � � � � � � �� � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � �

� � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � �

Figura 2.15: Diagrama B-shift de n=8, estilo LayeredDrawing

Assim para a contagem de ciclos na “Paciência Búlgara”, ou seja, o número de órbitas,

temos o seguinte Teorema, demonstrado em [2] e [1].

Teorema 2.5.1 Seja n = 1 + 2 + 3 + . . . + (k − 1) + r, 1 ≤ r ≤ k, k ∈ Z+, então o número

31


de ciclos para a Paciência Búlgara é CB(n) =
1

k

∑
d|mdc(k,r)

ϕ(d)

⎛
⎝ k/d

r/d

⎞
⎠, onde ϕ(d) é a função

totiente de Euler.

Exemplo 2.5.3 Seja n = 18. Pela notação do Teorema 2.5.1 escrevemos

n = 1 + 2 + 3 + 4 + 5 + 3 = 18 e assim temos k = 6 e r = 3. Logo o número de ciclos para a

Paciência Búlgara quando n = 18 é:

CB(18) =
1

6

∑
d|mdc(6,3)

ϕ(d)

⎛
⎝ 6/d

3/d

⎞
⎠ =

1

6

∑
d|3

ϕ(d)

⎛
⎝ 6/d

3/d

⎞
⎠ =

=
1

6
ϕ(1)

⎛
⎝ 6

3

⎞
⎠+

1

6
ϕ(3)

⎛
⎝ 2

1

⎞
⎠ =

1

6
· 1 ·

6!

3! · 3!
+

1

6
· 2 ·

2!

1! · 1!
=

20

6
+

4

6
=

24

6
= 4

A Figura 2.16 mostra o Diagrama B-shift de n=18 sem os rótulos das partições e também

sem as flechas. Nessa figura podemos observar a quantidade de ciclos que calculamos.

Figura 2.16: Diagrama B-shift de n=18, estilo RadialDrawing

Quanto maior o natural n mais interessante fica o seu Diagrama B-shift.

32


Exemplo 2.5.4 A Figura 2.17 mostra o Diagrama B-shift de n=32 com o estilo SpringElec-

tricalEmbedding, sem os rótulos das partições e sem as flechas. Por questão de zoom fica dif́ıcil

de ver os peŕıodos de cada ciclo porém a figura mostra claramente a quantidade de ciclos, que

coincide com a quantidade de “ redes” de partições distintas.

Figura 2.17: Diagrama B-shift de n=32, estilo SpringElectricalEmbedding

33


2.6 Partição raiz, gerada, pré-ćıclica e caracterizações

Observação 2.6.1 B-shift não é uma aplicação injetora pois dados λ = (4, 3, 1, 1, 1) e

θ = (6, 3, 1) partições de 10, temos B(λ) = B(θ) = (5, 3, 2). B-shift também não é sobrejetora

pois se λ = (1, 1, 1, 1, 1) � 5, não existe θ � 5, tal que B(θ) = λ.

Com a Observação 2.6.1 foi motivada a seguinte proposição:

Proposição 2.6.1 Sejam n um inteiro positivo e λ = (λ1, λ2, . . . , λs) � n:

(i) Se λi < s− 1, ∀i = 1, . . . , s, então não existe μ � n tal que B(μ) = λ. Nesse caso dizemos

que λ é uma partição raiz.

(ii) Se para algum i, i = 1, . . . , s, λi ≥ s− 1, então existe θ � n tal que B(θ) = λ. Nesse caso

dizemos que λ é uma partição gerada por θ, e nesse caso θ é a geratriz de λ.

Demonstração: (i) Suponha que existe μ = (μ1, μ2, . . . , μk) � n tal que B(μ) = λ, logo

μ possui pelo menos s − 1 partes (ver Observação 2.1.1) e assim para algum i, i = 1, . . . , s,

λi ≥ s− 1, o que é um absurdo.

(ii) Segue direto da definição da aplicação B-shift.

Observação 2.6.2 Em [7] a partição raiz é chamada de partição “Garden of Eden” na tradução

literal “Jardim do Éden”, que provém da terminologia de autômatos celulares e teoria combi-

natória de jogos. Também em [7] foi provado a quantidade dessas partições, dado um inteiro

positivo.

Exemplo 2.6.1 λ = (3, 2, 2, 1, 1, 1) é uma partição raiz.

Exemplo 2.6.2 α = (4, 2, 1) � 7 é uma partição gerada por μ = (3, 2, 1, 1) � 7 e θ = (5, 2) � 7

pois B(μ) = B(θ) = (4, 2, 1), ou seja, as geratrizes de uma partição não são únicas e isso ocorre

pelo fato da aplicação B-shift não ser injetora.

Figura 2.18:

34


Definição 2.6.1 Dizemos que λ é uma partição pré-ćıclica se λ não é ćıclica e B(λ) é

ćıclica, ou seja, λ é uma geratriz não ćıclica de uma partição ćıclica.

Exemplo 2.6.3 Seja n = 18 e λ = (7, 6, 3, 2). Então λ é uma partição pré-ćıclica pois λ não

é ćıclica já que não tem a forma ćıclica do Teorema 2.4.1 e B(λ) = (6, 5, 4, 2, 1) que é ćıclica.

Lema 2.6.1 Seja λ = (λ1, λ2, . . . , λs) � n uma partição gerada. Se λ possui l partes distintas

maiores ou iguais a (s− 1), então λ possui l geratrizes distintas.

Demonstração: Seja λi para algum i = 1, . . . , s uma parte de λ tal que λi ≥ s − 1. Pela

definição de B-shift, existe μ � n, |μ| = λi, μ �= λ, tal que B(μ) = λ, a saber:

μ = (λ1 + 1, λ2 + 1, . . . , λi−1 + 1, λi+1 + 1, . . . , λs + 1,

λi−(s−1)︷ ︸︸ ︷
1, 1, . . . , 1︸ ︷︷ ︸

λi

)

Portanto, como λ possui l partes distintas maiores ou iguais a (s − 1), então conseguimos

determinar l geratrizes distintas para λ.

Questão: Qual a caracterização das partições pré-ćıclicas?

Seja n um inteiro positivo, n = Tk−1 + r, 1 ≤ r ≤ k.

Se λ � n é uma partição B-ćıclica, então λ tem a forma ćıclica dada no Teorema 2.4.1:

(k − 1 + δk−1, k − 2 + δk−2, k − 3 + δk−3, . . . , 3 + δ3, 2 + δ2, 1 + δ1, δ0)

tal que δi = 1 ou 0 e

k−1∑
i=0

δi = r.

Se n é triangular, ou seja, r = k, então pelo Coroláro 2.4.1:

λ = (k, k − 1, k − 2, . . . , 3, 2, 1)

e assim λ possui k partes, ou seja |λ| = k. Logo possui 2 partes, λ1 = k e λ2 = k − 1 tal que

λ1, λ2 ≥ k − 1 e assim, pelo Lema 2.6.1, λ possui 2 geratrizes distintas, κ1
e κ2

.

- Seja κ1 a geratriz com k partes, logo, pela definição de B-shift, κ1 = λ que é ćıclica.

- Seja κ2 a geratriz com k − 1 partes, logo, pela definição de B-shift:

κ2
= (k + 1, k − 1, k − 2, . . . , 4, 3, 2︸ ︷︷ ︸

k−1

) (2.1)

que não é ćıclica.

Portanto, para n triangular, as partição pré-ćıclicas são da forma dada em (2.1).

Se n é não triangular, ou seja, 1 ≤ r < k então:

35


• Se δ0 = 1 então λ possui k partes, ou seja, |λ| = k. Logo possui 2 partes, a saber,

λ1 = k− 1 + δk−1 e λ2 = k − 2 + δk−2, com δk−2 = 1, tal que λ1, λ2 ≥ k− 1 e assim, pelo Lema

2.6.1, λ possui 2 geratrizes μ1 e μ2 com μ1 �= μ2.

- Seja μ1 a geratriz com (k − 1) + δk−1 partes, logo, pela definição de B-shift:

μ1
= (k − 1 + δk−2, k − 2 + δk−3, . . . , 3 + δ2, 2 + δ1, 1 + δ0, δk−1︸ ︷︷ ︸

(k−1)+δk−1

)

que é ćıclica.

- Seja μ2 a geratriz com (k − 2) + δk−2 partes, δk−2 = 1, logo, pela definição de B-shift:

μ2
= (k + δk−1, k − 2 + δk−3, k − 3 + δk−4, . . . , 3 + δ2, 2 + δ1, δk−2 + δ0︸ ︷︷ ︸

(k−2)+δk−2

)

Se δk−1 = 0 então μ2 é ćıclica.

Se δk−1 = 1 então μ2 não é ćıclica.

• Se δ0 = 0 então λ possui (k− 1) partes, ou seja, |λ| = k− 1, logo possui 3 partes, a saber

λ1 = k−1+ δk−1, λ2 = k−2+ δk−2 e λ3 = k−3+ δk−3, com δk−3 = 1, tal que λ1, λ2, λ3 ≥ k−1

e assim, pelo Lema 2.6.1, λ possui 3 geratrizes distintas θ1, θ2 e θ3.

- Seja θ1 a geratriz com (k − 1) + δk−1 partes, então θ1 = μ1.

- Seja θ2 a geratriz com (k − 2) + δk−2 partes, então θ2 = μ2.

Se δk−2 = 1 então:

se δk−1 = 0, então θ2 é ćıclica.

se δk−1 = 1, então θ2 não é ćıclica.

Se δk−2 = 0 então θ2 não é ćıclica.

- Seja δ3 a geratriz com (k − 3) + δk−3 partes, δk−3 = 1, logo, pela definição de B-shift:

θ3 = (k + δk−1, k − 1 + δk−2, k − 3 + δk−4, . . . , 3 + δ2, 2 + δ1︸ ︷︷ ︸
(k−3)+δk−3

)

que não é ćıclica.

Portanto, se n é não triangular, então as partições pré-ćıclicas são da forma:

ζ = (k + δk−1, k − 2 + δk−3, k − 3 + δk−4, . . . , 3 + δ2, 2 + δ1, δk−2 + δ0) (2.2)

com δ0 ≤ δk−2 e (δk−1, δk−2) �= (0, 1)

ou

ϑ = (k + δk−1, k − 1 + δk−2, k − 3 + δk−4, . . . , 3 + δ2, 2 + δ1) (2.3)

36


com δ0 = 0 e δk−3 = 1.

No caso em que δk−2 = δ0 = 0 e δk−3 = 1 temos ζ = ϑ.

Exemplo 2.6.4 Seja n = T4 + 2 = 12. As partições ćıclicas de 12 são da forma:

(4 + δ4, 3 + δ3, 2 + δ2, 1 + δ1, δ0)

tal que δi = 1 ou 0, para i = 0, . . . , 4, e

4∑
i=0

δi = 2.

Logo as partições pré-ćıclicas são da forma:

(5 + δ4, 3 + δ2, 2 + δ1, δ3 + δ0) com δ0 ≤ δ3 e (δ4, δ3) �= (0, 1)

ou

(5 + δ4, 4 + δ3, 2 + δ1) com δ0 = 0 e δ2 = 1.

E as possibilidades são: (6, 4, 2), (6, 3, 3), (5, 4, 3), (6, 3, 2, 1) e (5, 5, 2), como mostra a

Figura 2.19.

�
� � � � �

�

�
� � � � �

�

�
� � � � � � �

�

�
� � � � �

�

�
� � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � �

�

�
� � � � � � � � �

�

Figura 2.19:

37


2.7 Cálculo de DB(n) para números triangulares

Na Seção 2.2 definimos DB(n) e nesta seção vamos encontrar o valor de DB(n) para números

triangulares.

Teorema 2.7.1 Se n = Tk = 1 + 2 + . . .+ k, k ∈ Z+, então DB(n) ≥ k2 − k.

Demonstração: É suficiente mostrar que existe λ � n tal que dB(λ) = k2 − k já que

DB(n) := max{dB(λ) | λ � n}. Seja λ = (λ1, λ2, . . . , λk+1), tal que λ1 = k − 1, λi = k − i + 1

para i = 1, . . . , k, e λk+1 = 1. Assim λ = (k − 1, k − 1, k − 2, k − 3, . . . , 3, 2, 1, 1). Fazendo

a matriz associada Mλ temos que as diagonais de 1 a (k − 1) são formada apenas por 1’s, a

diagonal k é da forma (0, 1, 1, . . . , 1, 1), a diagonal k + 1 é da forma (0, 0, 0, . . . , 0, 0, 1) e as

diagonais abaixo da diagonal k + 1 são formadas apenas de 0’s.

k−1alinha
−→

kalinha
−→

k+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 1 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mλ

Com a forma da matriz Mλ definida, ao aplicar k vezes o processo B-shifting em Mλ, apenas

DMλ
(k + 1) é alterada, pois as outras diagonais são formadas apenas por 1’s ou são formadas

apenas por 0’s e a diagonal k permanece a mesma também pois possui k elementos. Note

que nessas k vezes foi preciso apenas utilizar o Passo 1 (Shifting Circuarl Diagonal) por causa

da configuração de Mλ. Assim as diagonais DMλ
(k) e DMλ

(k + 1) se comportam da seguinte

maneira:

38


� Processo B-shifting em Mλ (Passo 1) DMλ
(k) DMλ

(k + 1)

k (0, 1, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 0, 0, . . . , 0, 0, 1, 0︸ ︷︷ ︸
k+1

)

2k (0, 1, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 0, 0, . . . , 0, 1, 0, 0︸ ︷︷ ︸
k+1

)

...
...

...

(k − 2)k (0, 1, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 0, 1, 0, . . . , 0, 0, 0︸ ︷︷ ︸
k+1

)

(k − 1)k (0, 1, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 1, 0, 0, . . . , 0, 0, 0︸ ︷︷ ︸
k+1

)

Assim depois de aplicados (k−1)k vezes o Passo 1 do processo B-shifting em Mλ, chegamos

em uma matriz Mθ com a seguinte configuração:

k−1alinha
−→

kalinha
−→

k+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 0 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

0 1 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mθ

Há mais 1’s na segunda coluna do que na primeira, logo precisamos aplicar o Passo 2 do

processo B-shifting em Mθ e assim obtemos a matriz MB((k−1)k)(λ) que é a matriz associada da

partição B((k−1)k)(λ). Logo B((k−1)k)(λ) = (k, k − 1, k − 2, . . . , 3, 2, 1) que é ćıclica e portanto

dB(λ) = k2 − k.

k−1alinha
−→

kalinha
−→

k+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 0 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= MB((k−1)k)(λ)

Antes de provarmos o próximo teorema vamos precisar de algumas ferramentas, notações e

lemas.

39


Vamos começar com um exemplo para para um natural n = 15. O número 15 possui 176

partições. Como 15 é um número triangular escrito na forma n = 1 + 2 + 3 + 4 + 5 = T5, pelo

Corolário 2.4.1, sabemos que a partir de qualquer partição de 15, sempre alcançamos a partição

(5, 4, 3, 2, 1) em um certo número de iteradas.

As 176 partições do número 15 podem ser agrupadas em uma árvore, ilustrada na Figura

2.20, cujo os vértices correspondem ao número de partes da respectiva partição e a ligação de

cada vértice, lendo de cima para baixo, representa a aplicação B-shift.

Figura 2.20: Representação dos tamanhos das 176 partições do número 15

Por exemplo, o número 5 na base da árvore representa a partição (5, 4, 3, 2, 1) que possui 5

partes. O número 4 que vem logo acima desse 5 representa a partição (6, 4, 3, 2) que possui 4

40


partes.

Definição 2.7.1 Seja λ � n, associamos a λ a sequência seqB(λ) =< c1, c2, . . . >, tal que

ci = |B
(i−1)(λ)|, i ∈ Z+, ou seja, ci é o tamanho da partição B(i−1)(λ).

Exemplo 2.7.1 Na Figura 2.20, o vértice no topo e mais à esquerda, corresponde à partição

λ = (4, 4, 3, 2, 1, 1) � 15. Logo ela possui a sequência associada:

seqB(λ) =< 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, 5, 5, 6, 4, 5, 5, 5, 5, . . . >.

Dado n um inteiro positivo, podemos também plotar através do software “Wolfram Math-

ematica” um diagrama semelhante ao Diagrama B-shift de n, de tal forma que os vértices

agora são rotulados com o tamanho das respectivas partições. Chamaremos esse diagrama de

Árvore B-shift de n.

Exemplo 2.7.2 A Figura 2.21 representa a Árvore B-shift de 10. Comparando com a Figura

(2.13) é posśıvel ver a associação entre a partição e o respectivo tamanho.

�

�

�

��

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

��

�

�

��

�

�

�

�

��

	
� 


Figura 2.21: Árvore B-shift de 10

Na Figura 2.20, observamos que o padrão “x− 1, x, x, . . . , x, x, x+ 1” aparece com grande

frequência nas sequências associadas. Esse padrão é fundamental para o cálculo preciso de

DB(n). Para estudarmos esse padrão, associamos um diagrama para cada partição.

41


Definição 2.7.2 Dada uma partição λ = (λ1, λ2, . . . , λs) � n, seja seqB(λ) =< c1, c2, . . . > a

sua sequência associada. O diagramaB(λ) é definido como o diagrama mostrado na Tabela 2.2,

tal que cada coluna rotulada por λi (respc., ci ) possui λi (respec., ci) 1’s a partir do topo e

em sequência, e infinitos 0’s em todas as outras entradas. Os śımbolos � no diagramaB(λ)

são ignorados.

Tabela 2.2: diagramaB(λ)

� � � � λ1 λ2 · · · λs

� � � c1 · · ·

� � c2 · · ·

� c3 · · ·

. .
.

· · ·
... · · ·
...

...
...

...
...

... · · ·
...

Exemplo 2.7.3 Se λ = (4, 2, 2, 2) então o diagramaB(λ) é:

� � � � � � � � 4 2 2 2

� � � � � � � 4 1 1 1 1

� � � � � � 5 1 1 1 1 1

� � � � � 3 1 1 1 0 0 0

� � � � 4 1 1 1 1 0 0 0

� � � 4 1 1 1 1 0 0 0 0

� � 4 1 1 1 1 0 0 0 0 0

� 4 1 1 1 0 1 0 0 0 0 0

4 1 1 1 1 0 0 0 0 0 0 0

1 1 1 1 0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0

...
...

...
...

...
...

...
...

...
...

...
...

42


Observação 2.7.1 1) Pela definição do diagramaB(λ) há ci 1’s na coluna de ci , i ∈ Z+.

Temos também o mesmo número de 1’s na linha de ci , isso pelo fato da própria definição de

seqB(λ) e diagramaB(λ). O que difere os 1’s das colunas e das linhas de ci é que nas colunas

os 1’s são consecutivos e na linhas os 1’s não necessariamente são.

2) Além disso o diagramaB(λ) pode ser considerado como um “lembrete” para a operação

B-shift em λ, já que podemos obter facilmente B(i)
(λ) a partir do diagramaB(λ) para qualquer

natural i. Às vezes precisaremos reorganizar as colunas. Por exemplo, o retângulo formado

abaixo de c2 = 5 e à direta de c3 = 3 nos mostra, ignorando os zeros, B(2)(λ) = (5, 3, 2) e o

retângulo abaixo de c7 = 4 e à direta de c8 = 4 resulta, ignorando os zeros, em B(7)(λ) =

(4, 3, 2, 1).

Proposição 2.7.1 Sejam λ � n e seqB(λ) =< c1, c2, . . . >. Então:

(1) ci+1 ≤ ci + 1 para i ≥ 1.

(2) Para n = 1+ 2+ . . .+ (k− 1) + r, onde 1 ≤ r ≤ k, k ∈ Z+, a soma de quaisquer k termos

consecutivos da seqB(λ) é no máximo k(k − 1) + r.

(3) (Propriedade do Sandúıche) Sejam i, j, x ∈ N∗. Se i < j e ci < x < cj, então existem

inteiros p e q tal que i ≤ p < q ≤ j, q ≥ p+ 2, e (cp, cp+1, . . . , cq) = (x− 1, x, x, . . . , x, x+ 1).

Demonstração: (1) Seja λ � n uma partição cujo número de partes é ci. Logo, pela definição

de seqB(λ), ci+1 é o número de partes da partição B(λ) e, pela definição da aplicação B-shift,

apenas um dos seguintes casos pode acontecer:

i) ci+1 = ci, se uma das partes de λ for igual a 1 e as outras partes maiores que 1.

ii) ci+1 < ci, se duas ou mais partes de λ forem iguais a 1.

iii) ci+1 = ci + 1, se nenhuma das partes de λ for igual a 1.

Portanto, ci+1 ≤ ci + 1.

(2) Observe no diagramaB(λ) que para i > 0, ci+1 + ci+2 + . . . + ci+k é o número de 1’s nas

k linhas rotuladas por ci+1 + ci+2 + . . . + ci+k. O retângulo formado abaixo de ci e à direita

de ci+1 nos mostra, ignorando os zeros, a partição B(i)(λ), ou seja, há n 1’s nesse retângulo.

Olhando verticalmente ao lado esquerdo desse retângulo, como estamos somando k termos

consecutivos, temos (k − 1) + (k − 2) + . . . + 2 + 1 casas para serem completadas por 0 ou

1. Essa soma terá valor máximo quando todas as casas forem completadas por 1. Assim

ci+1 + ci+2 + . . .+ ci+k ≤ n + 1 + 2 + . . .+ (k − 1) = (k − 1)k + r.

(3) Escolha p o maior inteiro posśıvel tal que i ≤ p < j e cp = x− 1. Como escolhemos o maior

p tal que vale essa condição então cp+1 = x, pois se cp+1 ≥ x+ 1 chegaŕıamos em um absurdo

43


por (1), e se cp+1 ≤ x − 1, então não teŕıamos escolhido o maior p. Temos que cp+2 = x ou

x+1, pois se cp+2 ≥ x+2 ou cp+2 ≤ x−1, chegaŕıamos nos mesmos absurdos do caso anterior.

Se cp+2 = x+1 então (3) é satisfeita, se cp+2 = x então raciocinando da mesma forma cp+3 = x

ou x+1. . . . Assim para um determinado q com p < q ≤ j, cq = x+1 e teremos a condição (3)

satisfeita.

Precisaremos agora de uma série de lemas que relacionam a Proposição 2.7.1 e o diagramaB(λ).

Definição 2.7.3 Sejam λ = (λ1, λ2, . . . , λs) � n, seqB(λ) =< c1, c2, . . . > e i, j ∈ Z+. Para

i > j, denotamos por ei,j a entrada da linha ci com a coluna cj do diagramaB(λ). Para

j ∈ {1, . . . , s}, denotamos por fi,j a entrada da linha ci com a coluna λj .

� � � � λ1 λ2 · · · λs

� � � c1 f1,1 f1,2 · · · f1,s

� � c2 e2,1 f2,1 f2,2 · · · f2,s

� c3 e3,2 e3,1 f3,1 f3,2 · · · f3,s

. .
.

e4,3 e4,2 e4,1 f4,1 f4,2 · · · f4,s
...

...
...

...
...

... · · ·
...

Observação 2.7.2 Sejam i, j ∈ Z+, i ≥ 2. Segue das definições:

1) ei,i−1 = 1

2) Se ei,j = 1, então cj ≥ i− j. Se ainda ei+1,j = 0 então cj = i− j

3) Por outro lado, se ei,j = 1, então ei−1,j = ei−2,j = . . . = 1.

4) Se ei,j = 0 então ei+1,j = ei+2,j = . . . = 0. Se ainda ei+1,j+1 = 1 então cj+1 = cj + 1.

5) Dados i, k ∈ Z+, se ci = k e ci+1 = ci + 1 e, sem perda de generalidade, as k primeiras

entradas da linha de ci forem 1’s então as k+1 primeiras entradas da linha de ci+1 são também

formadas por 1’s.

Lema 2.7.1 Seja λ � n = 1 + 2 + . . .+ k, k ∈ Z+, e seqB(λ) =< c1, c2, . . . >. Então

(1) dB(λ) = t, com seqB(λ) =< c1, . . . , ct−1, ct, ct+1, ct+2, . . . >=< c1, . . . , ct−1, k − 1, k, k, . . . >.

(2) Se dB(λ) = t, com t ≥ k + 1, então pelo menos uma das seguintes condições é satisfeita:

(i) (cp, cp+1, cp+2, . . . , cq−1, cq) = (k − 1, k, k, . . . , k, k + 1) para inteiros positivos p, q com

t− k ≤ p < q ≤ t− 1 e q ≥ p+ 2;

(ii) (cp, cp+1, cp+2, . . . , cq−1, cq) = (k− 2, k− 1, k− 1, . . . , k− 1, k) para inteiros positivos p, q

com t− k + 1 ≤ p < q ≤ t + 1 e q ≥ p+ 2.

44


Demonstração: (1) Como dB(λ) = t, por definição B(t)(λ) é B-ćıclica. Pelo Corolário 3.3.1,

B(t)(λ) = (k, k − 1, . . . , 2, 1), já que n = 1 + 2 + . . . + k. Assim, por definição, ct+1 = k. Pela

definição da aplicação B-shift temos B(t)(λ) = B(t+1)(λ) = B(t+2)(λ) = . . ., logo ct+1 = ct+2 =

ct+3 = . . .. Assim, seqB(λ) =< c1, . . . , ct, k, k, . . . >.

Falta provarmos que ct = k − 1. Para isso, sejam μ e γ as partições de tamanhos ct e ct+1

respectivamente, então μ �= γ pois se μ = γ, então dB(λ) < t, o que é um absurdo.

Pelo Corolário 3.3.1, γ = (k, k − 1, . . . , 2, 1). Se ct = k, então pela definição de B-shift,

μ = (k, k − 1, . . . , 2, 1), o que é um absurdo. Assim ct �= k.

Se ct ≥ k+ 1, então ct + ct+1 + . . .+ ct+k ≥ k+1+ (k− 1)k = k2 +1, o que é um absurdo pela

Proposição 2.7.1(2).

Se ct ≤ k − 2, então ct+1 > ct + 1, o que é um absurdo pela Proposição 2.7.1(1).

Logo, ct = k − 1 e portanto seqB(λ) =< c1, . . . , ct−1, k − 1, k, k, . . . >.

(2) Pela Observação 2.7.2, temos et,t−1 = 1. Como ct = k − 1, seque que et,i = 0 para algum i,

t− k ≤ i ≤ t− 2. Escolhemos tal i como sendo o maior posśıvel.

Assim et,i+1 = 1, e, como ct+1 = k = ct + 1, pelo item 5) da Observação 2.7.2, temos

et+1,i+1 = 1. A Proposição 2.7.1(1) nos dá ci ≥ ci+1 − 1, o que força et−1,i = 1. Logo, temos

et−1,i = 1 e et,i = 0 e pelo item 2) da Observação 2.7.2 segue que ci = t− i− 1.

Como et,i = 0 e et+1,i+1 = 1, pelo item 4) da Observação 2.7.2 segue que ci+1 = ci + 1 e

assim temos ci+1 = t− i.

Se t − k + 1 ≤ i ≤ t− 2 então, ci ≤ k − 2 e assim (ii) vale pela propriedade do sandúıche,

pois temos ci = k − 2 quando i = t − k + 1, ci < k − 1 < cj = k, com j = t + 1, logo existem

inteiros p e q tal que i = t − k + 1 ≤ p < q ≤ j = t + 1 com (cp, cp+1, cp+2, . . . , cq−1, cq) =

(k − 2, k − 1, k − 1, . . . , k − 1, k).

Se i = t−k então ct−k = k−1 e ct−k+1 = k. Se cj ≤ k−2 para algum j, t−k+2 ≤ j ≤ t−1,

então (ii) vale pela propriedade do sandúıche pela mesma justificativa anterior. Se cj ≥ k + 1

para algum j, t−k+2 ≤ j ≤ t−1, então (i) vale pela propriedade do sandúıche, pois ci = k−1

com i = t− k, ci + 1 = k e cj ≤ k + 1, t− k + 2 ≤ j ≤ t− 1, ou seja, temos ci < k < cj, logo

existem p e q tal que i ≤ p < q ≤ j e (cp, cp+1, cp+2, . . . , cq−1, cq) = (k − 1, k, k, . . . , k, k + 1).

Suponha por absurdo que k − 1 ≤ cj ≤ k para j = t− k + 2, t− k + 3, . . . , t− 1, pois caso isso

ocorrer (i) ou (ii) não vale. Como i = t − k, a linha de ct consiste em k − 1 1’s consecutivos,

seguidos por 0’s. A linha ct+1 é formada de k 1’s consecutivos, seguidos por 0’s. Há k 1’s no

topo das colunas ct+1, ct+2, . . ..

Assim no retângulo formado abaixo de ct−1 e à direita de ct temos k − 1 1’s na primeira linha

e k − j + 1 1’s nas linhas j, 2 ≤ j ≤ k. Nas linhas abaixo, tudo é zero. No total temos

45


n− 1 1’s nesse retângulo, o que é uma contradição, já que esse retângulo representa, depois de

reordenadas as colunas se necessário, a partição B(t−1)(λ) de n.

Lema 2.7.2 Sejam λ � n e seqB(λ) =< c1, c2, . . . >. Se para inteiros p e k,

(cp, cp+1, cp+2, . . . , cp+k−1, cp+k) = (k − 2, k − 1, k − 1, . . . , k − 1, k),

então p+ k ≤ n+ 1.

Demonstração: Temos que ep+k−2,p = 1 e ep+k−1,p = 0, já que cp = k− 2. Pela condição dada

na hipótese, na linha cp+k também temos ep+k,j = 1 para j = p+ 1, p+ 2, . . . , p + k − 1. Note

que a soma dessas entradas resulta em k − 1, e, portanto, ainda falta completar uma entrada

com 1 no diagramaB(λ) na linha de cp+k, já que cp+k = k. Esse 1 que falta em uma dessas

entradas no diagramaB(λ), ou vem da coluna de algum λj, 1 ≤ j ≤ s, ou vem da coluna de

algum cj, 1 ≤ j ≤ p− 1.

Se acontecer o primeiro caso então temos p + k ≤ λj ≤ n e j = 1, pois se 2 ≤ j ≤ s, como

λ1 ≥ λ2 ≥ . . . então λj−1 = 1 e áı haveriam k + 1 1’s na na linha de cp+k, absurdo.

Se acontecer o segundo caso então p + k ≤ cj ≤ n + 1 e j = 1, pois se p − 1 ≤ j ≤ 2

teremos ep+k,j−1 = 0 e como cp+k = k = cp+k−1 + 1, comparando as linhas cp+k e cp+k−1

no diagramaB(λ) também teremos ep+k−1,j−1 = 0. Analogamente, como cp+k−1 = cp+k−2,

ep+k−2,p = 1 e ep+k−1,p = 0, comparando as linhas cp+k−1 e cp+k−2 no diagramaB(λ) teremos

ep+k−2,j−1 = 0. Assim cj > cj−1 + 1, o que é uma contradição pela Proposição 2.7.1(1).

Lema 2.7.3 Sejam λ � n e seqB(λ) =< c1, c2, . . . >. Se para inteiros x, p e q, com q ≥ p+3 e

(cp, cp+1, cp+2, . . . , cq−1, cq) = (x− 1, x, x, . . . , x, x+ 1),

então ou p ≤ x ou

(cp′, cp′+1, cp′+2, . . . , cq′−1, cq′) = (x′ − 1, x′, x′, . . . , x′, x′ + 1),

para inteiros x′, p′ e q′, com x′ ≤ x, 2 ≤ q′ − p′ < q − p, e p− x ≤ p′ < q′ ≤ p+ 1.

Demonstração: Vamos assumir p ≥ x+ 1 e provar a existência de p′, q′ e x′. Como

cp = x − 1 então temos que ep,p′ = 0 para algum p′, p − x ≤ p′ ≤ p − 2. Escolhemos o maior

p′ posśıvel que satisfaça essa condição. Assim ep,j = 1 para j = p′ + 1, p′ + 2, . . . , p − 1, e,

como cp+1 = x = cp + 1, comparando as linhas de cp e cp+1 no diagramaB(λ) , também temos

ep+1,j = 1 para j = p′ + 1, p′ + 2, . . . , p. A coluna abaixo de cp′+1 possui 1’s até pelo menos no

46


cruzamento com a linha cp+1. A Proposição 2.7.1(1) nos diz que cp′ ≥ cp′+1 + 1, o que força

todas as entradas, acima de 0 em ep,p′, e serem 1. Assim cp′ = p− p′ − 1, pois ep−1,p′ = 1 então

cp′ ≥ p − 1 − p′ e também ep,p′ = 0. Também temos cp′+1 = p − p′, pois ep+1,p′+1 = 1 então

cp′+1 ≥ p+1−p′−1 = p−p′ e também ep+2,p′+1 = 0, pois se ep+2,p′+1 = 1 então cp′+1 > cp′ +1,

absurdo.

Como cp+2 = x = cp+1, comparando as linhas de cp+2 e cp+1 no diagramaB(λ) temos ep+2,j = 1

para j = p′ + 2, p′ + 3, . . . , p + 1. Se ep+3,p′+2 = 1 então cp′+2 ≥ p + 3 − p′ − 2 = p − p′ + 1 e

como ep+4,p′+2 = 0 então cp′+2 = p− p′ + 1 e assim terminamos. Assim podemos assumir que

ep+3,p′+2 = 0 e cp′+2 = p− p′.

Como cp+3 = x = cp+2, comparando as linhas de cp+3 e cp+2 no diagramaB(λ) temos ep+3,j = 1

para j = p′ + 3, p′ + 4, . . . , p + 2. Se ep+4,p′+3 = 1 então cp′+3 ≥ p + 4 − p′ − 3 = p − p′ + 1 e

como ep+5,p′+3 = 0 então cp′+3 = p− p′ + 1 e assim terminamos. Assim podemos assumir que

ep+4,p′+3 = 0 e cp′+3 = p− p′. Continuando esse processo...

Podemos assumir que eq−1,p′+q−p−2 = 0, cp′+q−p−2 = p− p′, e eq−1,j = 1 para

j = p′ + q − p − 1, p′ + q − p, . . . , q − 2. Como cq = x + 1 = cq−1 + 1, comparando as linhas

de cq e cq−1 no diagramaB(λ), temos eq,p′+q−p−1 = p− p′ + 1. E assim completamos a prova do

teorema.

Lema 2.7.4 Sejam λ � n e seqB(λ) =< c1, c2, . . . >. Se

(cp, cp+1, cp+2) = (x− 1, x, x+ 1)

então p ≤ x.

Demonstração: Vamos supor que p > x. Então cp = x − 1 < p − 1 que implica ep,i = 0

para algum i, 1 ≤ i ≤ p − 2. Escolha o maior i posśıvel que satisfaça essa condição, e assim

ep,i+1 = 1. Como cp+1 = x = cp +1 e cp+2 = x+1 = cp+1 +1, comparando as linhas de cp, cp+1

e cp+2 no diagramaB(λ), temos também ep+2,i+1 = ep+1,i+1 = 1. Assim ci+1 > ci + 1, o que é

uma contradição pela Proposição 2.7.1(1).

Agora temos condições de provar o próximo teorema.

Teorema 2.7.2 Se n = Tk = 1 + 2 + . . .+ k, k ∈ Z+, então

DB(n) = k2 − k.

Demonstração: Provamos no Teorema 2.4.1 que DB(n) ≥ k2− k. Basta agora provarmos que

que DB(n) ≤ k2 − k.

47


Seja λ � n, é suficiente mostrar que dB(λ) ≤ k2−k. Vamos assumir que k ≥ 3, pois quando

k ≤ 2, dB(λ) ≤ k2 − k, já que para k = 1, (1) é a única partição de 1 e quando k = 2 temos

n = 3, e as partições de 3 são (2, 1), (3), (1, 1, 1). Além disso, assumimos que dB(λ) ≥ k + 1,

pois se dB(λ) ≤ k, como k ≥ 3, então dB(λ) ≤ k < k2 − k.

Seja seqB(λ) =< c1, c2, . . . > onde < ct, ct+1, ct+2, . . . >=< k−1, k, k, . . . >. Assim dB(λ) = t

e pelo menos (i) ou (ii) do Lema 2.7.1 vale.

Se (ii) vale com q = p + k (que é o valor máximo para q), então temos p = t − k + 1 e

q = t+1. Note que o Lema 2.7.2 nos dá p+k ≤ n+1. Então dB(λ) = t = p+k−1 ≤ n ≤ k2−k,

já que k ≥ 3.

Se não, (i) ou (ii) vale e q ≤ p + k − 1. Utilizando os Lemas 2.7.3 e 2.7.4, a seqB(λ)

tem no máximo (k − 1)+(3 + 4 + . . .+ (k − 2) + (k − 1))+((k − 3) + (k − 4) + . . .+ 2 + 1) =

k2 − 2k − 1 termos antes do termo cp:

seqB(λ) =<

�k−1︷ ︸︸ ︷
c1, . . . , ck−1,

�3︷ ︸︸ ︷
ck, ck+1, ck+2,

�k−3︷ ︸︸ ︷
ck+3, . . . , c2k−1,

�4︷ ︸︸ ︷
c2k, c2k+1, c2k+2, c2k+3,

�k−4︷ ︸︸ ︷
c2k+4, . . . , c3k−1, . . .

. . . ,

�k−2︷ ︸︸ ︷
cp−2k, . . . , cp−k−3,

�2︷ ︸︸ ︷
cp−k−2, cp−k−1,

�k−1︷ ︸︸ ︷
cp−k, . . . , cp−2,

�1︷︸︸︷
cp−1,

�k︷ ︸︸ ︷
cp, . . . , cp+k−1>

Assim dB(λ) = t ≤ (p− 1) + k + 1 ≤ (k2 − 2k − 1) + k + 1 ≤ k2 − k.

Definição 2.7.4 Seja λ � n, n = 1+ 2+ . . .+ k, k ∈ Z+. Se dB(λ) = k2− k então chamamos

λ de partição extrema.

Observamos que para k = 2 (resp. k = 3), λ = (1, 1, 1) (resp., λ = (2, 2, 1, 1)) é a única

partição de n = 1 + 2 + . . .+ k tal que dB(λ) = k2 − k. Para k ≥ 4,temos:

Teorema 2.7.3 Sejam k ≥ 4 e n = 1 + 2 + . . . + k, k ∈ Z+. Se λ � n, com dB(λ) = k2 − k,

então a sua matriz associada Mλ = [mij ]
∞
i,j=1 satisfaz as seguintes condições:

(1) mij = 1 para j ≤ k + 3− 2i,

(2) mij = 0 para j ≥ 2k + 1− 2i, e

(3) |{(i, j) : j = k + 4− 2i,mij = 0}| ≤ 2.

Demonstração: Se k ≥ 4 e dB(λ) = k2−k, a demonstração do Teorema 2.7.2 implica que (i) do

Lema 2.7.1 vale e q = p+k−1. Portanto, temos seqB(λ) =< c1, c2, . . . > onde (ck, ck+1, ck+2) =

(k − 1, k, k + 1) e (c2k, c2k+1, c2k+2, c2k+3) = (k − 1, k, k, k + 1). Nessas condições temos no

diagramaB(λ) que ek+2,k+1 = 1 e ek+2,k = 1. Também temos ek+2,i = 1 para i = 1, 2, . . . , k− 1,

pois caso contrário escolhemos o maior i posśıvel tal que 1 ≤ i ≤ k−1 e ek+2,i = 0, comparando

as linhas de ck+2, ck+1 e ck no diagramaB(λ), teremos ek,i = ek+1,i = 0 o que implica ci+1 > ci+1,

o que é um absurdo. Portanto, ci ≥ k + 2 − i para i = 1, 2, . . . , k + 2, e assim a Condição (1)

48


vale.

Temos também e2k,i = 1 para i = k + 1, k + 2, . . . , 2k − 1, pois caso contrário escolhemos o

maior i posśıvel tal que k+3 ≤ i ≤ 2k− 2 e e2k,i = 0. Logo e2k,i+1 = 1. Note que e2k+1,k+1 = 1

e e2k+2,k+1 = 0, já que ck+1 = k. Comparando as linhas c2k, c2k+1 e c2k+2 no diagramaB(λ),

temos e2k+2,i+1 = e2k+1,i+1 = 1 e assim ci+1 > ci + 1, o que é um absurdo. Portanto, e2k,i = 0

para i = 1, 2, . . . , k e a Condição (2) vale.

Como e2k,k+3 = 1, comparando as linhas c2k, c2k+1, c2k+2 e c2k+3 no diagramaB(λ), temos

e2k+3,k+3 = e2k+2,k+3, e2k+1,k+3 = 1, e assim ck+3 ≥ k. Portanto, temos

k+2∑
j=1

ek+3,j ≥ k, e assim a

Condição (3) vale.

Computacionalmente foi checado que a rećıproca do teorema é válida para k = 4, 5, 6, 7, em

particular a rećıproca com a condição (3) removida também é válida para k = 4, 5, 6. Quando

k = 8, existem 1.276 partições de k satisfazendo as 3 condições do Teorema 2.7.3, mas 9 dessas

partições tem dB(λ) �= 20 = k2 − k, são elas:

(1) (7, 7, 6, 6, 3, 3, 2, 1, 1)

(2) (7, 7, 6, 6, 3, 2, 2, 2, 1)

(3) (7, 7, 6, 6, 3, 2, 2, 1, 1, 1)

(4) (7, 7, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1)

(5) (7, 7, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1)

(6) (7, 7, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1)

(7) (5, 5, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1)

(8) (5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1)

(9) (5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1)

Portanto as três condições do Teorema 2.7.3 são necessárias mas não são suficientes para a

matriz associada das partições extremas.

2.8 Cálculo de Limites de DB(n) para números não tri-

angulares

Para qualquer número não triangular n, podemos escrevê-lo como n = 1+2+ . . .+(k−1)+r,

tal que 1 ≤ r < k, k ∈ Z+.

Nesta seção primeiramente vamos provar que DB(n) ≤ k2 − k baseado no Teorema 2.7.2 e

depois vamos melhorar esse limite para k2 − 2k − 1 para k ≥ 4. Também apresentaremos um

49


limite inferior.

Seja Λ =

∞⋃
i=1

Λi, onde Λi denota o conjunto que contém todas as partições de i, conforme

definido em 2.1.2.

Definição 2.8.1 Para λ = (λ1, λ2, . . .) e μ = (μ1, μ2, . . .) ∈ Λ, definimos uma ordem parcial,

ou seja, reflexiva, antissimétrica e transitiva por:

λ ≤ μ⇐⇒ λi ≤ μi, para i = 1, 2, . . .

Lema 2.8.1 Sejam x1, x2, . . . e y1, y2, . . . (não necessariamente em ordem não crescente) as

partes das partições x e y, x, y ∈ Λ, respectivamente. Se xi ≤ yi, para i ≥ 1, então x ≤ y.

Demonstração: Sem perda de generalidade assumimos que x1, x2, . . . estão em ordem não

crescente. Se y1 < y2, trocamos y1 e y2 e xi ≤ yi, para i ≥ 1, continua valendo. Se y2 < y3,

trocamos y2 e y3 e assim xi ≤ yi, para i ≥ 1, continua valendo. Continuando com esse processo,

podemos rearranjar todos os y′is em ordem não-crescente e xi ≤ yi, para i ≥ 1, e assim x ≤ y.

Teorema 2.8.1 Se λ, μ ∈ Λ e λ ≤ μ então B(λ) ≤ B(μ).

Demonstração: Seja λ, μ ∈ Λ então para algum n ∈ N∗, λ ∈ Λn e para algumm ∈ N∗, μ ∈ Λm.

Sem perda de generalidade suponha que λ = (λ1, λ2, . . . , λs) � n e que μ = (μ1, μ2, . . . , μt) � m

Então as partes de B(λ) são x1 = s, x2 = λ1 − 1, x3 = λ2 − 1, . . . , xs+1 = λs − 1.

Analogamente as partes de B(μ) são y1 = t, y2 = μ1 − 1, y3 = μ2 − 1, . . . , yt+1 = μt − 1.

Como xi ≤ yi, para i ≥ 1, pelo Lema 2.8.1, temos B(λ) ≤ B(μ).

Combinando o Teorema 2.8.1 com o Teorema 2.7.2, podemos mostrar o próximo Teorema.

Teorema 2.8.2 Seja n = 1 + 2 + . . .+ (k − 1) + r, 1 ≤ r < k. Então:

DB(n) ≤ k2 − k

Demonstração: Seja λ � n. É suficiente mostrar que dB(λ) ≤ k2 − k. Escolha μ e ν tal

que μ � (1 + 2 + . . . + (k − 1)), ν � (1 + 2 + . . . + k) e μ ≤ λ ≤ ν. Pelo Teorema 2.8.1,

temos que B(k2−k)(μ) ≤ B(k2−k)(λ) ≤ B(k2−k)(ν). Note que o Teorema 2.7.2 nos dá B(k2−k)(μ) =

(k−1, k−2, . . . , 2, 1) e B(k2−k)(ν) = (k, k−1, . . . , 2, 1). Portanto B(k2−k)(λ) tem a forma ćıclica

do Teorema 2.4.1 e assim dB(λ) ≤ k2 − k.

Vamos provar um lema análogo ao Lema 2.7.1, mas agora para números não triangulares.

Aplicando esse Lema junto com os Lemas 2.7.2, 2.7.3 e 2.7.4, vamos melhorar o limite superior

de DB(n) para números não triangulares.

50


Lema 2.8.2 Sejam n = 1 + 2 + . . .+ (k − 1) + r, 1 ≤ r < k, λ � n e seqB(λ) =< c1, c2, . . . >.

(1) Se (ct, . . . , ct+k−1) = (ct+k, . . . , ct+2k−1) = . . ., ou seja, ct+i = ct+i+k para i ≥ 0, então

dB(λ) ≤ t−1. (Assim podemos encontrar dB(λ) escolhendo tal t como sendo o menor posśıvel.)

(2) Se ct = k − 1, ct+1 = k, ct+i = ct+i+k para i ≥ 0, dB(λ) ≥ k + 1 e (ct−k, . . . , ct−1) �=

(ct, . . . , ct+k−1), então pelo menos (i) ou (ii) do Lema 2.7.1 vale.

Demonstração: (1) Se ct+i = ct+i+k para i ≥ 0, então cada ct+i é o número de partes de

alguma partição B-ćıclica de n, e assim o Teorema 2.4.1 nos garante que k− 1 ≤ ct+i ≤ k para

i ≥ 0. Em particular, note que cada linha de ct, ct+1, . . . , ct+k−1, no diagramaB(λ), consiste em

k − 1 ou k 1’s.

Pela Observação 2.7.1 item 2), temos que o retângulo formado abaixo de ct−1 e à direita de

ct, ignorando os zeros e, se necessário, reorganizando as colunas, nos dá B(t−1)(λ). Observe que

se ct+i = k− 1 para todo i = 0, . . . , k− 1, então haverá 1+ 2+ . . .+(k− 1) 1’s nesse retângulo,

o que seria uma absurdo, pois ele representa B(t−1)(λ). Assim ct+i = k para pelo menos algum

i = 0, . . . , k − 1.

Também não podemos ter ct+i = k para i = 0, . . . , k − 1, pois chegaŕıamos no mesmo

absurdo do caso anterior e assim temos que ter ct+i = k − 1 para algum i = 0, . . . , k − 1. (Ver

Exemplo abaixo com n = 13).

Logo a partição B(t−1)(λ) possui a forma ćıclica do Teorema 2.4.1 e assim é uma partição

B-ćıclica , e portanto dB(λ) ≤ t− 1.

� � � � � � � . . . . . . . . . . . .

� � � � � � ct−1 . . . . . . . . . . . .

� � � � � ct 1 1 1 1 1

� � � � ct+1 1 1 1 1 1 0

� � � ct+2 1 1 1 1 0 0 0

� � ct+3 1 1 1 1 1 0 0 0

� ct+4 1 1 1 1 0 0 0 0 0

. .
. ...

...
...

...
...

...
...

...
...

...
...

...
...

...
...

...
...

...
...

...
...

Exemplo: n = 13, ou seja, k = 5 e r = 3

(2) A demonstração é análoga à do Lema 2.7.1(2). No último caso, vamos supor por absurdo

que ct−k = k − 1, ct−k+1 = k, e k − 1 ≤ cj ≤ k, para j = t− k+ 2, t− k+ 3, . . . , t− 1. Análoga

51


à demonstração de (1) o retângulo abaixo de ct−k−1 e à direita de ct−k no diagramaB(λ), nos

mostra que B(t−k−1)(λ) é B-ćıclica. Assim, pelo Teorema 2.4.1, B(t−k−1+i)(λ) = B(t−1+i)(λ) para

i ≥ 0. Contando o número de partes de cada partição, temos (ct−k, . . . , ct−1) = (ct, . . . , ct+k−1),

o que contradiz a hipótese..

Teorema 2.8.3 Seja n um número não triangular, n = 1 + 2 + . . . + (k − 1) + r, 1 ≤ r < k.

Então:

(1) DB(n) ≤ k2 − 2k − 1 para k ≥ 4.

(2) A igualdade vale quando k ≥ 4 e r = k − 1

Demonstração: (1) Se k = 4 temos que r pode assumir os valores de 1, 2 ou 3 e assim n

pode assumir os valores de 7, 8 ou 9. DB(7) = 4 pela Figura 2.8, DB(8) = 5 pela Figura 2.15

e DB(9) = 7 pela Figura 2.22. Portanto DB(n) ≤ 7 para k = 4, e assim podemos assumir que

k ≥ 5.

Sejam λ � n e seqB(λ) =< c1, c2, . . . >. É suficiente mostrar que dB(λ) ≤ k2 − 2k − 1. Seja

B(t−1)
(λ) uma partição B-ćıclica para algum t ≥ 1. Logo o Teorema 2.4.1 nos dá ct+i = ct+i+k

e k − 1 ≤ ct+i ≤ k para i ≥ 0, e assim pelo Lema 2.8.2(1), dB(λ) ≤ t − 1. Também podemos

assumir ct = k − 1 e ct+1 = k, já que r �= k, e escolhemos tal t como o menor posśıvel.

Se t ≤ k, então dB(λ) ≤ t− 1 ≤ k − 1 < k2 − 2k − 1, já que k ≥ 5.

Logo, assumimos t ≥ k + 1 e (ct−k, . . . , ct−1) �= (ct, . . . , ct+k−1), já que escolhemos o menor t

posśıvel. Assim, pelo Lema 2.8.2(ii), pelo menos (i) ou (ii) do Lema 2.7.1 vale.

Se (ii) vale com q = p + k, temos (p, q) = (t − k + 1, t + 1). Note que o Lema 2.7.2 nos dá

p+ k ≤ n + 1. Assim, dB(λ) ≤ t− 1 = p+ k − 2 ≤ n− 1 < k2 − 2k − 1 já que k ≥ 5.

Se não, (i) ou (ii) vale e q ≤ p+ k− 2, pelos Lemas 2.7.3 e 2.7.4, a seqB(λ) tem no máximo

k2− 3k− 1 termos antes do termo cp. Logo, dB(λ) ≤ t− 1 ≤ (p− 1) + k ≤ (k2− 3k− 1) + k =

k2 − 2k − 1.

Se não, suponha por absurdo que (i) ou (ii) vale com q = p + k − 1: se (i) vale com

q = p + k − 1, temos que (p, q) = (t − k, t − 1) e ct−1 = k + 1, o que é uma contradição,

pois teremos (cp, . . . , cq) = (

k elementos︷ ︸︸ ︷
ct−k, . . . , ct−1) = (k − 1, k, . . . , k, k + 1). Fazendo a soma desses k

elementos cp + . . .+ cq = (k − 1) + (k − 2)k + k + 1 = (k − 1)k + k e pela Proposição 2.7.1(2)

essa soma é no máximo (k − 1)k + r, 1 ≤ r < k. Se não (ii) vale com q = p + k − 1 e temos

(p, q) = (t − k + 2, t + 1) e ct−k+2 = k − 2, o que é uma contradição, já que, comparando as

linhas de ct+1 e ct no diagramaB(λ), temos que ct−k+2 �= k − 2.

(2) Suponha k ≥ 4 e r = k−1. Por (1), é suficiente exibir λ � n tal que dB(λ) = k2−2k−1.

Seja λ = (λ1, λ2, . . . , λk, λk+1), onde λ1 = k − 1, λ2 = k − 2, λi = k − i+ 1 para i = 3, 4, . . . , k

52


� � �

� � � � �

� � � � �

� � � � � � �

� � � � � � �

� � � � �

� 	 � � � � �

� 	 � � � � �

� � � � � � � � �

� 	 � 
 �

� 
 � � � � �

� 
 � � � � � � �

� 	 � � � � � � �

� 
 � 
 � � � � 	 � � � � � � � � �

� � � � � � �

� � � � � � � � �

� 
 � � � � � � �

� 
 � � � � � � � � �

� 
 � � � � � � � � � � �
� � � � � � � � �

� � � � � � � � � � �

� � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � � � � � � � �

� � � � � � � � � � �� � � � � � � � � � � � �

� � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

Figura 2.22: Diagrama B-shift de n=9, estilo RadialDrawing

e λk+1 = 1. Assim λ = (k − 1, k − 2, k − 2, k − 3, k − 4, . . . , 3, 2, 1, 1). Fazendo a matriz asso-

ciada Mλ temos que as diagonais de 1 a (k − 1) são formada apenas por 1’s, a diagonal k é da

forma (0, 0, 1, . . . , 1, 1), a diagonal k+1 é da forma (0, 0, 0, . . . , 0, 0, 1) e as diagonais abaixo da

diagonal k + 1 são formadas apenas de 0’s.

53


k−1alinha
−→

kalinha
−→

k+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 1 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mλ

Com a forma da matriz Mλ definida, ao aplicar k vezes o processo B-shifting em Mλ, apenas

DMλ
(k + 1) é alterada, pois as outras diagonais são formadas apenas por 1’s ou são formadas

apenas por 0’s e a diagonal k permanece a mesma também pois possui k elementos. Note que

nessas k vezes foi preciso apenas utilizar o Passo 1 do processo (Shift Circular Diagonal) por

causa da configuração de Mλ. Assim, as diagonais DMλ
(k + 1) e DMλ

(k) se comportam da

seguinte maneira:

� Processo B-shifting em Mλ (Passo 1) DMλ
(k) DMλ

(k + 1)

k (0, 0, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 0, 0, . . . , 0, 0, 1, 0)︸ ︷︷ ︸
k+1

2k (0, 0, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 0, 0, . . . , 0, 1, 0, 0︸ ︷︷ ︸
k+1

)

...
...

...

(k − 3)k (0, 0, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k

) (0, 0, 1, 0 . . . , 0, 0, 0)︸ ︷︷ ︸
k+1

...
...

...

(k − 3)k + (k − 1) (0, 1, 1, . . . , 1, 1, 0︸ ︷︷ ︸
k

) (0, 1, 0, 0, . . . , 0, 0, 0︸ ︷︷ ︸
k+1

)

Assim depois de aplicados (k − 3)k + (k − 1) = k2 − 2k − 1 vezes o Passo 1 do processo

B-shifting em Mλ, chegamos em uma matriz Mθ com a seguinte configuração:

54


k−1alinha
−→

kalinha
−→

k+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 0 0 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

0 1 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mθ

Há mais 1’s na segunda coluna do que na primeira, logo precisamos aplicar o Passo 2 do processo

B-shifting em Mθ e assim obtemos a matriz MB(k2−2k−1)(λ) que é a matriz associada da partição

B(k2−2k−1)(λ). Logo B(k2−2k−1)(λ) = (k, k − 1, k − 2, . . . , 3, 2) e portanto dB(λ) = k2 − 2k − 1.

k−1alinha
−→

kalinha
−→

k+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 0 0 · · ·

1 1 · · · 1 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= MB(k2−2k−1)(λ)

Até agora obtemos um limite superior para DB(n) no Teorema 2.8.3. A seguir iremos

determinar um limite inferior para DB(n) que é conjecturado como o valor exato.

Teorema 2.8.4 [Limite Inferior] Para n ≥ 3 e n = 1 + 2 + . . .+ (k − 1) + r, 1 ≤ r ≤ k,

DB(n) ≥

⎧⎪⎪⎨
⎪⎪⎩

(k − 3− r)k + r + 2 para 1 ≤ r < �k−1
2


n− k + 1 para r = �k−1
2
 ou �k+1

2


(r − 2)k + r para �k+1
2
 < r ≤ k

Demonstração: É suficiente exibir λ � n tal que dB(λ) é o valor do respectivo limite inferior

para DB(n).

Vamos considerar três casos:

Caso (1) 1 ≤ r < �k−1
2
: Seja λ = (λ1, λ2, . . . , λk) tal que λ1 = k − 2, λi = k − i para

i = 2, 3, . . . , k − r − 1, e λj = k − j + 1 para j = k − r, k − r + 1, . . . , k. Seja Mλ a sua

matriz associada. Assim as diagonais de 1 a (k− 2) são todas compostas de 1’s, DMλ
(k− 1) =

55


(0, 1, 1, . . . , 1︸ ︷︷ ︸
k−1

) e DMλ
(k) = (0, 0, 0, . . . , 0,

r+1︷ ︸︸ ︷
1, 1, . . . , 1︸ ︷︷ ︸

k

), e as diagonais abaixo de DMλ
(k) são todas

nulas. Com essa configuração dada, ao aplicar (k−1) vezes o processo B-shifting em Mλ, sendo

necessário apenas o Passo 1, somente DMλ
(k) se altera. Logo temos o seguinte comportamento

na matriz Mλ:

� Processo B-shifting em Mλ (Passo 1) DMλ
(k − 1) DMλ

(k)

(k − 1) (0, 1, 1, . . . , 1, 1, 1, 1︸ ︷︷ ︸
k−1

) (0, 0, 0, . . . , 0,

r+1︷ ︸︸ ︷
1, 1, . . . , 1, 0︸ ︷︷ ︸

k

)

2(k − 1) (0, 1, 1, . . . , 1, 1, 1, 1︸ ︷︷ ︸
k−1

) (0, 0, . . . , 0,

r+1︷ ︸︸ ︷
1, 1, . . . , 1, 0, 0︸ ︷︷ ︸
k

)

...
...

...

(k − r − 2)(k − 1) (0, 1, 1, . . . , 1, 1, 1, 1︸ ︷︷ ︸
k−1

) (0,

r+1︷ ︸︸ ︷
1, 1, . . . , 1, . . . , 0, 0, 0︸ ︷︷ ︸

k

)

Assim depois de aplicados (k− r− 2)(k− 1) vezes o Passo 1 do processo B-shifting em Mλ,

chegamos em uma matriz Mθ e análogo à demonstração do Teorema 2.8.3, usando o Passo 2

do processo B-shifting, obtemos a matriz MB(k−r−2)(k−1)(λ) que é a matriz associada da partição

B(k−r−2)(k−1)(λ) = (k − 1, k − 2, k − 3, . . . , 3, 2, 1) + (0, 0,

r︷ ︸︸ ︷
1, 1, . . . , 1, 0, . . . , 0) que por sua vez

é B-ćıclica e, portanto, dB(λ) = (k−r−2)(k−1) = k2−k−kr+r−2k+2 = (k−3−r)k+r+2.

Caso (2) r = �k−1
2
 ou �k+1

2
: Seja λ = (1, 1, . . . , 1︸ ︷︷ ︸

n

).

Vamos provar primeiramente através de indução sobre i que:

B(1+1+2+3+...+i)
(λ) = (n− (1 + 2 + . . . , i), i, i− 1, i− 2, . . . , 2, 1) (2.4)

para i = 1, . . . , k − 2.

Por definição da aplicação B-shift, B(λ) = (n) e B(2)(λ) = (n− 1, 1). Assim, (2.4) vale para

i = 1.

Agora suponha que (2.4) vale para i = k−3 e vamos provar que vale para i = k−2. Assim,

seja z = 1 + 1 + 2 + 3 + . . .+ (k − 3), temos:

B(z)
(λ) = (n−(1+2+. . .+(k−3)), k−3, k−4, . . . , 2, 1) = ((k−2)+(k−1)+r, k−3, k−4, . . . , 2, 1)

e assim a sua matriz associada MB(z) é da forma:

56


MB(z) =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 1 · · · 1 1 1 0 · · ·

1 1 1 1 · · · 1 1 0 0 · · ·

1 1 1 1 · · · 1 0 0 0 · · ·
...

...
... . .

.
. .
.

. .
. ...

...
... · · ·

1 1 1 1 . .
.

0 0 0 0 · · ·

1 1 1 0 0 0 0 0 0 · · ·

1 1 0 0 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
...

...
... · · ·

1 0 0 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

As diagonais de 1 a (k − 2) de MB(z) são formadas apenas por 1’s. Portanto a cada vez

aplicado o processo B-shifting em MB(z) apenas as diagonais com ı́ndices maiores que (k − 2)

são alteradas. Note que a coluna 1 possui (k − 2) + (k − 1) + r 1’s e a coluna 2 possui (k − 3)

1’s. Sendo assim aplicando o Passo 1 do processo B-shifting em MB(z) a coluna 2 fica maior

que a coluna 1 e portanto precisamos aplicar o Passo 2 para encontrarmos MB(z+1). Aplicando

o Passo 2 a diagonal (k − 1) recebe um novo 1 que é o mesmo 1 que a coluna 1 perde.

Assim, ao aplicar o processo, aumentou-se um 1 na diagonal (k − 1) e diminui-se um 1 na

coluna 1. Seguindo com o racioćınio temos:

� Processo B-shifting em MB(z) DMλ
(k − 1) Quantidade de 1’s na coluna 1

0 (1, 0, 0, . . . , 0︸ ︷︷ ︸
k−2

) (k − 2) + (k − 1) + r

1 (1, 1, 0, 0, . . . , 0︸ ︷︷ ︸
k−3

) (k − 3) + (k − 1) + r

2 (1, 1, 1, 0, 0, . . . , 0︸ ︷︷ ︸
k−4

) (k − 4) + (k − 1) + r

...
...

...

(k − 3) (1, 1, . . . , 1, 1, 0︸ ︷︷ ︸
k−2

) (1) + (k − 1) + r

(k − 2) (1, 1, . . . , 1, 1, 1︸ ︷︷ ︸
k−1

) (k − 1) + r

57


Logo, as diagonais de 1 a (k − 1) de MB(z+(k−2)) são formadas por 1’s e a coluna 1 possui

(k − 1) + r 1’s. Sendo assim MB(z+(k−2)) é a matriz associada da composição B(z+(k−2))(λ) =

B(1+1+2+3+...+(k−2)) = ((k− 1) + r, k− 2, k− 3, . . . , 2, 1) e assim terminamos a demonstração da

indução.

Seja y = z + (k − 2) = (1 + 1 + 2 + 3 + . . . + (k − 2)), logo, como demonstrado acima as

(k − 1) primeiras diagonais da matriz MB(y) são formadas apenas por 1’s, e assim utilizando o

mesmo racioćınio utilizado, a cada aplicação do processo B-shift em MB(y) apenas as diagonais

de ı́ndice maiores que (k − 1) são alteradas e assim:

� Processo B-shifting em MB(y) DMλ
(k) Quantidade de 1’s na coluna 1

0 (1, 0, . . . , 0︸ ︷︷ ︸
k

) (k − 1) + r

1 (1, 1, 0, . . . , 0︸ ︷︷ ︸
k

) (k − 1) + r − 1

2 (1, 1, 1, 0, . . . , 0︸ ︷︷ ︸
k

) (k − 1) + r − 2

...
...

...

(r − 2) (

r−1︷ ︸︸ ︷
1, 1, . . . , 1, 0︸ ︷︷ ︸

k

) (k − 1) + 2

(r − 1) (

r︷ ︸︸ ︷
1, 1, 1, . . . , 1, 0︸ ︷︷ ︸

k

) (k − 1) + 1

Assim, as diagonais de 1 a (k − 1) de MB(y+(r−1)) são formada por 1’s e a coluna 1 possui

(k − 1) + 1 1’s. Sendo assim MB(y+(r−1)) é matriz associada da partição

B(y+(r−1))(λ) = ((k − 1) + 1, (k − 2) + 1, . . . , (k − r) + 1, . . . , 3, 2, 1) que é B-ćıclica e portanto

dB(λ) = y + (r − 1) = 1 + 1 + 2 + 3 + . . .+ (k − 2) + (r − 1) = n− k + 1.

Caso (3) �k+1
2
 < r ≤ k: Seja λ = (λ1, λ2, . . . , λk+1) onde λi = k−i para i = 1, 2, . . . , k−r+1,

λj = k− j +1 para j = k− r+ 2, k− r+ 3, . . . , k e λk+1 = 1. Seja Mλ a sua matriz associada.

Assim as diagonais de 1 a (k− 1) são todas compostas de 1’s, DMλ
(k) = (0, 0, . . . ,

r−1︷ ︸︸ ︷
1, 1, . . . , 1︸ ︷︷ ︸
k

) e

DMλ
(k + 1) = (0, 0, . . . , 0, 1︸ ︷︷ ︸

k+1

). Logo temos o seguinte comportamento na matriz Mλ:

58


� Processo B-shifting em Mλ (Passo 1) DMλ
(k) DMλ

(k + 1)

k (0, 0, . . . ,

r−1︷ ︸︸ ︷
1, 1, . . . , 1︸ ︷︷ ︸
k

) (0, 0, . . . , 0, 1, 0︸ ︷︷ ︸
k+1

)

2k (0, 0, . . . ,

r−1︷ ︸︸ ︷
1, 1, . . . , 1︸ ︷︷ ︸
k

) (0, 0, . . . , 1, 0, 0︸ ︷︷ ︸
k+1

)

...
...

...

(r − 2)k (0, 0, . . . ,

r−1︷ ︸︸ ︷
1, 1, . . . , 1︸ ︷︷ ︸
k

) (0, 0, . . . ,

r−1︷ ︸︸ ︷
1, 0, . . . , 0, 0︸ ︷︷ ︸
k+1

)

...
...

...

(r − 2)k + (r − 1) (

r−1︷ ︸︸ ︷
1, 1, . . . , 1, 0, . . . , 0︸ ︷︷ ︸

k

) (1, 0, . . . , 0, 0︸ ︷︷ ︸
k+1

)

(r − 2)k + (r) (0,

r−1︷ ︸︸ ︷
1, 1, . . . , 1, 0, . . . , 0︸ ︷︷ ︸

k

) (0, 1, 0, . . . , 0, 0︸ ︷︷ ︸
k+1

)

Assim depois de aplicados (r − 2)k + (r) vezes o Passo 1 do processo B-shifting em Mλ,

chegamos em uma matriz Mθ e análogo à demonstração do Teorema 2.8.3, usando o Passo 2

do processo B-shifting, obtemos a matriz MB(r−2)k+(r)(λ) que é a matriz associada da partição

B(r−2)k+(r)(λ) = ((k−1)+1, (k−2)+1, (k−3)+1, . . . , (k−r)+1, (k−r+1), (k−r+2), . . . , 3, 2, 1)

que por sua vez é B-ćıclica e, portanto, dB(λ) = (r − 2)k + (r).

2.9 Conjectura

Em [4] foi lançada a seguinte conjectura, que até o presente trabalho não se tem not́ıcia de que

foi provada.

Conjectura 2.9.1 No Teorema 2.8.4, “DB(n) ≥” pode ser substitúıdo por “DB(n) =”.

A conjectura foi confirmada quando r = k − 1, k e para n = 3, 4, . . . , 36, ver Tabela 2.1.

59


Caṕıtulo 3

Paciência Carolina: Uma variação da

Paciência Búlgara

Vamos neste caṕıtulo definir formalmente a Paciência Carolina, criada por Andrey Andreev

e os elementos usados para mostrar as relações com a Paciência Búlgara e também demonstrar

alguns resultados análogos ao da Paciência Búlgara.

3.1 Composições e aplicação C-shift

Definição 3.1.1 (Composição) Seja n um inteiro positivo, dizemos que

λ = (λ1, λ2, . . . , λs) ∈ Zs, s = 1, . . . , n, é uma composição de n, e escrevemos λ |= n, se

λi > 0, ∀i = 1, . . . , s e
s∑

i=1

λi = n. Assim como na partição, λi, i = 1, . . . , s é i-ésima parte

da composição e também o seu comprimento (tamanho) é |λ| = s.

A diferença entre composição e partição de um número, é que na composição não necessari-

amente as partes tem que estar em ordem não crescente e se estiver a composição coincide com

a partição.

Exemplo 3.1.1 λ = (6, 1, 6) é uma composição do número 13 e possui 3 partes, |λ| = 3.

μ = (1, 1, 1, 1, 5, 3, 8) é uma composição do número 20 e possui 7 partes, |μ| = 7.

Definição 3.1.2 Seja n um inteiro positivo, definimos Γn = {λ | λ |= n} o conjunto de todas

as composições de n.

Análogo às partições de um inteiro n, vamos definir uma aplicação de Γn em Γn e posteri-

ormente a “Paciência Carolina”.

60


Definição 3.1.3 Dado um inteiro positivo n e λ = (λ1, λ2, . . . , λs) |= n. Definimos por

C-shift a aplicação, C : Γn −→ Γn, que associa λ à uma nova composição de n denotada por

C(λ), obtida da seguinte maneira:

i) diminui-se uma unidade de cada parte λi, i = 1, . . . , s. i = 1, . . . , s.

ii) Descarta(m) se a(s) parte(s) nula(s), caso houver.

iii) Cria-se uma nova parte de tamanho s, colocando-a como primeira parte.

Observação 3.1.1 Assim como na aplicação B-shift, se λ |= n possui s partes então C(λ)

possui no máximo s+ 1 partes.

Exemplo 3.1.2 Seja λ = (1, 5, 1, 7) |= 14, logo C(λ) = (4, 4, 6). Se μ = (2, 3, 1, 4) |= 10, então

C(μ) = (4, 1, 2, 3).

Utilizando a mesma ideias de blocos, podemos ver geometricamente o comportamento de

C-shift, conforme ilustra a Figura 3.1

Figura 3.1:

Definição 3.1.4 (Paciência Carolina) Dada uma composição λ de um inteiro positivo n,

descrevemos a “Paciência Carolina” de λ como sendo a sequência:

λ, C(λ), C(2)(λ), . . .

onde C(i)(λ), i ∈ Z+, representa a composição de n, obtida através de sucessivas aplicações de

C-shift em λ, no total de i vezes. Nesse caso dizemos que C(i)(λ) é a i-ésima iterada de λ pela

aplicação C-shift.

61


Ou seja, a “Paciência Carolina” de uma composição λ |= n, pensando como um sistema

dinâmico no conjunto Γn com a aplicação C-shift, nada mais é do que a sua órbita.

Exemplo 3.1.3 Seja λ = (2, 1, 1, 1, 1) |= 6, então temos C(λ) = (5, 1), C(2)(λ) = (2, 4),

C(3)(λ) = (2, 1, 3), C(4)(λ) = (3, 1, 2), C(5)(λ) = (3, 2, 1), C(6)(λ) = (3, 2, 1), . . . .

Exemplo 3.1.4 Seja μ = (6, 1) |= 7, assim temos C(μ) = (2, 5), C(2)(μ) = (2, 1, 4), C(3)(μ) =

(3, 1, 3), C(4)(μ) = (3, 2, 2), C(5)(μ) = (3, 2, 1, 1), C(6)(μ) = (4, 2, 1), C(7)(μ) = (3, 3, 1), C(8)(μ) =

(3, 2, 2), C(9)(μ) = (3, 2, 1, 1), C(10)(μ) = (4, 2, 1), . . ..

Observe que no Exemplo 3.1.3 após 5 iteradas de C em λ chegamos em uma composição que

não se modifica mais através de C. Já no Exemplo 3.1.4, após 4 iteradas de C em μ chegamos

em uma composição que se repete ao longo da sequência de iteradas.

Definição 3.1.5 Dizemos que uma composição μ = (μ1, μ2, . . . , μs) |= n é uma permutação

da composição λ = (λ1, λ2, . . . , λs) |= n, se as partes μi de μ são permutações das partes λi de

λ, i = 1, . . . , s.

Exemplo 3.1.5 A composição μ = (2, 1, 2, 4) |= 9 é uma permutação da composição

λ = (1, 4, 2, 2) |= 9.

Pela definição, podemos observar que dada uma composição μ = (μ1, μ2, . . . , μs) |= n ela

é sempre uma permutação de uma única partição λ = (λ1, λ2, . . . , λs) � n. Por exemplo, seja

μ = (2, 1, 4, 5) |= 12, organizando suas partes em ordem não crescente, temos que μ é uma

permutação da partição λ = (5, 4, 2, 1) � 12.

Observação 3.1.2 Um fato interesante e importante que será utilizado em demonstrações é

que se μ |= n é uma permutação de λ � n, então ∀i > 0, C(i)(μ) |= n é também uma permutação

de B(i)(λ) � n. Isso vem direto das definições de B-shift e C-shift já que ambas as aplicações

fazem exatamente o mesmo a menos de ordem das partes. Assim no mesmo “ńıvel” i de iteração

sempre teremos a permutação entre a composição e a partição.

3.2 Composições ćıclicas, dC(λ) e DC(n)

Analogamente para uma partição μ � n B-ćıclica, dB(μ) e DB(n) na Paciência Búlgara,

podemos definir uma composição λ |= n C-ćıclica, dC(λ) e DC(n) na Paciência Carolina.

Sejam n um inteiro positivo, λ |= n e C : Γn −→ Γn.

62


Definição 3.2.1 Dizemos que λ é C-ćıclica, ou simplesmente ćıclica, de peŕıodo i, se i é o

menor inteiro positivo tal que C(i)(λ) = λ. Assim o conjunto O(λ) = {λ, C(λ), C(2)(λ), . . . , C(i−1)(λ)}

é a sua órbita periódica, ou ciclo, e o seu peŕıodo é i. Nesse caso também podemos dizer que λ

é periódica de peŕıodo i.

Observação 3.2.1 (1) Se i = 1 dizemos que λ é uma composição fixa.

(2) Se a composição λ é ćıclica de peŕıodo i, então O(λ) = O(C(λ)) = . . . = O(C(i−1)(λ))

No Exemplo 3.1.3 (3, 2, 1) é uma composição fixa, enquanto no Exemplo 3.1.4 (3, 2, 2) é uma

composição C-ćıclica, de peŕıodo 4.

Definição 3.2.2 Definimos dC(λ) como sendo o menor inteiro i ≥ 0 tal que C(i)(λ) é C-ćıclica

e DC(n) := max{dC(λ) | λ |= n}.

Analogamente, vale também a mesma interpretação da Observação 2.2.2.

Exemplo 3.2.1 λ = (4, 1) |= 5. Fazendo as iterações em λ obtemos:

(4, 1)
C
→ (2, 3)

C
→ (2, 1, 2)

C
→ (3, 1, 1)

C
→ (3, 2)

C
→ (2, 2, 1)

C
→ (3, 1, 1)

C
→ . . .

Assim dC(λ) = 3 pois a composição μ = C(3)(λ) = (3, 1, 1) é C-ćıclica, já que C(3)(μ) = μ.

Exemplo 3.2.2 DC(4) = 3, pois as composições de 4 são: (1, 1, 1, 1), (3, 1), (1, 3), (2, 2),

(2, 1, 1), (1, 2, 1), (1, 1, 2), (4), e:

(1, 1, 2)

↓C

(1, 1, 1, 1)
C
→ (4)

C
→ (1, 3)

C
→ (2, 2)

C
→ (2, 1, 1)

C
→ (3, 1)

C
→ (2, 2)

C
→ (2, 1, 1) . . .

↑C

(1, 2, 1)

Pelo diagrama acima dC(1, 1, 1, 1) = 3, dC(3, 1) = 0, dC(1, 3) = 1, dC(2, 2) = 0, dC(2, 1, 1) =

0, dC(1, 2, 1) = 1, dC(1, 1, 2) = 1, dC(4) = 1.

Os valores de DC(n), 4 ≤ n ≤ 36, são mostrados na Tabela a seguir, calculados computa-

cionalmente. A representação de n é da forma n = 1 + 2 + 3 + . . .+ (k − 1) + r, 1 ≤ r ≤ k.

63


Tabela 3.1: Valores de DC(n), n = 4, . . . , 36

k = 3 k = 4 k = 5 k = 6 k = 7 k = 8

r = 1 DC(4) = 3 DC(7) = 6 DC(11) = 11 DC(16) = 19 DC(22) = 29 DC(29) = 41

r = 2 DC(5) = 5 DC(8) = 8 DC(12) = 12 DC(17) = 17 DC(23) = 23 DC(30) = 34

r = 3 DC(6) = 8 DC(9) = 10 DC(13) = 13 DC(18) = 18 DC(24) = 24 DC(31) = 31

r = 4 DC(10) = 15 DC(14) = 18 DC(19) = 21 DC(25) = 25 DC(32) = 32

r = 5 DC(15) = 24 DC(20) = 28 DC(26) = 32 DC(33) = 36

r = 6 DC(21) = 35 DC(27) = 40 DC(34) = 45

r = 7 DC(28) = 48 DC(35) = 54

r = 8 DC(36) = 63

3.3 Caracterização das Composições Ćıclicas

Vamos traçar o mesmo caminho que foi feito para a “Paciência Búlgara” para encontrarmos

a caracterização das composições ćıclicas e assim vamos definir uma matriz formada apenas por

0’s e 1’s que represente uma composição.

Definição 3.3.1 Dada uma composição λ = (λ1, λ2, . . . , λs) |= n definimos por Mλ a sua

matriz associada, se forma que:

Mλ = [mij ]
∞
i,j=1, onde mij =

⎧⎨
⎩

1, se j ≤ s e i ≤ λj ;

0, c.c.

Portanto, a matriz associada é a mesma usada para partições.

Exemplo 3.3.1 Seja λ = (2, 5, 3, 2, 4) |= 16, então:

Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 1 1 0 0 · · ·

1 1 1 1 1 0 0 · · ·

0 1 1 0 1 0 0 · · ·

0 1 0 0 1 0 0 · · ·

0 1 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

ou seja, o número de 1’s de cada coluna corresponde à respectiva parte da composição.

64


Análogo ao processo B-shifting para partições μ, vamos definir o processo C-shifting para

composições λ, para obtermos MC(λ), MC(2)(λ), . . ., a partir de Mλ somente deslocando 0’s e 1’s

das diagonais da matriz associada.

Definição 3.3.2 (Processo C-shifting) Sejam λ = (λ1, λ2, . . . , λs) |= n e Mλ = [mij ] a

sua matriz associada. O processo de obtenção de MC(λ) a partir de Mλ, chamado de Processo

C-shifting, é composto de no máximo 2 passos:

Passo 1: Shifting Circular Diagonal: É o mesmo Passo 1 do processo B-shifting para

partições, descrito na seção 2.4. Após esse passo, obtemos uma nova matriz, denotada por M ′
λ.

Note que a quantidade de 1’s nas colunas de M ′
λ são s, λ1 − 1, λ2 − 1, . . . , λs − 1, 0, 0, . . ..

Se λi − 1 = 0 e λi+1 − 1 > 0 para algum i, i = 1, . . . , s, ou seja, se tivermos uma coluna de

M ′
λ toda nula e a coluna posterior não nula, então precisamos de um passo extra para obtermos

MC(λ). Caso contrário, M ′
λ = MC(λ).

Passo 2. Shifting pela Esquerda: Sempre que para algum inteiro positivo j tal que a coluna

j de M ′
λ for toda nula e a coluna (j + 1) de M ′

λ não for, removemos a coluna j e deslocamos

cada coluna com ı́ndice maior para à esquerda. Repetimos esses deslocamentos até não existir

tal inteiro j. A nova matriz é MC(λ).

Observação 3.3.1 Note que o Passo 1 do processo faz com as colunas de Mλ o equivalente com

o que a definição da aplicação C-shift faz com as partes da composição. As vezes é necessário

o Passo 2, pois quando uma coluna é toda nula e a posterior não, isso quer dizer que há uma

parte nula na composição e a posterior não nula e assim há a necessidade de eliminação dessa

coluna da matriz (respect. parte da partição)

Observação 3.3.2 Com a definição do processo C-shifting, a partir de Mλ obtemos MC(k)(λ),

∀k ∈ Z+ e portanto, obtemos a composição C(k)(λ). Ou seja, sempre que conveniente, ao invés

de trabalharmos com a aplicação C-shift em λ, iremos trabalhar com o processo C-shifting

em Mλ.

Exemplo 3.3.2 Sejam λ = (3, 2, 4) |= 9 e Mλ a sua matriz associada. Pela definição da

aplicação C-shift, sabe-se que C(λ) = (3, 2, 1, 3). Aplicando o processo C-shifting em Mλ obte-

mos:

65


Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 0 · · ·

1 1 1 0 · · ·

1 0 1 0 · · ·

0 0 1 0 · · ·
...

...
...

...
. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo1
−→ M ′

λ = MC(λ) =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 1 1 · · ·

1 1 0 1 · · ·

1 0 0 1 · · ·

0 0 0 0 · · ·
...

...
...

...
. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Exemplo 3.3.3 Para λ = (1, 3) |= 4 temos:

Mλ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 0 · · ·

0 1 0 · · ·

0 1 0 · · ·

0 0 0 · · ·
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo1
−→ M ′

λ =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 0 1 · · ·

1 0 1 · · ·

0 0 0 · · ·

0 0 0 · · ·
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Passo2
−→ MC(λ) =

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 0 · · ·

1 1 0 · · ·

0 0 0 · · ·

0 0 0 · · ·
...

...
...

. . .

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎠

Foi necessário a utilização do Passo 2 pois ao aplicar o Passo 1 a coluna 2 de M ′
λ ficou toda

nula.

Vamos demonstrar o próximo resultado que caracterizaa as composições C-ćıclica.

Teorema 3.3.1 Seja n = 1 + 2 + 3 + . . .+ (k − 1) + r, 1 ≤ r ≤ k, k ∈ Z+.

λ |= n é C-ćıclica se, e somente se, λ tem a forma ćıclica:

(k − 1 + δk−1, k − 2 + δk−2, . . . , 2 + δ2, 1 + δ1, δ0)

onde cada δi é 0 ou 1, i = 0, . . . , k − 1, e

k−1∑
i=0

δi = r.

Demonstração: (⇐) Análoga à demonstração do Teorema 2.4.1(⇐), trocando B-shifting por

C-shifting.
1alinha
−→

2alinha
−→

k−2alinha
−→

k−1alinha
−→

kalinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 δ0 0 · · ·

1 1 · · · 1 δ1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 δk−3 0 0 0 0 · · ·

1 δk−2 0 0 0 0 0 · · ·

δk−1 0 0 0 0 0 0 · · ·

0 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mλ

66


(⇒) No processo C-shifting, notamos que o Passo 1 sempre mantém as entradas da matriz

associada na mesma diagonal, enquanto que no Passo 2 sempre deslocamos algumas entradas da

matriz para diagonais de ı́ndice menor. Assim para qualquer composição C-ćıclica μ, devemos

usar apenas o Passo 1 no processo de obtenção da matriz MC(μ).

Sejam λ |= n uma composição C-ćıclica e Mλ a sua matriz associada. Suponha que λ não

possui a forma ćıclica. Assim para algum w ∈ N∗, há um 0 na w-ésima diagonal e um 1 na

(w+1)-ésima diagonal na matrizMλ, ou seja, DMλ
(w) = (. . . , 0, . . .︸ ︷︷ ︸

w

) eDMλ
(w+1) = (. . . , 1, . . .︸ ︷︷ ︸

w+1

).

Como a série de processos C-shifting de Mλ para MC(λ), para MC(2)(λ) e assim por diante

envolve apenas o Passo 1, em algum momento chegaremos em uma matriz Mθ cuja entradas

(2, w − 1) e (3, w − 1) são iguais a 0.

Assim o processo C-shifting de Mθ para MC(θ) envolve o Passo 2, o que é um absurdo.

walinha
−→

w+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 1 · · ·

1 1 · · · 1 1 0 0 · · ·

1 1 · · · 0 1 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mλ

walinha
−→

w+1alinha
−→

⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 1 · · · 1 1 1 1 · · ·

1 1 · · · 1 0 1 0 · · ·

1 1 · · · 1 0 0 0 · · ·
...

... . .
.

. .
.

. .
. ...

... · · ·

1 1 1 0 0 0 0 · · ·

1 1 0 0 0 0 0 · · ·

1 0 0 0 0 0 0 · · ·
...

...
...

...
...

...
... · · ·

⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

= Mθ

Corolário 3.3.1 Seja n = Tk = 1+2+3+ . . .+ k, k ∈ Z+, então (k, k− 1, . . . , 2, 1) é a única

composição de n que é C-ćıclica.

67


Demonstração: Seja λ |= n uma composição C-ćıclica, assim pelo Teorema 3.3.1 λ = (k− 1+

δk−1, k − 2 + δk−2, . . . , 2 + δ2, 1 + δ1, δ0), onde cada δi é 0 ou 1, i = 0, . . . , k − 1, e

k−1∑
i=0

δi = k.

Logo δi = 1 ∀i, i = 1, . . . , k − 1, e portanto, λ é escrita de maneira única.

Portanto, a caracterização das composições ćıclicas é a mesma das partições ćıclicas.

3.4 Cálculo de DC(n) para números triangulares

Pelos Teoremas 2.4.1 e 3.3.1 temos que λ |= n é C-ćıclica se e somente se λ � n é B-ćıclica.

Portanto, o número de ciclos para a Paciência Carolina é o mesmo que na Paciência Búlgara.

A seguir veremos alguns resultados que envolvem a relação entre Paciência Búlgara e

Paciência Carolina que serão fundamentais para o cálculo d