Número sequencial combinatório

Históricamente a matemática sempre teve grande interesse em "combinações". As loterias e demais jogos de azar baseiam-se fortemente em análise combinatorial e probabilidade em seu funcionamento.

Nesse contexto, existem dois problemas recorrentes quando se trata desse ramo da matemática:

1. Determinar o índice (ou posição lexicográfica ou ainda número sequencial combinatório-CSN) de uma dada combinação;
2. Construir uma combinação dado um determinado índice CSN.

A primeira tentativa de solucionar esses problemas foi feita em 1974. Nesse ano, B.P. Buckles and M. Lybanon criaram um programa de computador que construía combinações simples dado um índice conhecido (algoritmo “ACM #515”). Depois disso, diversos outros algoritmos surgiram com maior ou menor grau de complexidade, para atender outras classes de combinações.

Definição

O índice CSN (Combination Sequential Number) de uma dada combinação refere-se a posição desta no universo de combinações possíveis de um subconjunto de tamanho r em um conjunto n estabelecido.

$0<csn\leq {n \choose r}\;$

Assim, por exemplo, em um jogo de 49/6 combinações (n/r), a combinação 6-7-16-20-28-47 equivale ao índice 6991908 (exatamente o ponto central do número total de combinações). A mesma combinação tem o índice 45148858 em um jogo de 69/6 combinações.

Conversão notação combinatorial para CSN

Demonstra-se abaixo uma fórmula genérica para cálculo do código CSN a partir de um dado vetor de elementos a previamente classificados em ordem crescente.

$csn={n \choose r}-{\sum _{i=1,k=(n-a_{r-i+1}),k>=i}^{r}{k \choose i}}$

Ou, alternativamente:

$csn={n! \over (r!(n-r)!)}-{\sum _{i=1,k=(n-a_{r-i+1}),k>=i}^{r}{k! \over (i!(k-i)!))}}$

Onde:

  n = número de elementos a serem combinados
  r = números por combinação
  a = vetor com a combinação desejada (a[1]=primeiro elemento)

Em notação computacional pode-se usar o seguinte algorítmo para realizar a conversão da notação combinatorial para o código CSN:

  x = 0
  Para i de 1 até r faça
    k = n - a[r-i+1]
    Se k >= i Então
       x = x + k!/(i!(k-i)!)  
       // ou: x = x + combinação(k, i)
    Fim Se
  Fim Para
  CSN = (n!/(r!(n-r)!)) - x
  // ou: CSN = combinação(n, r) - x

Conversão notação CSN para combinatorial

Demonstra-se abaixo o algorítmo para obtenção da combinação dado um código CSN qualquer.

 n = número de elementos a serem combinados
 r = números por combinação
 a = vetor para receber a combinação (a[1]=primeiro elemento)
 csn = código CSN de entrada

 csn = combinação(n, r) - csn
 k = n + 1
 Para i de r até 1 faça
    Repita
       k = k - 1
       Se k >= i Então
          x = combinação(k, i)
       Senão
          x = 0
       Fim Se
    Até x <= csn
    csn = csn - x
    a[r-i+1] = n - k
 Fim Para
 Se csn >= 0 Então
    a[r] = a[r] - csn
 Fim Se