Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 40 vistas

    Recurrencia

    Cargado por

    Carlos Nbova Dawad
    Este documento presenta varios ejercicios sobre definiciones recursivas de conjuntos y secuencias numéricas. Los ejercicios incluyen definiciones recursivas de conjuntos de números enteros, pares ordenados, palabras binarias, permutaciones, formas de agregar paréntesis y darse la mano alrededor de una mesa. También se piden relaciones recursivas y de recurrencia para varias secuencias numéricas, y se exploran sus relaciones con los números de Fibonacci, Motzkin y trayectorias similares.

    Copyright:

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

    Recurrencia

    Cargado por

    Carlos Nbova Dawad
    40 vistas3 páginas
    Este documento presenta varios ejercicios sobre definiciones recursivas de conjuntos y secuencias numéricas. Los ejercicios incluyen definiciones recursivas de conjuntos de números enteros, pares ordenados, palabras binarias, permutaciones, formas de agregar paréntesis y darse la mano alrededor de una mesa. También se piden relaciones recursivas y de recurrencia para varias secuencias numéricas, y se exploran sus relaciones con los números de Fibonacci, Motzkin y trayectorias similares.

    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 varios ejercicios sobre definiciones recursivas de conjuntos y secuencias numéricas. Los ejercicios incluyen definiciones recursivas de conjuntos de números enteros, pares ordenados, palabras binarias, permutaciones, formas de agregar paréntesis y darse la mano alrededor de una mesa. También se piden relaciones recursivas y de recurrencia para varias secuencias numéricas, y se exploran sus relaciones con los números de Fibonacci, Motzkin y trayectorias similares.

    Copyright:

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

    Recurrencia

    Cargado por

    Carlos Nbova Dawad
    Este documento presenta varios ejercicios sobre definiciones recursivas de conjuntos y secuencias numéricas. Los ejercicios incluyen definiciones recursivas de conjuntos de números enteros, pares ordenados, palabras binarias, permutaciones, formas de agregar paréntesis y darse la mano alrededor de una mesa. También se piden relaciones recursivas y de recurrencia para varias secuencias numéricas, y se exploran sus relaciones con los números de Fibonacci, Motzkin y trayectorias similares.

    Copyright:

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

    Universidad Nacional de Colombia

    . Departamento de Matemáticas
    . Sistemas Numéricos
    . Definiciones Recursivas (I-2018)

    Prof. José L. Ramı́rez


    Nombre: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Código . . . . . . . . . . . . . Fecha . . . . . . . . . . . . .

    1. Escriba una definición recursiva de:

    el conjunto de los enteros positivos impares.


    el conjunto de los enteros pares.
    el conjunto de los enteros positivos potencias de 3.
    el conjunto de los enteros positivos no divisibles por 5.

    2. Sea S el conjunto de los pares ordenados de enteros definidos recursivamente por:

    (0, 0) ∈ S.
    si (a, b) ∈ S, entonces (a + 2, b + 3) ∈ S y (a + 3, b + 2) ∈ S.

    a) Encuentre los elementos de S obtenidos por las primeras cinco aplicaciones de la


    definición recursiva.
    b) Utilice el PIM (Fuerte) sobre el número de aplicaciones del paso recursivo de la
    definición para demostrar que 5 divide a a + b cuando (a, b) ∈ S.

    3. Sea an el número de palabras binarias de longitud n que no contienen dos 1’s consecu-
    tivos. Demuestre que an = Fn+2 .

    4. Sea bn el número de permutaciones π en el conjunto Sn = {1, 2, . . . , n} tal que |i−πi | ≤


    1 para todo 1 ≤ i ≤ n, donde n ≥ 1. En otras palabras, bn cuenta el número de
    permutaciones que envı́an cada elemento a otro que diste a lo más de una posición de
    su posición natural. Calcule b4 . Encuentre una recurrencia para bn . ¿Qué relación hay
    con los números de Fibonacci?

    5. Sea Cn el número de formas de poner paréntesis al producto de n + 1 números,


    x0 · x1 · x2 · · · · · xn , para especificar el orden de multiplicación. Por ejemplo C3 = 5,
    ya que hay 5 formas de poner paréntesis a la expresión x0 · x1 · x2 · x3 , que son:

    ((x0 ·x1 )·x2 )·x3 , (x0 ·(x1 ·x2 ))·x3 , (x0 ·x1 )·(x2 ·x3 ) x0 ·((x1 ·x2 )·x3 ) x0 ·(x1 ·(x2 ·x3 )).
    Demuestre que Cn satisface la siguiente recurrencia:

    Cn = C0 Cn−1 + C1 Cn−2 + · · · + Cn−1 C0 ,

    con C0 = C1 = 1.

    6. Sea Hn el número de formas en el que 2n personas, sentadas alrededor de una mesa


    redonda, pueden darse la mano sin entrecruzar sus manos. Calcule Hn y encuentre una
    relación con Cn .

    7. Considere la secesión {Pn }n≥0 definida por Pn = 2Pn−1 + Pn−2 para n ≥ 2, con los
    valores iniciales P0 = 0 y P1 = 1.

    Demuestre que para todo número natural n ≥ 0 se tiene que


    n
    X 1
    P2k+1 = P2n+2 .
    k=0
    2

    Sea Qn el número de formas de teselar una cinta de tamaño 2 × n (n ≥ 1) con las


    siguientes tres baldosas:

    2 1 1
    1
    2 2

    Demuestre que Qn = Pn+1 para todo n ≥ 1.

    8. Sea M el conjunto de trayectorias de Motzkin definidas recursivamente por:

    ∅ ∈ M.
    si M1 y M2 son trayectorias de Motzkin, entonces la siguiente trayectoria es tam-
    bién de Motzkin:
    M1

    M2

    si M1 es una trayectoria de Motzkin, entonces la siguiente trayectoria es también


    de Motzkin:
    M1
    a) Encuentre los elementos de M obtenidos por las primeras dos aplicaciones de la
    definición recursiva.
    b) Sea mn es el número de trayectorias de Motzkin de longitud n (número de pa-
    sos). Encuentre los valores de mn para n = 0, 1, 2, 3. Muestre explı́citamente los
    elementos en cada caso.
    c) Sea vn el número de secuencias de enteros positivos con n − 1 dı́gitos en el que el
    primer dı́gito o el último es 1 o 2, y tal que la diferencia entre cualquier par de
    dı́gitos consecutivos es -1, 0 o 1. Por ejemplo v4 = 9, y las sucesiones son

    (1, 1, 1), (2, 3, 2), (2, 2, 2), (2, 1, 2), (2, 1, 1), (2, 2, 1), (1, 2, 1), (1, 2, 2), (1, 1, 2).

    Encuentre los primeros valores de vn para n = 0, 1, 2, 3, 4, 5 (muestre explı́cita-


    mente los elementos en cada caso).
    d ) ¿Qué relación hay entre mn y vn ? Justifique su respuesta.

    También podría gustarte