Método bola traço

O método bola traço é na Análise combinatória um dispositivo visual para a facilitação da operação de contagem. Foi popularizado por William Feller e é especialmente útil para a demonstração de vários teoremas combinatórios simples. Pode resolver qualquer problema análogo à "permutar n elementos iguais, entre k compartimentos distintos"

Enunciado dos teoremas

Ao longo deste artigo, $\mathbb {N}$ denotará o conjunto dos inteiros não-negativos, i.e., $\mathbb {N} =\{n\in \mathbb {Z} \mid n\geq 0\}=\{0,1,2,3,\ldots \}$. O conjunto dos inteiros positivos é, portanto, $\mathbb {N} \smallsetminus \{0\}$.

Teorema 1. Sejam $n$ e $k$ inteiros positivos. Se ${\mathcal {B}}_{n,k}=\{(x_{1},\ldots ,x_{k})\in \mathbb {N} ^{k}\mid x_{1}+x_{2}+\ldots +x_{k}=n\}$, então o número de elementos de ${\mathcal {B}}_{n,k}$ é $\vert {\mathcal {B}}_{n,k}\vert ={\binom {n+k-1}{k-1}}$.

Teorema 2. Se ${\widetilde {{\mathcal {B}}_{n,k}}}=\{(x_{1},\ldots ,x_{k})\in (\mathbb {N} \smallsetminus \{0\})^{k}\mid x_{1}+\ldots +x_{k}=n\}$, então $\vert {\widetilde {{\mathcal {B}}_{n,k}}}\vert ={\binom {n-1}{k-1}}$.

Discussão

Primeiro vejamos como os teoremas anteriores são logicamente equivalentes: temos uma bijeção ${\widetilde {{\mathcal {B}}_{n,k}}}\to {{\mathcal {B}}_{n-k,k}}$ dada por $(x_{1},\ldots ,x_{k})\mapsto (x_{1}-1,x_{2}-1,\ldots ,x_{k}-1)$.

Para provarmos o Teorema 1, observe como podemos representar os seguintes elementos de ${\mathcal {B}}_{7,5}$:

O elemento $(4,0,1,2,0)$ será representado por esta configuração.

$(0,3,1,2,1)$

$(1,1,2,1,2)$

Veremos um elemento de ${\mathcal {B}}_{n,k}$ como uma configuração de $n+k-1$ posições ($n$ bolas e $k-1$ traços, ou $n$ estrelas e $k-1$ barras), escolhendo $k-1$ posições para as barras. Precisamente, se $X$ é o conjunto de todas as $(k-1)$-tuplas estritamente crescentes com entradas no conjunto $\{1,2,\ldots ,n+k-1\}$, temos a bijeção ${\mathcal {B}}_{n,k}\to X$ dada por $(x_{1},\ldots ,x_{k})\mapsto (1+x_{1},2+x_{1}+x_{2},\ldots ,k-1+x_{1}+x_{2}+\cdots +x_{k-1})$. A inversa leva $(a_{1},a_{2},\ldots ,a_{k-1})\mapsto (a_{1}-1,a_{2}-a_{1}-1,a_{3}-a_{2}-1,\ldots ,a_{k-1}-a_{k-2}-1,n+k-1-a_{k-1})$. Isso prova o Teorema 1.

Exemplo

Considere a série de potências formal ${\biggl [}\sum _{k=0}^{\infty }x^{k}{\biggr ]}^{n}=\sum _{k=0}^{\infty }c_{k}x^{k}$. Temos ${\biggl [}\sum _{k=0}^{\infty }x^{k}{\biggr ]}^{n}=\sum _{(\nu _{1},\ldots ,\nu _{n})}x^{\nu _{1}+\ldots +\nu _{n}}=\sum _{k=0}^{\infty }{\biggl (}\sum _{\nu _{1}+\ldots +\nu _{n}=k}1{\biggr )}x^{k}$. Mas $\sum _{\nu _{1}+\ldots +\nu _{n}=k}1$ é precisamente $\vert {\mathcal {B}}_{k,n}\vert ={\binom {k+n-1}{k}}$; então $c_{k}={\binom {k+n-1}{k}}$. Analogamente, ${\biggl [}\sum _{k=1}^{\infty }x^{k}{\biggr ]}^{n}=\sum _{k=n}^{\infty }{\binom {k-1}{n-1}}x^{k}$. Essas igualdades valem no sentido analítico para $x\in \,\,]-1,1[$, como consequência do Teorema de Cauchy-Mertens (há convergência absoluta). Com essa igualdade válida para $x\in \,\,]-1,1[$ e usando que ${\biggl [}\sum _{k=0}^{\infty }x^{k}{\biggr ]}^{n}=1/{(1-x)}^{n}$, podemos tomar derivadas sucessivas para concluir que $k!c_{k}=n(n+1)\ldots (n+k-1)$, donde $c_{k}={\binom {n+k-1}{k}}$ ‒ outra prova do Teorema 1.

Potências simétricas de um espaço vetorial

Se $V$ é um espaço vetorial sobre um corpo $F$, a $r$-ésima potência simétrica de $V$ pode ser definida como $\operatorname {Sym} ^{r}(V)=V^{\otimes r}/E$, onde $E$ é o subespaço gerado por todos os tensores da forma $v_{1}\otimes \ldots \otimes v_{i}\otimes v_{i+1}\otimes \ldots \otimes v_{r}-v_{1}\otimes \ldots \otimes v_{i+1}\otimes v_{i}\otimes \ldots \otimes v_{r}$, $i=1,2,\ldots ,r-1$. Recebe esse nome porque toda função $r$-linear simétrica fatora-se através de $\operatorname {Sym} ^{r}(V)$. Denotando por $v_{1}v_{2}\ldots v_{r}$ a imagem de $v_{1}\otimes v_{2}\otimes \ldots \otimes v_{r}$ no quociente e agrupando fatores como o fazemos num produto usual, por meio de potências, vê-se sem muita dificuldade que $\{v_{1}^{\nu _{1}}v_{2}^{\nu _{2}}\ldots v_{n}^{\nu _{n}}\mid (\nu _{1},\ldots ,\nu _{n})\in {\mathcal {B}}_{r,n}\}$ é base para $\operatorname {Sym} ^{r}(V)$ se $\{v_{1},\ldots ,v_{n}\}$ é base para o espaço $n$-dimensional $V$. Daí segue imediatamente que $\dim _{F}\operatorname {Sym} ^{r}(V)={\binom {n+r-1}{r}}$.