Número sequencial combinatório

Na matemática, o número sequencial combinatório (CSN) 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.

Histórico

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:

Determinar o índice (ou posição lexicográfica ou ainda número combinático) de uma dada combinação;
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 & 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[1][2] surgiram com maior ou menor grau de complexidade, para atender outras classes de 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})}^{r}{\left\{{\begin{matrix}{0},&{\mbox{se }}k<i\\{k \choose i},&{\mbox{se }}k\geq i\end{matrix}}\right.}}$

Ou, alternativamente:

$csn={n! \over (r!(n-r)!)}-{\sum _{i=1,k=(n-a_{r-i+1})}^{r}{\left\{{\begin{matrix}{0},&{\mbox{se }}k<i\\{k! \over (i!(k-i)!)},&{\mbox{se }}k\geq i\end{matrix}}\right.}}$

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 algoritmo 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] (edito para salientar que na codificaçao sera k=n-a(r-i) visto o array começar na posiçao zero)
    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

Ver também

Referências gerais

Phillip J. Chase, Algorithm 382: combinations of M out of N objects [G6], Communications of the ACM, v.13 n.6, p. 368, June 1970
LEHMER, D.H. The machine tools of combinatorics. In Applied Combinatorial Mathematics, E.F. Beckenbach, Ed., Wiley, New York, 1964, pp. 5-30.
C. N. Liu , D. T. Tang, Algorithm 452: enumerating combinations of m out of n objects [G6], Communications of the ACM, v.16 n.8, p. 485, Aug. 1973
Charles J. Mifsud, Algorithm 154: combination in lexicographical order, Communications of the ACM, v.6 n.3, p. 103, March 1963
NIJENHUIS, A., AND WILF, H.S. Combinatorial Algorithms. Academic Press, New York, 1975.
PHILLIPS, J.P.N. Permutations of the elements of a vector in lexicographic order. Comput. J. 10, 4 (Oct. 1967), 311.
Henry F. Walter, Algorithm 151: location of a vector in a lexicographically ordered list, Communications of the ACM, v.6 n.2, p. 68, Feb. 1963
M. L. Wolfson , H. V. Wright, Algorithm 160: combinatorial of M things taken N at a time, Communications of the ACM, v.6 n.4, p. 161, April 1963

Número sequencial combinatório

Índice

Histórico

Conversão notação combinatorial para CSN

Ver também

Referências gerais

Ligações externas