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\ge 0\}=\{0,1,2,3,\dots \}$. O conjunto dos inteiros positivos é, portanto, $\mathbb{N}\setminus \{0\}$.

Teorema 1. Sejam $n$ e $k$ inteiros positivos. Se ${ℬ}_{n,k}=\{(x_1,\dots ,x_k)\in {\mathbb{N}}^k\mid x_1+x_2+\dots +x_k=n\}$, então o número de elementos de ${ℬ}_{n,k}$ é $|{ℬ}_{n,k}|=(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$.

Teorema 2. Se $\widetilde{{ℬ}_{n,k}}=\{(x_1,\dots ,x_k)\in (\mathbb{N}\setminus \{0\}{)}^k\mid x_1+\dots +x_k=n\}$, então $|\widetilde{{ℬ}_{n,k}}|=(\genfrac{}{}{0ex}{}{n-1}{k-1})$.

Discussão

Primeiro vejamos como os teoremas anteriores são logicamente equivalentes: temos uma bijeção $\widetilde{{ℬ}_{n,k}}\to {ℬ}_{n-k,k}$ dada por $(x_1,\dots ,x_k)\mapsto (x_1-1,x_2-1,\dots ,x_k-1)$.

Para provarmos o Teorema 1, observe como podemos representar os seguintes elementos de ${ℬ}_{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 ${ℬ}_{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,\dots ,n+k-1\}$, temos a bijeção ${ℬ}_{n,k}\to X$ dada por $(x_1,\dots ,x_k)\mapsto (1+x_1,2+x_1+x_2,\dots ,k-1+x_1+x_2+\cdots +x_{k-1})$. A inversa leva $(a_1,a_2,\dots ,a_{k-1})\mapsto (a_1-1,a_2-a_1-1,a_3-a_2-1,\dots ,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 $[\sum _{k=0}^{\mathrm{\infty }}{x}^k{]}^n=\sum _{k=0}^{\mathrm{\infty }}{c}_k{x}^k$. Temos $[\sum _{k=0}^{\mathrm{\infty }}{x}^k{]}^n=\sum _{({\nu }_1,\dots ,{\nu }_n)}{x}^{{\nu }_1+\dots +{\nu }_n}=\sum _{k=0}^{\mathrm{\infty }}(\sum _{{\nu }_1+\dots +{\nu }_n=k}1)x^k$. Mas $\sum _{{\nu }_1+\dots +{\nu }_n=k}1$ é precisamente $|{ℬ}_{k,n}|=(\genfrac{}{}{0ex}{}{k+n-1}{k})$; então $c_k=(\genfrac{}{}{0ex}{}{k+n-1}{k})$. Analogamente, $[\sum _{k=1}^{\mathrm{\infty }}{x}^k{]}^n=\sum _{k=n}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{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 $[\sum _{k=0}^{\mathrm{\infty }}{x}^k{]}^n=1/{(1-x)}^n$, podemos tomar derivadas sucessivas para concluir que $k!c_k=n(n+1)\dots (n+k-1)$, donde $c_k=(\genfrac{}{}{0ex}{}{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 ${\mathrm{Sym}}^r(V)=V^{\otimes r}/E$, onde $E$ é o subespaço gerado por todos os tensores da forma $v_1\otimes \dots \otimes v_i\otimes v_{i+1}\otimes \dots \otimes v_r-v_1\otimes \dots \otimes v_{i+1}\otimes v_i\otimes \dots \otimes v_r$, $i=1,2,\dots ,r-1$. Recebe esse nome porque toda função $r$-linear simétrica fatora-se através de ${\mathrm{Sym}}^r(V)$. Denotando por $v_1{v}_2\dots v_r$ a imagem de $v_1\otimes v_2\otimes \dots \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}\dots v_n^{{\nu }_n}\mid ({\nu }_1,\dots ,{\nu }_n)\in {ℬ}_{r,n}\}$ é base para ${\mathrm{Sym}}^r(V)$ se $\{v_1,\dots ,v_n\}$ é base para o espaço $n$-dimensional $V$. Daí segue imediatamente que ${\dim }_F{\mathrm{Sym}}^r(V)=(\genfrac{}{}{0ex}{}{n+r-1}{r})$.Predefinição:Referências