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:

1. Determinar o índice (ou posição lexicográfica ou ainda número combinático) 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 & 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 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] (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

Conversão notação CSN para combinatorial

Demonstra-se abaixo uma fórmula genérica para obtenção da combinação dado um código CSN qualquer.

$Q(x)=\left(\left\{{\begin{matrix}{1},&{\mbox{se }}x\leq 0\\{\prod _{k=1}^{n}{\left(\left\{{\begin{matrix}{(k+1) \over k},&{\mbox{se }}{k \choose {r-x+1}}\leq ({n \choose r}-csn-\left(\left\{{\begin{matrix}{0},&{\mbox{se }}x\leq 1\\{\sum _{i=1}^{x-1}{Q(x-1) \choose (r-i+1)}},&{\mbox{se }}x>1\end{matrix}}\right)\right.)\\{1},&{\mbox{se }}falso\end{matrix}}\right)\right.}},&{\mbox{se }}x>0\end{matrix}}\right)\right.{-1}$

$A(x)=n-Q(x)$

Segue-se abaixo, em notação computacional, o algorítmo equivalente.

 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

Ver também

• Combinação
• Combinatória
• Triângulo de Pascal
• en:Generating function
• en:Combinadic

Referências

• 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

Ligações externas

• Combination sequence number
• Generating the mth Lexicographical Element of a Mathematical Combination
• ACM Algorithm 515 - Fortran Source Code
• Combinatorial Routines