Qual a definição básica de composição colorida?

Passo 1

Você perguntou: “Qual a definição básica de composição colorida?”
Informações relevantes dadas no enunciado: pede-se apenas a definição básica (explicação do que é uma composição colorida). Não há outros dados numéricos ou figura.

Passo 2

Primeiro vamos lembrar o que é uma composição (sem cor) de um inteiro, porque a composição colorida é construída em cima disso. Uma composição de um inteiro n é uma sequência ordenada de inteiros positivos cujo somatório é n.
Exemplo: para n=4, algumas composições são (4), (1,3), (2,1,1), (1,1,1,1). Note que a ordem importa: (1,3) é diferente de (3,1).

Passo 3

Agora acrescentamos “cor” às partes. Intuitivamente: em vez de cada parte ser só um número (o tamanho da parte), cada parte também recebe uma cor escolhida entre um conjunto de cores permitido para aquele tamanho. Assim duas composições que têm os mesmos tamanhos, mas cores diferentes em alguma parte, são consideradas diferentes.

Passo 4

Formalizando de maneira simples e precisa: uma composição colorida de n é uma sequência finita de pares
(\ell_1,\gamma_1),(\ell_2,\gamma_2),\dots,(\ell_t,\gamma_t)
onde cada \ell_i é um inteiro positivo (o tamanho da parte), cada \gamma_i é uma “cor” atribuída àquela parte, e
\sum_{i=1}^t \ell_i = n.
Além disso, para cada tamanho k\ge1 existe um certo número a_k (possivelmente zero) de cores disponíveis para partes de tamanho k. Isso significa que, ao escolher uma parte de tamanho k, existem a_k opções de cor para ela.

Passo 5

Explicando por que a definição acima é útil: a sequência de pares preserva a ordem (como em composições) e distingue não só o tamanho das partes mas também a cor atribuída. Se duas sequências diferem em ordem, em tamanho de alguma parte ou na cor de alguma parte, são composições coloridas distintas.

Passo 6

Contagem e ferramenta prática (útil em prova): defina a série geradora
F(x)=\sum_{k\ge1} a_k x^k,
onde a_k é o número de cores disponíveis para partes de tamanho k. Como uma composição colorida é uma sequência (de comprimento arbitrário) de partes coloridas, a série geradora para composições (permitindo comprimento zero) é
\frac{1}{1-F(x)}.
Se quisermos apenas composições não vazias (comprimento \ge1), a série geradora é
\frac{F(x)}{1-F(x)}.
O número de composições coloridas de n é, portanto, o coeficiente de x^n nessa série geradora.

Passo 7

Dois exemplos rápidos para fixar a ideia:
  • Caso básico (nenhuma cor extra): a_k=1 para todo k. Então F(x)=\sum_{k\ge1} x^k=\dfrac{x}{1-x} e o número de composições de n (não coloridas) é 2^{n-1} para n\ge1 — resultado clássico.
  • Caso “cada parte tem r cores, independente do tamanho”: a_k=r para todo k. Então F(x)=r\cdot \dfrac{x}{1-x} e a contagem dá (para n\ge1) o número de composições coloridas igual a
r\,(1+r)^{\,n-1}.
Esses exemplos mostram como usar a definição em provas: identifique a_k, forme F(x), e extraia coeficientes.

Passo 8

Dicas para a prova (prático e motivador): ao ver um problema que fala em “composições coloridas”, imediatamente pergunte-se: para cada possível tamanho de parte, quantas cores há? Isso é o vetor (a_1,a_2,\dots). Em seguida, monte F(x) e use a fórmula da série geométrica para sequências. Se os a_k forem simples (constantes, ou zeros para certos k), frequentemente dá para obter uma fórmula explícita para o coeficiente.

Resposta

Uma composição colorida de n é uma sequência finita de pares (\ell_i,\gamma_i) com \ell_i\in\mathbb{Z}_{>0} e \gamma_i uma cor para a parte \ell_i, tal que \sum_{i=1}^t \ell_i=n; se para cada tamanho k existem a_k cores possíveis, o número de composições coloridas de n é o coeficiente de x^n em \dfrac{F(x)}{1-F(x)}, onde F(x)=\sum_{k\ge1}a_k x^k.

Exercícios relacionados