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

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.

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 \]

Vamos provar

\[ 1 + 2 + \cdots + n = \binom{n+1}{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} \]

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.
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} \]

01: Probabilidade e contagem

03: Problema do aniversário, propriedades