{"id":22012,"date":"2016-11-07T22:52:56","date_gmt":"2016-11-08T03:52:56","guid":{"rendered":"http:\/\/blog.espol.edu.ec\/estg1003\/?p=215"},"modified":"2026-04-04T10:47:52","modified_gmt":"2026-04-04T15:47:52","slug":"combinatorias","status":"publish","type":"post","link":"https:\/\/blog.espol.edu.ec\/algoritmos101\/stp-unidades\/stp-u01eva\/combinatorias\/","title":{"rendered":"7. Combinatorias en Python"},"content":{"rendered":"\n

Referencia<\/strong>: Le\u00f3n-Garc\u00eda p.42, Gubner p.35, Ross p.10<\/p>\n\n\n\n

Combinatorias es el estudio de m\u00e9todos sistem\u00e1ticos de conteo, las cuatro clases de problemas principales son:<\/p>\n\n\n\n

    \n
  1. Muestreo ordenado con reemplazo<\/a><\/li>\n\n\n\n
  2. Muestreo ordenado sin reemplazo<\/a><\/li>\n\n\n\n
  3. Muestreo no ordenado sin reemplazo<\/a><\/li>\n\n\n\n
  4. Muestreo no ordenado con reemplazo<\/a><\/li>\n<\/ol>\n\n\n\n
    \n\n\n\n

    1. Muestreo ordenado con reemplazo<\/h2>\n\n\n\n

    Se llaman variaciones con repetici\u00f3n de m elementos tomados de n en n, a los diferentes grupos que pueden formarse con los m elementos dados, tomados de n en n.
    Dos grupos pueden ser distintos entre si, si tienen diferentes elementos en diferente orden.<\/p>\n\n\n\n

    El n\u00famero de posibles k-tuplas en distinto orden (x1<\/sub>x2<\/sub>x3<\/sub>... xk<\/sub>) con elementos xi<\/sub> de un grupo de ni<\/sub> elementos diferentes es:<\/p>\n\n\n\n

    n\u00famero de k-tuplas en orden distinto = n1<\/sub>n2<\/sub>n3<\/sub>... nk<\/sub><\/p>\n\n\n\n

    1.1 Ejemplo : Posibles rutas para un paquete de internet<\/h3>\n\n\n\n

    Referencia<\/strong>: Le\u00f3n-Garc\u00eda E2.15 p.42.<\/p>\n\n\n\n

    Una urna tiene cinco pelotas numeradas de 1 al 5. Suponga que se sacan dos pelotas de la urna con reemplazo.<\/p>\n\n\n\n

    - \u00bfCu\u00e1ntos pares diferentes de se pueden obtener?<\/p>\n\n\n\n

    pares diferentes = 5 * 5 = 52<\/sup> = 25 pares diferentes<\/p>\n\n\n\n

    - \u00bfCu\u00e1l es la probabilidad que en se repitan las pelotas?<\/p>\n\n\n\n

    las formas de repetir son (1,1),(2,2),(3,3),(4,4) y (5,5), en total 5 de un total de 25 pares diferentes, por lo que la probabilidad ser\u00e1 5\/25 = 1\/5 = 0.20<\/p>\n\n\n\n

    \n\n\n\n

    2. Muestreo ordenado sin reemplazo<\/h2>\n\n\n\n

    Se seleccionan k elementos en sucesi\u00f3n sin reemplazo de una poblaci\u00f3n A de n elementos diferentes. Con k\u2264n, la primera vez se pueden escoger n1<\/sub>=n elementos diferentes, la segunda n2<\/sub>=n-1, la tercera n3<\/sub>=n-2, ... en la \u00faltima nk<\/sub>=n-(k-1)<\/p>\n\n\n\n

    n\u00famero de k-tuplas en orden distinto = n(n-1)(n-2)...(n-k+1)<\/p>\n\n\n n(n-1)(n-2)...(n-k+1) = \\frac{n!}{(n-k)!} <\/span>\n\n\n\n

    2.1 Ejemplo - Urna con 5 pelotas<\/h3>\n\n\n\n

    Referencia<\/strong>: Le\u00f3n-Garc\u00eda E2.17 p.43.<\/p>\n\n\n\n

    Una urna tiene cinco pelotas numeradas de 1 al 5. Suponga que se sacan tres pelotas sin reemplazo .<\/p>\n\n\n\n

    - \u00bfCu\u00e1ntos tripletas diferentes de se pueden obtener?<\/p>\n\n\n\n

    tripletas diferentes = 5 * 4 * 3 = 60 formas diferentes<\/p>\n\n\n\n

    (5!)\/(5-3)! = 5!\/2! = 5*4*3*(2!)\/2! =5*4*3 = 60 formas diferentes<\/p>\n\n\n\n

    import<\/span> scipy.special as<\/span> sts\nsts.perm(5,3)<\/code><\/pre>\n\n\n\n
    60.0<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    3. Muestreo no ordenado sin reemplazo<\/h2>\n\n\n\n
    Se sacan k elementos de un grupo A de n objetos diferentes sin reemplazo, y que se escriben los resultados sin importar e orden. Ser\u00eda como colocarlos en otro conjunto B, el orden deja de importar.<\/p>\n\n\n\n
    En el nuevo conjunto B, existen k! formas ordenadas de seleccionar los objetos, y Ck<\/sub>n<\/sup> ser\u00e1 el valor buscado de las combinaciones de tama\u00f1o k del conjunto A de n elementos.<\/p>\n\n\n C_k^n k! = n(n-1)(n-2)...(n-k+1) = <\/span>\n\n\n = \\frac{n!}{(n-k)!} <\/span>\n\n\n\n
    que simplificando se convierte el \"coeficiente binomial\" y se lee \"de n toma k elementos\":<\/p>\n\n\n C_k^n = \\frac{1}{n!} \\frac{k!}{(n-k)!} = \\left( \\begin{array}{c} n \\\\ k \\end{array} \\right) <\/span>\n\n\n\n
    da lo mismo escoger k elementos del conjunto A, que dejar n-k elementos en el conjunto, por lo que:<\/p>\n\n\n \\left( \\begin{array}{c} n \\\\ k \\end{array} \\right) =\\left( \\begin{array}{c} n \\\\ n-k \\end{array} \\right) <\/span>\n\n\n\n
     3.1 Ejemplo - sorteo de jueces<\/h3>\n\n\n\n
    Referencia<\/strong>: Gubner E 1.38 p.38.<\/p>\n\n\n\n
    Se requiere conformar un jurado de 12 personas seleccionados de un total de 20 jueces. \u00bfCu\u00e1ntas formas posibles existen para conformar el jurado?. No importa el orden.<\/p>\n\n\n \\left( \\begin{array}{c} 20 \\\\ 12 \\end{array} \\right) = \\frac{20!}{12!8!} = 125970 <\/span>\n\n\n\n
    import<\/span> scipy.special as<\/span> sts\n\nsts.comb(20,12,repetition=False)<\/code><\/pre>\n\n\n\n
    125970.0<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    4. Muestreo no ordenado con reemplazo<\/h2>\n\n\n\n
    Se toman k objetos de un grupo de n objetos diferentes con reemplazo, se escribe el resultado sin importar el orden.<\/p>\n\n\n \\left( \\begin{array}{c} n-1+k \\\\ k \\end{array} \\right) = \\left( \\begin{array}{c} n-1+k \\\\ n-1 \\end{array} \\right) <\/span>\n\n\n\n
    4.1 Ejemplo : Dispensadora de frutas<\/h3>\n\n\n\n
    Referencia: Gubner Ej 1.38<\/p>\n\n\n\n
    En una maquina dispensadora autom\u00e1tica se entregan manzanas, bananas y peras. Por un precio fijo, se pueden obtener cinco frutas seleccionadas por el cliente.<\/p>\n\n\n\n
    El proceso se maneja electr\u00f3nicamente con una secuencia de 7 bits que los ceros (0) representan las manzanas, bananas y peras en orden y se separan por un bit uno (1) como en el ejemplo:<\/p>\n\n\n\n
    0100100 son un manzana, dos bananas y dos peras.<\/p>\n\n\n\n
    El primer grupo de 0\u2019s es manzanas, el segundo grupo de 0\u2019s son bananas y el grupo final de 0\u2019s son peras.
    \u00bfCu\u00e1ntas opciones tienen los clientes?<\/p>\n\n\n\n
    Soluci\u00f3n: Equivale a preguntar cu\u00e1ntas secuencias de 7 bits hay con cinco ceros y dos unos.<\/p>\n\n\n \\left( \\begin{array}{c} 7 \\\\ 5,2 \\end{array} \\right) = \\left( \\begin{array}{c} 7 \\\\ 5 \\end{array} \\right) =\\left( \\begin{array}{c} 7 \\\\ 2 \\end{array} \\right) <\/span>\n\n\n\n
    import<\/span> scipy.special as<\/span> sts\n\nc1 = sts.comb(7,2)\nc2 = sts.comb(7,5)\n\nprint(c1)\nprint(c2)<\/code><\/pre>\n\n\n\n
    21.0\n21.0<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    Referencia: Le\u00f3n-Garc\u00eda p.42, Gubner p.35, Ross p.10 Combinatorias es el estudio de m\u00e9todos sistem\u00e1ticos de conteo, las cuatro clases de problemas principales son: 1. Muestreo ordenado con reemplazo Se llaman variaciones con repetici\u00f3n de m elementos tomados de n en n, a los diferentes grupos que pueden formarse con los m elementos dados, tomados de […]<\/p>\n","protected":false},"author":8043,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"wp-custom-template-entrada-stp-unidades","format":"standard","meta":{"footnotes":""},"categories":[213],"tags":[],"class_list":["post-22012","post","type-post","status-publish","format-standard","hentry","category-stp-u01eva"],"_links":{"self":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts\/22012","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/users\/8043"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/comments?post=22012"}],"version-history":[{"count":3,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts\/22012\/revisions"}],"predecessor-version":[{"id":22334,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/posts\/22012\/revisions\/22334"}],"wp:attachment":[{"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/media?parent=22012"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/categories?post=22012"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/algoritmos101\/wp-json\/wp\/v2\/tags?post=22012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}