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?

b) Seguindo a definição de temos que demonstrar que:

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

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

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

c) Agora temos que provar a identidade:

Vamos fazer uma mudança de variável, no somatório.

Lembremos da identidade demonstrada no livro :

Como queríamos demonstrar.

d) Vamos calcular o valor de :

E o