Número sequencial combinatório: diferenças entre revisões
m Bot: Adicionando: es:Combinádico |
m Checkwiki (090) + Ajustes |
||
Linha 1: | 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. |
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 < |
<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. |
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ó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. |
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: | Linha 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. |
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== |
== 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. |
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 < |
<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: |
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>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> |
}}</math> |
||
Linha 39: | Linha 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) |
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 |
Se k >= i Então |
||
x = x + k!/(i!(k-i)!) |
x = x + k!/(i!(k-i)!) |
||
// ou: x = x + combinação(k, i) |
// ou: x = x + combinação(k, i) |
||
Fim Se |
Fim Se |
||
Linha 46: | Linha 44: | ||
// ou: CSN = combinação(n, r) - x |
// ou: CSN = combinação(n, r) - x |
||
==Conversão notação CSN para combinatorial== |
== 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. |
Demonstra-se abaixo uma fórmula genérica para obtenção da combinação dado um código CSN qualquer. |
||
<math> |
<math> |
||
Q(x) = \left ( |
Q(x) = \left ( |
||
\left |
\left |
||
\{ \begin{matrix} {1}, & \mbox{se }x \le 0 \\ |
\{ \begin{matrix} {1}, & \mbox{se }x \le 0 \\ |
||
Linha 57: | Linha 54: | ||
\left ( |
\left ( |
||
\left |
\left |
||
\{ \begin{matrix} |
\{ \begin{matrix} |
||
{(k+1) \over k} |
{(k+1) \over k} |
||
, & \mbox{se }{k \choose {r - x + 1}} \le |
, & \mbox{se }{k \choose {r - x + 1}} \le |
||
({n \choose r} - csn - |
({n \choose r} - csn - |
||
\left ( |
\left ( |
||
\left |
\left |
||
\{ \begin{matrix} {0}, & \mbox{se }x \le 1 \\ |
\{ \begin{matrix} {0}, & \mbox{se }x \le 1 \\ |
||
{ |
{ |
||
\sum_{i=1}^{x-1} |
\sum_{i=1}^{x-1} |
||
{ |
{ |
||
{Q(x - 1) \choose (r - i + 1)} |
{Q(x - 1) \choose (r - i + 1)} |
||
} |
} |
||
}, & \mbox{se }x > 1 |
}, & \mbox{se }x > 1 |
||
\end{matrix} |
\end{matrix} |
||
\right ) |
\right ) |
||
Linha 79: | Linha 76: | ||
\right ) |
\right ) |
||
\right . |
\right . |
||
}} , & \mbox{se }x > 0 |
}} , & \mbox{se }x > 0 |
||
\end{matrix} |
\end{matrix} |
||
\right ) |
\right ) |
||
\right . |
\right . |
||
{- 1} |
{- 1} |
||
Linha 115: | Linha 112: | ||
Fim Se |
Fim Se |
||
=={{ |
== {{Ver também}} == |
||
*[[Combinação]] |
* [[Combinação]] |
||
*[[Combinatória]] |
* [[Combinatória]] |
||
*[[Triângulo de Pascal]] |
* [[Triângulo de Pascal]] |
||
*[[:en:Generating function]] |
* [[:en:Generating function]] |
||
*[[:en:Combinadic]] |
* [[:en:Combinadic]] |
||
==Referências== |
== 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 |
* 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. |
* 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 |
* 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 |
* 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. |
* 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. |
* 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 |
* 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 |
* 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}}== |
== {{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 |
{{DEFAULTSORT:Numero Sequencial Combinatorio}} |
||
[[Categoria:Combinatória]] |
[[Categoria:Combinatória]] |
||
Revisão das 12h26min de 6 de setembro de 2009
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.
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 combinático) 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.
Ou, alternativamente:
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.
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
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. 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