
Antes de se avançar para qualquer estudo estatístico em totolotarias, é conveniente termos a noção
de qual é a probabilidade de acertarmos com um dado conjunto de números. Só assim é possível
aferir a fiabilidade de um conjunto de filtros, ou uma metodologia de escolha de números e/ou
filtros, por via da sua aplicação ao historial do concurso. É claro para toda a gente que, se uma
dada metodologia tem resultados inferiores ou sensivelmente iguais à probabilidade natural dum
conjunto de números de igual tamanho, essa metodologia está desafinada ou é uma treta (ou ambas).

Por esse motivo, fiz
[este estudo](https://docs.google.com/spreadsheets/d/e/2PACX-1vTW38KgBdXvjXvTSRY4aCY9Aeuy0_gXPK_w5A_YOwdGAr1WgYWbzYka_tkSU9M5TNhNayt74ssanSQ8/pubhtml)
em Novembro de 2006, no fórum euromilhoes.com, para o Euromilhões (números e estrelas) e para o
totoloto. A primeira coluna das tabelas é a quantidade de números escolhida e a primeira fila é a
quantidade de acertos. Nas tabelas onde essa primeira fila é **1**, **2**, **3**, etc., a
probabilidade é calculada para _exactamente_ esses acertos, nem mais, nem menos; Nas tabelas onde
a primeira fila é **1+**, **2+**, **3+**, etc., a probabilidade é calculada para _pelo menos_
esses acertos (1 ou mais, 2 ou mais, etc.).

A probabilidade de se acertar $x$ elementos num total de $n$ de um conjunto de tamanho $N$, em
sorteios de $K$ elementos é calculada recorrendo à fórmula da **distribuição hipergeométrica**.
Qualquer aplicação de folhas de cálculo tem uma expressão directa para o calcular,
**HYPGEOMDIST(x,n,K,N)**. A fórmula completa, usando combinações, é a seguinte:

$$
p_x = \frac{\binom{K}{x}\binom{N - K}{n - x}}{\binom{N}{n}}
$$

A título de exemplo, para o caso do euromilhões, querendo acertar em 5 escolhendo 20, temos que
$x = 5$, $N = 50$, $K = 5$ e $n = 20$:

$$
p_5 = \frac{\binom{5}{5}\binom{50 - 5}{20 - 5}}{\binom{50}{20}}
= \frac{\binom{5}{5}\binom{45}{15}}{\binom{50}{20}}
= 0.0073175 \approx	0.73\%
$$



Uma forma de calcular os CSN, e vice-versa, seria simplesmente construir todo o desdobramento até
ao CSN pretendido, ou até à chave pretendida. _Don’t_. É estúpido, é um desperdício de ciclos de
processamento e é péssima programação. Sobretudo, se já alguém pensou no assunto e se os
algoritmos são do domínio público.

Vamos então aos ditos&hellip;

O algoritmo para calcular a combinação a partir do CSN é um engenhosa obra prima de
**B. P. Buckles** e **M. Lyabanon**, publicada em 1974.

```clike
função csnParaCombinacao(csn, n, k)
    seja limite_inferior = 0;
    seja r = 0;
    seja combinação = [0...k-1]

    para cada i, sendo i = 0, enquanto i < k - 1, incrementar i
        combinação[i] = 0;
        se(i != 0) combinação[i] = combinação[i - 1];

        fazer
            combinação[i] =  combinação[i] + 1;
            // lembram-se desta função?
            r = numeroDeCombinacoes(n - combinação[i], (k - 1) - i);
            limite_inferior = limite_inferior + r;
        enquanto (limite_inferior < csn);

        limite_inferior = limite_inferior - r;
    fim de para;

    combinação[k - 1] = combinação[k - 2] + csn - limite_inferior;

    devolve combinação;
fim de função;
```

Para começar, quero-vos dizer que parece bem mais complicado do que, na realidade, é.

Depois, reparem como a última posição da combinação é tratada à parte, duma maneira perfeitamente
elegante, usando os valores do CSN pedido e do último limite inferior calculado.

Mas passemos, então, à manobra inversa, calcular o CSN a partir da combinação. O seguinte algoritmo
não tem, que eu saiba, autores oficiais. A sua simplicidade decorre de ser um _negativo_ quase
perfeito da função anterior.

```clike
função combinacaoParaCsn(combinação, n)
    seja k = combinação.tamanho();
    seja limite_inferior = 0;
    seja r= 0;

    para cada i, sendo i = 1, enquanto i <= k, incrementar i
        r = n - combinação[k - i];
        se (r >= i)
            limite_inferior = limite_inferior + númeroDeCombinações(r, i);
        fim de se;
    fim de para;

    devolve numeroDeCombinacoes(n, k) - limite_inferior;
fim de função;
```

Podem ver, na segunda instrução do `para`, que a combinação está a ser percorrida de trás para a
frente, e o limite inferior está a ser contado como _o que falta até ao fim_, sendo finalmente
subtraído ao número de combinações total para nos dar o CSN.
