Enunciado

Considere um torneio com n competidores no qual o resultado é uma ordenação desses competidores, sendo permitidos empates. Isto é, o resultado divide os jogadores em grupos, com o primeiro grupo sendo formado por aqueles que empataram em primeiro lugar, o grupo seguinte sendo formado por aqueles que empataram em segundo lugar, e assim por diante. Faça N(n) representar o número de diferentes resultados possíveis. Por exemplo, N(2) = 3, pois, em um torneio com 2 competidores, o jogador 1 poderia ser unicamente o primeiro, o jogador 2 poderia ser unicamente o primeiro, ou eles poderiam empatar em primeiro.

(a) Liste todos os resultados possíveis quando n = 3.

(b) Com N(0) definido como igual a 1, mostre, sem realizar nenhum cálculo, que

Dica: Existem quantos resultados nos quais i jogadores empatam em último

lugar?

Passo 1

Opa galeeeeera! Hoje vamos descobrir de quantas formas podemos ganhar um torneio.

Vamos tentar formar o número de resultados possíveis para 3 competidores N ( 3 ) :

Podemos ter 3 pessoas empatadas em primeiro lugar, 3 3 = 1 possibilidades. Ou 2 pessoas em primeiro e outra pessoa em segundo lugar, 3 2 1 1 = 3 possibilidades. Ou 1 pessoa em primeiro e 2 em segundo lugar, 3 1 2 2 = 3 possibilidades. Ou 1 pessoa em primeiro e 1 em segundo e 1 em terceiro lugar, 3 1 2 1 1 1 = 6 possibilidades.

Pelo princípio aditivo teremos 1 + 3 + 3 + 6 = 13 diferentes resultados.

Passo 2

b) Seguindo a definição de N 0 = 1 temos que demonstrar que:

N n = ∑ i = 1 n n i N ( n - i )

Podemos pensar que cada uma das classificações há i pessoas em ultima colocação, i ∈   N

Vamos pensar em um i qualquer. Estas i pessoas podem ser escolhidos de n i formas, e sobrarão n - i pessoas que estarão necessariamente a cima deles e cada uma delas pode ser arranjada de N n - i formas, então pelo princípio multiplicativo para um i fixo podemos ter:

n i N n - i

Mas temos que contabilizar para todos os i ’s então pelo princípio aditivo:

N n = ∑ i = 1 n n i N ( n - i )

Passo 3

c) Agora temos que provar a identidade:

N n = ∑ i = 1 n n i N ( n - i ) = n i N ( i )

Vamos fazer uma mudança de variável, k = n - i no somatório.

= ∑ k = 0 n - 1 n n - k N ( k )

Lembremos da identidade demonstrada no livro n n - k = n k :

N n = ∑ k = 0 n - 1 n k N ( k )

Como queríamos demonstrar.

Passo 4

d) Vamos calcular o valor de N 3 :

N 3 = ∑ k = 0 n - 1 n k N k

N 3 = ∑ k = 0 2 2 k N k = 2 0 N 0 + 2 1 N 1 + 2 2 N 2

=   1 ⋅ 1 + 3 ⋅ 1 + 3 ⋅ 3

= 13

E o N 4 :

N 4 = ∑ k = 0 3 3 k N k = 3 0 N 0 + 3 1 N 1 + 3 2 N 2 + 3 3 N 3

=   1 ⋅ 1 + 4 ⋅ 1 + 6 ⋅ 3 + 4 ⋅ 13

= 65

Resposta

Ei, a resposta está no passo a passo :)

Exercícios de Livros Relacionados

De um grupo de n pessoas, suponha que queiramos escolher um comitê de k, k (a) Mantendo o foco primeiro na escolha do comitê e então na escolha do presidente, mostre que há possíveis.(b) Mantendo o fo
Considere a identidade combinatória a seguir: (c) Mostre agora que(n k) k3 = 2^n-3 n2 n+3
A identidade a seguir é conhecida como a identidade combinatória de Fermat.Forneça um argumento combinatório (cálculos não são necessários) para estabelecer essa identidade. Dica: Considere o conjunto
Demonstre que (n+m r)=(n 0)(m r) + (n 1)(m r-1)+ ... + (n r)(m 0)
Considere a identidade combinatória a seguir: (a) Apresente um argumento combinatório para essa identidade considerando um conjunto de n pessoas e determinando, de duas maneiras, o número de possíveis