Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 226 vistas

    Maco U2 Ea Lapb

    Cargado por

    Laura Pontón Becerril
    Este documento presenta 5 problemas de análisis combinatorio y sus soluciones. En el primer problema, se encuentra el número de enteros positivos menores a 1,000,000 cuya suma de dígitos es 31. En el segundo, se encuentra la función generatriz para una ecuación con restricciones en los términos. En el tercero, se determinan las funciones generatrizas de dos sucesiones dadas. En el cuarto, se calcula el coeficiente de un término en dos expresiones. Finalmente, en el quinto problema, se cuenta el número de

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Maco U2 Ea Lapb

    Cargado por

    Laura Pontón Becerril
    226 vistas10 páginas
    Este documento presenta 5 problemas de análisis combinatorio y sus soluciones. En el primer problema, se encuentra el número de enteros positivos menores a 1,000,000 cuya suma de dígitos es 31. En el segundo, se encuentra la función generatriz para una ecuación con restricciones en los términos. En el tercero, se determinan las funciones generatrizas de dos sucesiones dadas. En el cuarto, se calcula el coeficiente de un término en dos expresiones. Finalmente, en el quinto problema, se cuenta el número de

    Descripción original:

    Aplicando técnicas más avanzadas de conteo Análisis Combinatorio

    Título original

    MACO_U2_EA_LAPB

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta 5 problemas de análisis combinatorio y sus soluciones. En el primer problema, se encuentra el número de enteros positivos menores a 1,000,000 cuya suma de dígitos es 31. En el segundo, se encuentra la función generatriz para una ecuación con restricciones en los términos. En el tercero, se determinan las funciones generatrizas de dos sucesiones dadas. En el cuarto, se calcula el coeficiente de un término en dos expresiones. Finalmente, en el quinto problema, se cuenta el número de

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    226 vistas10 páginas

    Maco U2 Ea Lapb

    Cargado por

    Laura Pontón Becerril
    Este documento presenta 5 problemas de análisis combinatorio y sus soluciones. En el primer problema, se encuentra el número de enteros positivos menores a 1,000,000 cuya suma de dígitos es 31. En el segundo, se encuentra la función generatriz para una ecuación con restricciones en los términos. En el tercero, se determinan las funciones generatrizas de dos sucesiones dadas. En el cuarto, se calcula el coeficiente de un término en dos expresiones. Finalmente, en el quinto problema, se cuenta el número de

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 10

    Anlisis Combinatorio

    Unidad 1 Evidencia de Aprendizaje

    APLICANDO TCNICAS MS AVANZADAS DE CONTEO


    22 de agosto de 2015
    Autor: Laura Pontn Becerril

    Anlisis Combinatorio
    Unidad 1 Evidencia de Aprendizaje
    1. Encuentra el nmero de enteros positivos menores que 1,000,000 tales
    que la suma de sus dgitos sea 31.
    En el caso que se requiera la suma de dgitos sea igual a 31, entonces se debe de
    preguntar el nmero de soluciones del polinomio a usar.
    El polinomio que vamos a usar es:
    1 + 2 + 3 + 4 + 5 + 6 = 31
    Como los dgitos a usar son: 0,1,2,3,4,5,6,7,8,9 que son 10 elementos, entonces:
    0 9
    Ignorando restricciones:
    La cantidad de combinaciones, que son soluciones, de los 6 dgitos es:
    (

    31 + 6 1
    ) = 376992
    31

    Entonces, las restricciones son:


    Para:
    0 9
    Para los que exceden 9, o sea > 10
    ( ) = (

    21 + 6 1
    ) = 65780
    21

    Anlisis Combinatorio | 22/08/2015

    Y el nmero de ( ): 6C1=6

    Si vuelven a exceder 9, o sea > 10


    11 + 6 1
    ) = 4368
    11

    ( ) = (
    Y el nmero de ( ): 6C2=15
    Si vuelven a exceder 9, o sea > 10

    ( ) = (

    1+61
    )=6
    1

    Y el nmero de ( ): 6C3=20
    Si vuelven a exceder 9, o sea > 10 no aplican a soluciones positivas, nmeros
    naturales.
    Aplicando el principio de inclusin-exclusin:
    || = (1 2 3 )
    || = 376992 6(65780) + 15(4368) 20(6) =
    || = 47712
    Solucin:
    El nmero de enteros positivos menores que 1,000,000 tales que la suma de sus
    dgitos sea 31 son 47712
    2. Encuentra la funcin generatriz y el coeficiente en ella que da el nmero
    de soluciones enteras de la ecuacin:
    + + + =

    Se sospecha un error en la redaccin:
    Suponiendo que el enunciado sea:
    0 7 , 1 4 4
    Para: 0 7:
    (1 + 1 + 2 + 3 + 4 + 5 + 6 + 7 )4
    Para: 1 4:
    (1 + 2 + 3 + 4 )4
    Para: 4 :
    (1 + 2 + 4 + 6 + 8 + + 18 + 20 )
    Entonces el resultado es:
    () = (1 + 1 + 2 + 3 + 4 + 5 + 6 + 7 )4 (1 + 2 + 3 + 4 )4 (1 + 2 + 4 + 6
    + 8 + + 18 + 20 )

    0 7 1 4 4

    Para: 0 7:
    (1 + 1 + 2 + 3 + 4 + 5 + 6 + 7 )4
    Para: 4 :
    (1 + 2 + 4 + 6 + 8 + + 18 + 20 )

    Anlisis Combinatorio | 22/08/2015

    En el caso que la redaccin del problema sea:

    Entonces el resultado es:


    () = (1 + 1 + 2 + 3 + 4 + 5 + 6 + 7 )4 (1 + 2 + 4 + 6 + 8 + + 18 + 20 )

    El coeficiente en ella que da el nmero de soluciones enteras de la ecuacin es 20


    3. Encuentra las funciones generatrices correspondientes a las siguientes
    sucesiones:
    a. (), (), (), , ()
    Observacin: (19) empieza de 1, y son 9 elementos en la sucesin finita, lo que conlleva a un
    polinomio de grado 8. Si fuera polinomio de grado 9, entonces seran 10 elementos en la
    sucesin finita.
    Los coeficientes son:
    1(9), 2(36), 3(84), 4(126), 5(126), 6(84), 7(36), 8(9), 9(1)
    Efectuando:
    9,72,252,504,630,504,252,72,9
    Factorizando 9:
    9(1,8,28,56,70,56,28,8,1)
    Podemos hacer la siguiente relacin:
    Sea:
    9

    9
    () = ( )

    =0

    Buscamos su derivada:
    9

    9
    () = ( ) 1

    Anlisis Combinatorio | 22/08/2015

    =0

    Dado que () es la funcin generatriz, entonces:


    () = (1 + )9
    Y la funcin () es la funcin generadora de las sucesiones, entonces:
    () = 9(1 + )8
    Comprobando:
    9 + 72 + 252 2 + 504 3 + 630 4 + +504 5 + 252 6 + 72 7 + 9 8
    Ahora:
    (1 + )8 = +8 + 28 2 + 56 3 + 70 4 + 56 5 + 28 2 + 8 + 1
    Entonces:
    9(1 + 8 + 28 2 + 56 3 + 70 4 + 56 5 + 28 2 + 8 + 1) = 9(1 + )8
    Que es igual a:
    + + + + + + + +
    Donde los coeficientes, son la sucesin dada.

    b. 0,0,0,0,1,0,1,0,1,0,1,0,1,
    El polinomio generador es:
    4 (1 + 2 + 4 + 6 + )
    Donde:
    Para: 1, 0, 1, 0, 1, 0,1 el polinomio generador es (1 + 2 + 4 + 6 + ) y la funcin
    generadora es:
    1
    1 2
    Y para 0, 0, 0, 0 el polinomio generador es 4 y la funcin generadora es:
    4
    Entonces, la funcin generadora resultante es:

    () =

    4. Encuentra el coeficiente de en:


    a. ( )
    El desarrollo de la funcin es:
    1024 13 5120 12 + 11520 11 + + 180 5 20 4 + 3
    Y nos encontramos que el trmino 15 no existe, por lo tanto el coeficiente de este trmino
    es cero. Aun reduciendo y buscando solo el coeficiente para(1 2)10, este no llega a 15 .
    b. ( + ) /( )
    Transformando a:
    (1 + )4 (1 )4

    Para: (1 + )4
    Los coeficientes de su desarrollo son:
    4
    4
    4
    4
    4
    0: ( ) = 1 1: ( ) = 4 2: ( ) = 6 3 ( ) = 4 4 ( ) = 1
    0
    1
    2
    3
    4
    Para: (1 )4
    Los coeficientes de su desarrollo que se suman por ser trminos semejantes, sern los
    grados 11, 12, 13, 14 y 15:
    4
    14
    4
    15
    4
    16
    11: ( ) = ( ) = 364 12: ( ) = ( ) = 455 13: ( ) = ( )
    11
    11
    12
    12
    13
    13
    = 560
    4
    17
    4
    18
    14: ( ) = ( ) = 680 15: ( ) = ( ) = 816
    14
    14
    15
    15

    Anlisis Combinatorio | 22/08/2015

    El coeficiente ser la suma de los trminos semejantes que en los desarrollos que tengan
    15

    Ahora, al reducir los grados correspondientes:


    Grado de
    ( + )

    coeficiente

    Grado de
    ( )

    coeficiente

    Multiplicacin coeficientes
    de

    Suma
    grados

    ( + ) ( )

    15

    816

    (1)(816) = 816

    15

    14

    680

    (4)(680) = 2720

    15

    13

    560

    (6)(560) = 3360

    15

    12

    455

    (4)(455) = 1820

    15

    11

    364

    (1)(364) = 364

    15

    Suma:

    9080

    Solucin:
    (+)

    el coeficiente de en () es 9080.

    5. De cuntas formas pueden separarse 3000 sobres idnticos en paquetes de


    25 entre cuatro grupos estudiantes, de modo que cada grupo tenga al menos
    150 pero no ms de 1000 sobres?
    Organizando la informacin:
    Son paquetes de 25, entonces:
    3000
    = 120
    25

    Anlisis Combinatorio | 22/08/2015

    Son 120 paquetes.


    Si tenemos 150 sobres entonces tenemos:
    150
    =6
    25
    Son 6 paquetes.

    Si tenemos 1000 sobres, entonces:


    1000
    = 40
    25
    Son 40 paquetes
    Para encontrar el polinomio caracterstico de la situacin es:
    6 + 7 + 8 + + 40
    Podemos replantear el problema, como:

    El problema se reduce a repartir 120 paquetes iguales en cuatro grupos de estudiantes de


    modo que cada grupo reciba al menos 6 paquetes pero no ms de 40.
    Entonces:
    Cada grupo debe tener al menos 6 paquetes pero no ms de 40.
    Las distribuciones de esta forma son:
    Para 4 grupos la funcin generadora es:
    ( 6 + 7 + 8 + + 40 )4
    Quien nos dar la respuesta ser el coeficiente del o de los trminos de grado 120, o sea
    120
    Buscamos el coeficiente de 120
    Reduciendo y factorizando:
    ( 6 + 7 + 8 + + 40 )4 = [ 6 (1 + + 2 + 3 + + 34 )]4
    = 24 (1 + 2 + 3 + + 34 )4
    Por estos polinomios sabemos que es lo mismo localizar el coeficiente 120 en la expresin
    24 (1 + 2 + 3 + + 34 )4, que buscar el coeficiente de 96 en la expresin (1 + 2 + 3 +
    + 34 )4 .
    Buscando su funcin generadora:
    4

    (1 + + + +

    34 )4

    1 35
    =(
    ) = (1 35 )4 (1 )4
    1

    Entonces:
    Donde buscaremos el coeficiente con 96 ser en (1 35 )4 (1 )4 .

    Para: (1 )4
    Los coeficientes de su desarrollo que se suman por ser trminos semejantes, sern los
    grados 96, 61 y 26:
    4
    29
    4
    64
    4
    99
    26: ( ) = ( ) = 3654 61: ( ) = ( ) = 41664 96: ( ) = ( )
    26
    26
    61
    61
    96
    96
    = 156849

    Anlisis Combinatorio | 22/08/2015

    Para: (1 35 )4
    Los coeficientes de su desarrollo son:
    Los coeficientes de su desarrollo para la respuesta, son los grados 0, 35 y 70
    4
    4
    4
    0: ( ) = 1 35: ( ) = 4 70: ( ) = 6
    0
    1
    2
    Donde los grados correspondientes son 0, 35 y 70.

    Ahora, al reducir los grados correspondientes:


    Grado de

    coeficiente

    Grado de
    ( )

    ( )

    coeficiente

    Multiplicacin coeficientes
    de

    Suma
    grados

    ( ) ( )

    96

    156849

    (1)(156849) = 156849

    96

    35

    -4

    61

    41664

    (4)(41664) = 166656

    96

    70

    26

    3654

    (6)(3654) = 21924

    96

    Suma:

    12117

    Solucin:
    4

    el coeficiente de 15 en

    (1+ 35 )
    (1)4

    es 12117.

    De otra forma, para clacular el coeficiente de 96 :


    Los productos que dan trminos con 96 son:
    99
    1 ( ) 96
    96

    64
    (4 35 ) ( ) 61
    61

    29
    (6 70 ) ( ) 26
    26

    Sumando estos coeficientes


    99
    64
    29
    ( ) 4 ( ) + 6 ( ) = 156849 4(41664) + 6(3654) = 12117
    96
    61
    26

    Anlisis Combinatorio | 22/08/2015

    La solucin es: 12117 formas.

    6. Cinco inspectores sanitarios realizan pruebas a dos lotes de vacunas de 24


    dosis cada uno. De cuntas formas pueden distribuirse las 48 dosis de modo
    que cada inspector revise al menos dos dosis del primer lote y al menos tres
    dosis del segundo?
    Existen dos casos:
    Caso 1: al menos 2 dosis del primer lote.
    Caso 2: al menos 3 dosis del segundo lote.
    La solucin ser la multiplicacin del nmero de formas de distribuirse del caso 1 por el
    nmero de casos de distribuirse del caso 2.
    Para el primer caso: al menos 2 dosis:
    Polinomio:
    ( 2 + 3 + 4 + )5

    Resolviendo y factorizando:
    [ 2 (1 + + 2 + 3 + )]5
    Entonces:
    10 (1 + + 2 + 3 + )5
    Donde la funcin generadora es:
    10 (1 )5
    Donde la respuesta es el coeficiente del trmino 24
    Simplificando:
    Para la expresin:
    (1 )5
    24
    10 (1
    Es lo mismo que buscaremos
    )5 , y simplificando entonces buscamos
    14 (1 )5:
    Entonces:
    5
    14 + 5 1
    18
    ( )=(
    )=( )
    14
    14
    14
    Entonces, para el primer caso, que es el primer lote, se distribuyen las 24 dosis de (18
    )
    14
    formas

    15 (1 )5
    Donde la respuesta es el coeficiente del trmino 24
    Simplificando:
    Para la expresin:
    (1 )5
    Es lo mismo que buscaremos 24 15 (1 )5 , y simplificando entonces buscamos
    9 (1 )5 :
    Entonces:
    5
    9+51
    13
    ( )=(
    )=( )
    9
    9
    9
    Entonces, para el segundo caso, que es el segundo lote, se distribuyen las 24 dosis de (13
    )
    9
    formas.
    Para los dos lotes las formas son:
    18 13
    ( ) ( ) = (3060)(715) = 2187900
    14
    9

    Anlisis Combinatorio | 22/08/2015

    Para el segundo caso: al menos 3 dosis:


    Polinomio:
    ( 3 + 4 + 5 + )5
    Resolviendo y factorizando:
    [ 3 (1 + + 2 + 3 + )]5
    Entonces:
    15 (1 + + 2 + 3 + )5
    Donde la funcin generadora es:

    Existen 2187900 formas pueden distribuirse las 48 dosis de modo que cada inspector
    revise al menos dos dosis del primer lote y al menos tres dosis del segundo

    Bibliografa:
    Grimaldi, R. (2004). Discrete and Combinatorial Mathematics. Boston: Pearson.

    Anlisis Combinatorio | 22/08/2015

    Referencias:
    https://www.cise.ufl.edu/class/cot3100su09/disc/Note8.pdf
    http://www.iesxunqueira1.com/Departamentos/Documentos/funcionesgeneratrices.pdf
    https://www.youtube.com/watch?v=Yp09MkLpGyc

    También podría gustarte