02: Histórias e axiomas

Vídeo

Exercícios do livro (cap. 1)

17. Quadrados de combinações

$$\sum_{k = 0}^n \binom{n}{k}^2 = \binom{2n}{n}$$

• Quero escolher $n$ pessoas dentre $2n$ pessoas (lado direito).

• Divido as $2n$ pessoas em dois grupos de $n$ cada.

• Para $k \in \{0, 1, \ldots n\}$:

  • Escolho $k$ pessoas do primeiro grupo — $\binom{n}{k}$ — para entrar.

  • Escolho $k$ pessoas do segundo grupo — $\binom{n}{k}$ — para não entrar.

  • Para este valor de $k$, tenho $\binom{n}{k}^2$ maneiras de selecionar $n$ pessoas, com $k$ pessoas do primeiro grupo e $n-k$ pessoas do segundo.

18. Quadrados de combinações vezes $k$

$$\sum_{k = 1}^n k\binom{n}{k}^2 = n\binom{2n-1}{n-1}$$

• Usamos o mesmo raciocínio do exercício anterior, com uma modificação.

• Temos $2n$ pessoas, divididas em dois grupos de $n$, como antes.

• Como antes, quero escolher $n$ pessoas dentre as $2n$.

• Mas agora, para cada escolha, quero designar uma das $n$ pessoas do primeiro grupo como chefe (i.e., sempre haverá pelo menos uma pessoa do primeiro grupo). Isto corresponde ao fator $n$ no lado direito.

• Escolhido o chefe, preciso escolher $n - 1$ pessoas dentre as $2n - 1$ restantes ($n - 1$ do primeiro grupo, $n$ do segundo). Isto corresponde ao segundo fator do lado direito.

• Do lado esquerdo, para $k \in \{1, 2, \ldots, n \}$:

  • Vou escolher $k$ pessoas do primeiro grupo — $\binom{n}{k}$ — para entrar.

  • Dentre elas, vou escolher um chefe — $k$.

  • Vou escolher $k$ pessoas do segundo grupo — $\binom{n}{k}$ — para não entrar.

19. Produto de combinações

$$\sum_{k=2}^n \binom k2 \binom{n-k+2}{2} = \binom{n+3}{5}, \quad \forall n \geq 2$$

• Um exemplo concreto: $n = 3$

• Queremos escolher $5$ elementos dentre $6$.

• Para $k \in \{ 2, 3 \}$:

  1. Escolhemos sempre o elemento $k + 1$:

     $$\begin{aligned} 1 \quad 2 \quad \underbrace{3}_{k = 2} \quad 4 \quad 5 \quad 6 \\ 1 \quad 2 \quad 3 \quad \underbrace{4}_{k = 3} \quad 5 \quad 6 \end{aligned}$$

     Este é o elemento que vai estar no meio do grupo dos escolhidos.

  2. Escolhemos $2$ dentre os $k$ primeiros elementos:

     $$\begin{aligned} \underbrace{1 \quad 2}_{k = 2} \quad 3 \quad 4 \quad 5 \quad 6 \\ \underbrace{1 \quad 2 \quad 3}_{k = 3} \quad 4 \quad 5 \quad 6 \end{aligned}$$

  3. Escolhemos $2$ dentre os $n - k + 2$ últimos elementos:

     $$\begin{aligned} 1 \quad 2 \quad 3 \quad \underbrace{4 \quad 5 \quad 6}_{k = 2}\\ 1 \quad 2 \quad 3 \quad 4 \quad \underbrace{5 \quad 6}_{k = 3} \end{aligned}$$

20. Teorema das colunas

1. Mostre que

$$\binom{k}{k} + \binom{k + 1}{k} + \binom{k + 2}{k} + \cdots + \binom{n}{k} = \binom{n + 1}{k + 1}$$

• O lado direito significa escolher $k + 1$ pessoas dentre $n + 1$ pessoas.

• O truque é ordenar as pessoas de algum modo.

• Um exemplo concreto, com $n = 4$ e $k = 2$, mostrando que

  $$\binom{5}{3} = \binom{4}{2} + \binom{3}{2} + \binom{2}{2}$$

  1. Vamos chamar as $n + 1$ pessoas de $1, 2, 3, 4, 5$.

  2. Grupos de $k + 1$ pessoas onde o menor número é $1$:

     • $1, 2, 3$
     • $1, 2, 4$
     • $1, 2, 5$
     • $1, 3, 4$
     • $1, 3, 5$
     • $1, 4, 5$

  3. Grupos de $k + 1$ pessoas onde o menor número é $2$:

     • $2, 3, 4$
     • $2, 3, 5$
     • $2, 4, 5$

  4. Grupos de $k + 1$ pessoas onde o menor número é $3$:

     • $3, 4, 5$

• No caso geral, vamos ordenar as $n + 1$ pessoas, rotulando-as como

  $$a_0, a_1, a_2, \dots, a_n$$

• Como a ordem dentro de cada grupo não importa, vamos escolher primeiro um elemento para ser o de menor índice do grupo e escolher os restantes $k$ elementos dentre os elementos de índice maior do que o primeiro.

• Se escolhermos $a_0$ como o de menor índice, temos $\binom{n}{k}$ modos de escolher os restantes.

• Se escolhermos $a_1$ como o de menor índice, temos $\binom{n - 1}{k}$ modos de escolher os restantes.

• $\dots$

• Se escolhermos $a_{n - (k+1)}$ como o de menor índice, temos $\binom{k + 1}{k}$ modos de escolher os restantes.

• Se escolhermos $a_{n - k}$ como o de menor índice, temos $\binom{k}{k}$ modos de escolher os restantes.

2. Suppose that a large pack of Haribo gummi bears can have anywhere between $30$ and $50$ gummi bears. There are $5$ delicious flavors. How many possibilities are there for the composition of such a pack of gummi bears?

• Usando a notação de OLIVEIRA MORGADO et al³, onde $\text{CR}_k^n$ é o número de combinações completas de $n$ elementos de $k$ tipos diferentes, a resposta é

  $$\begin{aligned} \text{CR}_5^{30} + \text{CR}_5^{31} + \cdots + \text{CR}_5^{50} &= \binom{34}{4} + \binom{35}{4} + \cdots + \binom{54}{4} \\ &= \binom{55}{5} - \left[ \binom{33}{4} + \binom{32}{4} + \cdots + \binom{4}{4} \right] \\ &= \binom{55}{5} - \binom{34}{5} \end{aligned}$$

22. Soma de cubos

Para provar

$$1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$$

1. Vamos provar

   $$1 + 2 + \cdots + n = \binom{n+1}{2}$$

2. E vamos provar

   $$1^3 + 2^3 + \cdots + n^3 = 6\binom{n+1}{4} + 6\binom{n+1}{3} + \binom{n+1}{2}$$

1. Considere $n + 1$ times, numerados de $0$ a $n$, num campeonato onde cada time joga com todos os outros exatamente uma vez. O total de jogos será

   $$\binom{n+1}{2}$$

   • O time $0$ joga com $n$ times com número maior que ele.

   • O time $1$ joga com $n - 1$ times com número maior que ele.

   • O time $2$ joga com $n - 2$ times com número maior que ele.

   • …

   • O time $n-2$ joga com $2$ times com número maior que ele.

   • O time $n-1$ joga com $1$ time com número maior que ele.

   • O time $n$ joga com $0$ times com número maior que ele.

2. Hint: Imagine choosing a number between $1$ and $n$ and then choosing $3$ numbers between $0$ and $n$ smaller than the original number, with replacement. Then consider cases based on how many distinct numbers were chosen.

   • Vamos chamar o número escolhido de $k$.

   • Para $k = 1$, só temos o $0$ para escolher. É $1$ possibilidade.

   • Para $k = 2$, temos $2$ números. São $2^3$ possibilidades.

   • Para $k = 3$, temos $3$ números. São $3^3$ possibilidades.

   • No geral, para $k = n$, são $n^3$ possibilidades.

   • A soma de todos os casos é a soma dos cubos.

   • Vamos examinar o caso em que $k$ foi o número escolhido. De quantas maneiras podemos escolher $3$ números entre $0$ e $k-1$, com reposição?

     • Com $1$ número, basta escolher o número: $\binom{k}{1}$ possibilidades.

     • Com $2$ números distintos:

       • Escolhemos os $2$ números: $\binom{k}{2}$ possibilidades;

       • Escolhemos qual dos $2$ aparecerá $2$ vezes: $2$ possibilidades;

       • Escolhemos a posição do número que aparece uma vez: $3$ possibilidades.

       • São $6 \binom{k}{2}$ possibilidades.

     • Com $3$ números distintos:

       • Escolhemos os $3$ números: $\binom{k}{3}$ possibilidades;

       • Escolhemos a ordem dos $3$ números: $6$ possibilidades;

       • São $6 \binom{k}{3}$ possibilidades.

   • Para todos os valores de $k$, o total de possibilidades é

     $$\sum_{k = 1}^n \left[ \binom{k}{1} + 6\binom{k}{2} + 6\binom{k}{3}\right]$$

   • Usando o teorema das colunas, chegamos ao resultado

     $$\binom{n + 1}{2} + 6\binom{n + 1}{3} + 6\binom{n + 1}{4}$$