Diferenças entre edições de "Número sequencial combinatório"

103 bytes adicionados ,  12h26min de 6 de setembro de 2009
m
Checkwiki (090) + Ajustes
m (Bot: Adicionando: es:Combinádico)
m (Checkwiki (090) + Ajustes)
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.
 
<math>0 < csn \le {n \choose r} \;</math>
 
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.
 
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 [http://portal.acm.org/citation.cfm?id=355739&coll=portal&dl=ACM ACM #515]). Depois disso, diversos outros algoritmos[http://www.saliu.com/bbs/messages/348.htm][http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/mth_lexicograp.asp ] 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.
 
<math>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 . }}</math>
 
Ou, alternativamente:
 
<math>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 .
}}</math>
 
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
// 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.
 
<math>
Q(x) = \left (
\left
\{ \begin{matrix} {1}, & \mbox{se }x \le 0 \\
\left (
\left
\{ \begin{matrix}
{(k+1) \over k}
, & \mbox{se }{k \choose {r - x + 1}} \le
({n \choose r} - csn -
\left (
\left
\{ \begin{matrix} {0}, & \mbox{se }x \le 1 \\
{
\sum_{i=1}^{x-1}
{
{Q(x - 1) \choose (r - i + 1)}
}
}, & \mbox{se }x > 1
\end{matrix}
\right )
\right )
\right .
}} , & \mbox{se }x > 0
\end{matrix}
\right )
\right .
{- 1}
Fim Se
 
== {{VejaVer também}} ==
* [[Combinação]]
* [[Combinatória]]
* [[Triângulo de Pascal]]
* [[:en:Generating function]]
* [[:en:Combinadic]]
 
== 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.&nbsp;368, June 1970
* LEHMER, D.H. The machine tools of combinatorics. In Applied Combinatorial Mathematics, E.F. Beckenbach, Ed., Wiley, New York, 1964, pp. &nbsp;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.&nbsp;485, Aug. 1973
* Charles J. Mifsud, Algorithm 154: combination in lexicographical order, Communications of the ACM, v.6 n.3, p.&nbsp;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.&nbsp;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.&nbsp;161, April 1963
 
== {{Ligações externas}} ==
*[ {{Link||2=http://www.saliu.com/bbs/messages/348.html |3=Combination sequence number]}}
*[ {{Link||2=http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/mth_lexicograp.asp |3=Generating the mth Lexicographical Element of a Mathematical Combination] }}
*[ {{Link||2=http://ftp.cac.psu.edu/pub/ger/fortran/hdk/combenum.for |3=ACM Algorithm 515 - Fortran Source Code]}}
*[ {{Link||2=http://www.scs.fsu.edu/~burkardt/cpp_src/subset/subset.html |3=Combinatorial Routines]}}
 
{{DEFAULTSORT:Numero sequencialSequencial combinatorioCombinatorio}}
[[Categoria:Combinatória]]
 
94 507

edições