Número sequencial combinatório: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: es:Combinádico |
m Checkwiki (090) + Ajustes |
||
Linha 1:
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 <
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.
Linha 16 ⟶ 15:
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 <
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>
Linha 39 ⟶ 37:
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
Linha 46 ⟶ 44:
// 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 \\
Linha 57 ⟶ 54:
\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 )
Linha 79 ⟶ 76:
\right )
\right .
}} , & \mbox{se }x > 0
\end{matrix}
\right )
\right .
{- 1}
Linha 115 ⟶ 112:
Fim Se
== {{
* [[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. 368, June 1970
* LEHMER, D.H. The machine tools of combinatorics. In Applied Combinatorial Mathematics, E.F. Beckenbach, Ed., Wiley, New York, 1964, pp.
* 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}} ==
*
*
*
*
{{DEFAULTSORT:Numero
[[Categoria:Combinatória]]
| |||