Retirar palitos

O Nim é um jogo geralmente jogado em duplas. As jogadas são feitas alternadamente, e cada jogador deve retirar no mínimo um palito ou no máximo todos os palitos de uma mesma fileira, mas não pode retirar palitos de fileiras diferentes. O perdedor é aquele que retirar o último palito da mesa. A figura a seguir mostra as filas montadas por dois jogadores como preparação para o jogo:

Fila 1:     l    
Fila 2:     l l l
Fila 3:     l l l l l
Fila 4:     l l l l l l l
Fila 5:     l l l l l l l l l

Iniciando o jogo, o primeiro jogador decidiu retirar palitos da Fila 5

De quantas maneiras distintas esse jogador pode retirar palitos dessa fila?

A) 9
B) 8!
C) 9!
D) 2^9
E) (2^9) - 1

Gabarito: E

A resolução se dá por meio da formação de subconjuntos com dois elementos a partir de um conjunto com 9 elementos, mas não consegui compreender direito, pois todos os elementos desse conjunto seriam iguais (Palito 1 = Palito 5). Alguém saberia explicar de uma forma mais didática?

Valeu pessoal

Pode retirar 1 palito, 2 palitos, 3 palitos,... , 9 palitos:

x = C(9, 1) + C(9, 2) + C(9, 3) + ... + C(9, 9)

Acontece que C(n, 0) + C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, n) = 2ⁿ = (1 + 1)ⁿ

C(n, 0) + x = 2ⁿ ---> 1 + x = 2ⁿ ---> x = 2ⁿ - 1

Elcioschin escreveu:Pode retirar 1 palito, 2 palitos, 3 palitos,... , 9 palitos:

x = C(9, 1) + C(9, 2) + C(9, 3) + ... + C(9, 9)

Acontece que C(n, 0) + C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, n) = 2ⁿ = (1 + 1)ⁿ

C(n, 0) + x = 2ⁿ ---> 1 + x = 2ⁿ ---> x = 2ⁿ - 1

Muito obrigado mestre, por combinação ficou bem claro. Interessante que essa série converge pra 2^n, não sabia. 

Isto é uma consequência do Binômio de Newton

N = (x + y)ⁿ 

Para x = y = 1 ---> N = (1 + 1)ⁿ ---> N = 2ⁿ