Combinações de dígitos

Encontrar todas as combinações dentro de um conjunto é tão fácil como contar em binário. Digamos que eu tenha um conjunto de quatro itens; se eu contar até 15 (4 bits), vou ter 0000, 0001, 0010, 0011, etc.

Eu decidi que um bit 1 indica que o item está no subconjunto e que 0 indica que não está. Então, se o meu conjunto for (A, B, C, D), 0000 vai representar o conjunto vazio, 0001 vai representar (D), 0010 vai representar (C) e assim por diante. O último subconjunto é o próprio conjunto, representado por 1111.

O fato de que eu preciso contar até 2ⁿ-1 me lembrou do triângulo de Pascal. A soma dos números de cada linha do triângulo é 2ⁿ e isso me fez perceber que os números, individualmente, devem representar alguma coisa também.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

Como cada número do triângulo representa a quantidade de subconjuntos com uma certa quantidade de itens, eles têm que representar também a quantidade de números que têm um determinado número de dígitos 1.

Por exemplo, a quarta linha é "1 3 3 1" e equivale a um número de 3 bits. Com 3 bits, podemos representar os seguintes números:

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

Temos, então, 1 número só de zeros, 3 com apenas 1 dígito 1, 3 com 2 dígitos 1 e apenas 1 com 3 dígitos 1.

Alternativamente, se eu quiser saber quantos números de 1 byte possuem 3 dígitos 1, posso rapidamente descobrir no triângulo que são 56.

Certamente, esconde-se aí alguma verdade capaz de trazer fama, dinheiro e mulheres.