Número sequencial combinatório

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde outubro de 2013).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

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 \le {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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 \ge 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 \ge 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[editar | editar código-fonte]

Referências gerais[editar | editar código-fonte]

  • 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[editar | editar código-fonte]