Número sequencial combinatório: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 03h06min de 1 de julho de 2006

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 sequencial combinatório) 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}{\{{\begin{matrix}{0},&{\mbox{se }}k<i\\{k \choose i},&{\mbox{se }}k>=i\end{matrix}}}}$

Ou, alternativamente:

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

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

Ver também

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

@@ Linha 20: / Linha 20: @@
 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.
-<math>csn = {n \choose r} - {\sum_{i=1,k=(n-a_{r-i+1}),k>=i}^r {k \choose i}}</math>
+<math>csn = {n \choose r} - {\sum_{i=1,k=(n-a_{r-i+1})}^r {\{ \begin{matrix} {0}, & \mbox{se }k < i \\ {k \choose i}, & \mbox{se }k>=i \end{matrix} }}</math>
 Ou, alternativamente:
-<math>csn = {n! \over (r!(n-r)!)} - {\sum_{i=1,k=(n-a_{r-i+1}),k>=i}^r {k! \over (i!(k-i)!))}}</math>
+<math>csn = {n! \over (r!(n-r)!)} - {\sum_{i=1,k=(n-a_{r-i+1})}^r {\{ \begin{matrix} {0}, & \mbox{se }k < i \\ {k! \over (i!(k-i)!)}, & \mbox{se }k>=i \end{matrix}
+}}</math>
 Onde:
@@ Linha 44: / Linha 45: @@
    CSN = (n!/(r!(n-r)!)) - x
    // ou: CSN = combinação(n, r) - x
 ==Conversão notação CSN para combinatorial==