Alumno: David Cabezas Berrido

DNI: 20079906D

# Números naturales. Inducción. Recursividad.

## Naturales

En esta sección vamos a trabajar con $\mathbb N $

Pero antes, una breve introducción a Jupyter notebook:

1. La tecla a crea una nueva celda encima de la seleccionada.
1. Si pulsamos m, la celda pasa a ser de texto.
1. Dos veces d sobre una celda, la elimina.
1. Shift + tab o ? al final muestran una pequeña ayuda de las funciones.
1. El tabulador autocompleta.
1. Jupyter notebook acepta programación en python y LaTex, como puede 
   comprobarse en la $\mathbb N $ de naturales o en la enumeración de esta lista.

Dicho esto, comencemos.

En `python` podemos utilizar `isinstance` para determinar si un objeto es un entero


```python
isinstance(4,int)
```




    True




```python
isinstance([3.4],int)
```




    False



Podemos con esta función definir otra que detecte si un número es natural


```python
def isnatural(n):
    if not isinstance(n,int):         # Descartamos decimales
        return False
    return n>=0                       # Nos aseguramos de que no sea negativo
```


```python
isnatural(3)
```




    True




```python
isnatural(-3)
```




    False



La funciones sucesor y predecesor quedarían como sigue


```python
sucesor = lambda x: x+1   # lambda permite definir funciones rápidamente
```


```python
sucesor(2)
```




    3



Generador de errores:


```python
def prec(n):
    if not isnatural(n):
        raise TypeError("El argumento debe ser un número natural")
    if n==0: 
        raise ValueError("El 0 no tiene predecesor")
    return n-1
```


```python
prec(1)
```




    0




```python
prec(27)
```




    26




```python
prec(0)
```

La función predecesor está bastante completa, sin embargo la función sucesor es mejorable, ahora sabemos como hacerla.


```python
sucesor(-1.5)
```




    -0.5




```python
def suc(n):
    if not isnatural(n):
        raise TypeError("Debe introducir un número natural")
    return n+1
```


```python
suc(1.5)
```


```python
sucesor(28)
```




    29



Así mejor, ahora podemos definir la suma recursivamente, como hemos visto en teoría


```python
def suma(m,n):
    if n == 0:
        return m
    return sucesor(suma(m,prec(n)))
```


```python
suma(2,3)
```




    5




```python
suma(1000,1)
```




    1001



Pero no cantemos victoria tan pronto.


```python
suma(1,1000)
```




    1001



Definamos también el producto, también de forma poco eficiente


```python
def producto(m,n):
    if n == 0:
        return 0
    return suma(producto(m,prec(n)),m)
```


```python
producto(7,6)
```




    42




```python
producto(500,500)
```




    250000



Tal como dijimos, poco eficiente. Veremos la recursividad en profundidad más adelante.

## Sucesiones, inducción

Con la librería `sympy` podemos hacer cálculo simbólico. En particular, podemos calcular el valor de algunas sumas con parámetros.


```python
import sympy as sp                # Tendre que poner sp. antes de las funciones
```


```python
from sympy import *               # Ya no
```

Cuando vamos a utilizar un símbolo tenemos que declararlo primero. Para el ejemplo que sigue vamos a utilizar `n` como entero e `i` como contador 


```python
n, i = symbols("n, i", integer = True)
```

### Algunas sumatorias

Calculemos por ejemplo $\sum_{i=1}^n i$


```python
s = Sum(i,(i,1,n))
```


```python
s
```




    Sum(i, (i, 1, n))



Si queremos calcular el "valor" de esta sumatoria, podemos utilizar el método `doit`


```python
s.doit()
```




    n**2/2 + n/2




```python
pprint(_)   # Esta función lo imprime de forma más bonita, _ se refiere al último resultado obtenido
```

     2    
    n    n
    ── + ─
    2    2



```python
summation(2,(i,1,n))    # Esta función lo hace directamente, en este caso estamos sumando 2 n veces
```




    2*n



Y una suma de potencias


```python
s=Sum(i**2,(i,1,n))  # Suma de los cuadrados de 1 a n
```


```python
s.doit()
```




    n**3/3 + n**2/2 + n/6




```python
s=Sum(i**30,(i,1,n))    # Suma de los número del 1 a n elevados a 30
```


```python
s.doit()
```




    n**31/31 + n**30/2 + 5*n**29/2 - 203*n**27/6 + 1131*n**25/2 - 16965*n**23/2 + 216775*n**21/2 - 2304485*n**19/2 + 19959975*n**17/2 - 137514723*n**15/2 + 731482225*n**13/2 - 31795091601*n**11/22 + 8053785025*n**9/2 - 102818379585*n**7/14 + 15626519181*n**5/2 - 23749461029*n**3/6 + 8615841276005*n/14322




```python
a = Symbol("a")     
```


```python
Sum(a**i,(i,1,n)).doit()   # a^1 + a^2 + ... + a^n
```




    Piecewise((n, Eq(a, 1)), ((a - a**(n + 1))/(-a + 1), True))



### Inducción

Veamos cómo podemos utilizar `sympy` para hacer algunos ejemplos de inducción

Por ejemplo, veamos que para todo $6\mid 7^n-1$ para todo $n\in \mathbb N$. Empezamos definiendo una función que nos devuelva $7^n-1$


```python
f = lambda n: 7**n -1
```

Primero veamos qué valor tiene en el 0


```python
f(0) % 6     # Se cumple para 0
```




    0



Si por hipótesis de inducción $f(n)$ es un múltiplo de 6, entonces para probar que $f(n+1)$ también lo es, bastará demostrar que la diferencia $f(n+1)-f(n)$ es un múltiplo de 6


```python
simplify((f(n+1)-f(n)) % 6) 
```




    6*Mod(7**n, 1)



Esto significa que es igual a 6 por el resto de dividir $7^n$ entre 1, que obviamente será 0, luego $f(n+1)-f(n)$ se diferencian en un múltiplo de 6. Se confirma así que para cualquier $n\in \mathbb N$, $7^n -1$ en múltiplo de 6.

Ahora demostremos que $7^{2n}+16n-1$ es múltiplo de 64 para cuarquier $n\in \mathbb N$


```python
f = lambda n: 7**(2*n)+16*n-1
```


```python
f(0)
```




    0




```python
simplify((f(n+1)-f(n)) % 64)
```




    16*Mod(3*7**(2*n) + 1, 4)



Esta vez $3\times 7^{2n}+1$ debe de ser múltiplo de $4$, lo cual no es tan obvio habremos acabado. Nueva inducción:


```python
g = lambda n: 3*7**(2*n)+1
```


```python
g(0)
```




    4




```python
simplify((g(n+1)-g(n))%4)
```




    0



$3\times7^{2n}+1$ es múltiplo de 4 para todo $n\in \mathbb N$ y como consecuencia $7^{2n}+16n-1$ lo es de 64

Pongamos otro ejemplo: Demostrar que para todo número impar k, el resto de dividir $2^k$ entre 3 es
2.

Podemos escribir ese k como 2n+1


```python
f = lambda n: 2**(2*n+1)
```


```python
f(0) % 3      # 0 la cumple
```




    2




```python
simplify(f(n+1) - f(n))
```




    6*2**(2*n)




```python
Mod(_,3)
```




    0



Si $f(n+1)$ y $f(n)$ se diferencian en un múltiplo de 3, el resto de dividir $f(n+1)$ entre 3 será el mismo que el de dividir $f(n)$ entre 3, Por lo que si se cumple para un $n\in \mathbb N$, se cumplirá para $n+1$.

Vamos con el último. Demostrar que la sumatoria de las quintas potencias más las séptimas potencias de los naturales del 1 al n es igual a $2\times (\frac{n^2+n}{2})^4$ para cualquier n natural mayor o igual a 1.


```python
k = Symbol("k",integer=true)
```


```python
f = lambda n: 2*((n**2+n)/2)**4
```


```python
g = lambda n: summation(k**5+k**7,(k,1,n))
```


```python
simplify((f(n+1) - f(n)) - (g(n+1) - g(n)))
```




    0



Luego $f(n+1) - f(n)$ es igual a $g(n+1) - g(n)$. Y suponiendo $f(n) = g(n)$ se llega a $f(n+1) = g(n+1)$. Lo que termina la demostración.

### Recursividad e iteración

Veamos cómo las funciones recursivas se pueden acelerar usando memorización de los pasos anteriores


```python
fib = lambda n: n if n<2 else fib(n-2)+fib(n-1)    # Definimos una función recursiva de fibonacci
```


```python
fib(10)
```




    55




```python
fibonacci(10)
```




    55



Parece que funciona igual que la original, pero sólo para el lento tiempo de reacción de las personas y para números pequeños.


```python
import time   # Muestra tiempo

```


```python
start=time.time()
fib(35)
time.time()-start

```




    3.521246910095215




```python
start=time.time()
fibonacci(35)
time.time()-start
```




    0.0009148120880126953



Un posible solución a este problema es ir almacenando los resultados previos de cálculo, lo cual es conocido como [memoization](http://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python)


```python
import functools
```


```python
@functools.lru_cache(maxsize=None)
def fibo(num):
    if num < 2:
        return num
    else:
        return fibo(num-1) + fibo(num-2)
```


```python
start=time.time()
fibo(35)
time.time()-start
```




    0.00027561187744140625



Hemos definido una función recursiva mucho más eficiente, pero requiere de almacenamiento en la memoria, luego es mejor pensar razonadamente y definir una función de fibonacci iterativa.


```python
def fibon(n):
    if (not isnatural(n)) or n == 0:                                        # Generador de errores
        raise TypeError("Debe introducir un número natural distinto de 0")
    else: 
        if n == 1 or n == 2:              # Términos 1 y 2 de la sucesión
            return 1
        else:                             # Cálculo del término n para n >=3
            a = 1
            b = 1
            for i in range(n-2):          # Sumamos los dos anteriores términos n-2 veces
                f = a + b                 
                b = a                     # El número pasa a ser el anterior
                a = f                     # El anterior pasa a ser el anterior del anterior
        return f                          # Devuelvo el término n-ésimo
        
```


```python
fibon(35)
```




    9227465




```python
start=time.time()
fibon(35)
time.time()-start
```




    7.843971252441406e-05



Con esto queda confirmado que la recursividad es bastante mala en términos de eficiencia, aunque más sencilla de programar.
Antes continuar, definamos una función potencia igual a la vista en teoría.


```python
def potencia(m,n):
    if n == 0:
        return 1
    else: 
        return producto(potencia(m,prec(n)),m)
```


```python
potencia(5,0)
```




    1




```python
potencia(2,7)
```




    128



Funciona, pero es una función recursiva que llama a la función producto, también recursiva y que a su vez llama a la función suma, también recursiva. Por lo que esta función es el colmo de la ineficiencia.


```python
potencia(3,9)
```

## Resolución de ecuaciones recursivas

Para sistemas de ecuaciones lineales, ulilizaremos linsolve().

Para sistemas de ecuaciones no lineales, utilizaremos solve(), que también resuelve las lineales pero tarda más por tener que determinar su tipo.

Para ecuaciones en recurrencia, utilizaremos rsolve(), del paquete `simpy`.

Empecemos con un ejemplo:
- $a(0)=0$,
- $a(1)=1$,
- $a(n+2)=5a(n+1)-6a(n)$.

Empezamos declarando `a` como función


```python
a = Function('a')
```

Tendríamos que resolver la ecuación $x^2-5x+6=0$, cuyas soluciones son 2 y 3. Comprobémoslo.


```python
rsolve(a(n+2)-5*a(n+1)+6*a(n),a(n))       
```




    2**n*C0 + 3**n*C1



Sólo nos queda hallar la solución particular, aunque el mismo comando rsolve se puede encargar de ello si le damos
también los términos iniciales como parámetros.


```python
rsolve(a(n+2)-5*a(n+1)+6*a(n),a(n), {a(0):0,a(1):1})  # Diccionario
```




    -2**n + 3**n



En este caso serían C0=-1, C1=1.

También podemos usar el comando solve para resolverla mediante el polinomio característico


```python
x=Symbol("x")
solve(x**2-5*x+6)
```




    [2, 3]



Y por tanto la solución general será de la forma $a_n=u 2^n + v 3^n$, para ciertas constantes $u$ y $v$ que tenemos que encontrar a partir de las condiciones iniciales

Imponemos por tanto que $a_0=0=u+v$ y que $a_1=1=2u+3v$


```python
u,v = symbols("u,v")
solve([u+v,2*u+3*v-1])
```




    {u: -1, v: 1}



Por lo que $a_n=-2^n+3^n$, como habíamos visto arriba

Veamos un ejemplo de una que no sea homogénea

$a(n+2)=5a(n+1)-6a(n)+n$


```python
rsolve(a(n+2)-5*a(n+1)+6*a(n)-n,a(n))
```




    2**n*C0 + 3**n*C1 + C0*n



Como vemos es bastante rápido, ahora hagamos otro más paso a paso.

$a(0)=0$, $a(1)=1$, $a(n+2)=5a(n+1)-6a(n)+n\times3^n$

Cuando la ecuación está igualada a un número elevado a n por un polinomio en n, se añade multiplicando al polinomio característico $(x-b)^{r+1}$ donde b es el número y r el grado del polinomio en n.
El polinomio característico sería $(x^2-5x+6)(x-3)^2$


```python
factor(x**2-5*x+6)
```




    (x - 3)*(x - 2)



Las soluciones serían x=3 (sol. triple) y x=2. Por lo que la solución general tendría esta forma: $(An^2+Bn+C)\times 3^n + D\times 2^n$

Esta ecuación tiene las soluciones deseadas, pero también tiene otras que hemos añadido al obtener el polinomio característico, por lo que para simplificarla tomaremos parámetros generales en las condiciones iniciales.

- $a(0) = p = C + D$
- $a(1) = q = (A+B+C)\times 3 + D\times 2$
- $a(2) = 5\times a(1) - 6\times a(0) + 2\times 3^2 = 5q-6p+18 = (4A+2B+C)\times 9 + D\times 4$ 
- $a(3) = 5\times a(2) - 6\times a(1) + 3\times 3^3 = 5\times (5q-6p+18)-6q+81=(9A+3B+C)\times 27 + D\times 8$

Resolvemos el sistema y comprobamos que dos parámetros ahora son fijos.


```python
A, B, C, D, p, q = symbols("A, B, C, D, p, q")
```


```python
linsolve([C+D-p,(A+B+C)*3+D*2-q,(4*A+2*B+C)*9+D*4-(5*q-6*p+18),(9*A+3*B+C)*27+D*8-(5*(5*q-6*p+18)-6*q+81)],[A,B,C,D])
```




    {(3/2, -9/2, -2*p + q + 9, 3*p - q - 9)}



Ahora la ecuación general (la que tiene sólo las soluciones que nos interesan) tiene esta forma: 


```python
g = lambda n:simplify(((3/2)*n**2+(-9/2)*n+(-2*p+q+9))*3**n+(3*p-q-9)*2**n)
```


```python
solve([g(0),g(1)-1],[p,q])
```




    {p: 0, q: 1}



Introducimos las condiciones especiales particulares y ya podemos hallar la solución particular.


```python
p = lambda n:simplify(((3/2)*n**2+(-9/2)*n+(-2*0+1+9))*3**n+(3*0-1-9)*2**n)
```


```python
p(n)       # Aquí la tenemos
```




    -10*2**n + 3**n*(1.5*n**2 - 4.5*n + 10)



Hagamos otro ejemplo: $a(0)+a(1)=2, a(1)+a(2)=4, a(n)+a(n-1)=2n$

Esta vez las condiciones iniciales vienen dadas de una forma peculiar. Aunque de eso nos ocuparemos luego, para homogeneizar y eliminar el $2n$ restaremos dos términos consecutivos de la ecuación.


```python
n = Symbol("n", integer=true)
a = Function('a')
```


```python
rsolve(a(n)-a(n-1)-n+1,a(n),{a(1):0})
```




    n*(n/2 - 1/2)




```python
pprint(_)
```

      ⎛n   1⎞
    n⋅⎜─ - ─⎟
      ⎝2   2⎠



```python
a(n)+a(n-1)-2*n - (a(n-1)+a(n-2)-2*(n-1))
```




    a(n) - a(n - 2) - 2



Ahora tenemos un molesto 2, que podemos eliminar repitiendo el proceso. 


```python
a(n)-a(n-2)-2 -(a(n-1)-a(n-3)-2) 
```




    a(n) + a(n - 3) - a(n - 2) - a(n - 1)




```python
solve(x**3-x**2-x+1,x)   # Esto no nos vale, no tiene en cuenta las soluciones múltiples
```




    [-1, 1]




```python
factor(x**3-x**2-x+1,x) # Ahora sí
```




    (x - 1)**2*(x + 1)




```python
g = lambda n: A*(-1)**n +(B*n+C)  # Solución general
```

Ahora debemos buscar una solución particular que cumpla   $a(1)+a(0)=2,   a(2)+a(1)=4$

Para esto, resolveremos el siguiente sistema:

- $a(0)+a(1) = 2$

- $a(1)+a(2) = 4$


```python
solve([g(0)+g(1)-2,g(2)+g(1)-4],[A,B,C])
```




    {B: 1, C: 1/2}




```python
p = lambda n: A(-1)**n + n + 1/2
```


```python
p(n)
```




    n + A(-1)**n + 0.5



Esta solución particular es válida para cualquier valor de A.

Ahora pasemos a ver la utilidad de esto, con ejemplo más prácticos.

El juego de las Torres de Hanói se trata de pasar una serie de discos de una varilla a otra, disponiendo de una tercera para auxliarse, reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Calculemos el mínimo número de movimientos posibles para realizar el juego con n discos, $a(n)$.

Cuenta una leyenda que Dios encargó a los monjes de un monasterio de Hanói pasar 64 discos entre tres varillas de diamante, y que cuando acabaran, el mundo terminaría.

Para desplazar los $n$ discos, primero tendremos que desplazar todos menos el mayor a una de las varillas, $a(n)$; a continuación, desplazar el mayor de los discos a la otra varilla que queda libre ($1$); y por último, volver a colocar los $n-1$ primeros encima del mayor. Luego nos queda la siguiente ecuación de recurrencia:

$a(n)=2a(n-1)+1$



```python
rsolve(a(n)-2*a(n-1)-1,a(n),{a(0):0})   # Aunque no sea homogénea, rsolve puede hacerla directamente
```




    2**n - 1




```python
h = lambda n: 2**n - 1
```


```python
h(64)     
```




    18446744073709551615



Si los monjes movieran un disco por segundo, tardarían en completar el juego 117 el tiempo de exitencia de la Tierra y 41.78 veces el tiempo de vida del universo. Así que aún queda mundo para rato.

Ahora contemos las regiones en las que queda subdividido un plano al trazar n rectas no paralelas y sin que 3 rectas se corten en el mismo punto:

- 0 rectas -> 1 región
- 1 recta -> 2 regiones
- 2 rectas -> 4 regiones
- 3 rectas -> 7 regiones

Nos queda la ecuación de recurrencia:
$a(n)=a(n-1)+n$, con $a(0)=1$ 




```python
rsolve(a(n)-a(n-1)-n,a(n),{a(0):1})
```




    n*(n + 1)/2 + 1




```python
pprint(_)
```

    n⋅(n + 1)    
    ───────── + 1
        2        



```python
r = lambda n: n*(n+1)/2+1
```


```python
r(100)
```




    5051.0



Sería difícil contar las regiones tras trazar 100 líneas, pero sabemos que saldrían 5051.

Ahora un ejemplo bastante conocido, que permitirá hallar una fórmula iterativa para calcular un término de la sucesión de fibonacci, este lo haremos paso a paso. $a(n)=a(n-1)+a(n-2), a(0)=0, a(1)=1$


```python
solve(x**2-x-1)    # Las soluciones del polinomio característico son el número phi y el inverso de su opuesto.
```




    [1/2 + sqrt(5)/2, -sqrt(5)/2 + 1/2]




```python
g = lambda n: A*(1/2+sqrt(5)/2)**n + B*(1/2-sqrt(5)/2)**n
```


```python
solve([g(0),g(1)-1],[A,B])   # Se puede hacer a mano por reducción fácilmente y se obtiene A = 1/sqrt(5), B = -1/sqrt(5)
```




    {A: 0.447213595499958, B: -0.447213595499958}




```python
fibo = lambda n: (1/sqrt(5))*(1/2+sqrt(5)/2)**n - (1/sqrt(5))*(1/2-sqrt(5)/2)**n 
```


```python
fibo(10)
```




    -sqrt(5)*(-sqrt(5)/2 + 0.5)**10/5 + sqrt(5)*(0.5 + sqrt(5)/2)**10/5



Es curioso como una expresión tan compleja siempre acaba valiendo un número natural. Pero eso no es nada, en el siguiente y último ejemplo, incluso se utilizan números imaginarios.

$a(1)=1, a(2)=2, a(n)=-a(n-2)$


```python
solve(x**2+1,x)     # Empezamos bien...
```




    [-I, I]




```python
g = lambda n: A*I**n + B*(-I)**n
```


```python
solve([g(1)-1,g(2)-2],[A,B])
```




    {A: -1 - I/2, B: -1 + I/2}




```python
p = lambda n: (-I/2-1)*I**n + (I/2-1)*(-I)**n
```


```python
simplify(p(1)), simplify(p(8)), simplify(p(10789423))   # Le ocurre lo mismo que al anterior
```




    (1, -2, -1)



## Combinatoria

#### Principio de inclusión-exclusión

Para contar los elementos de la unión de dos o más conjuntos cuando es más fácil calcular la intersección que la unión. Se usa el principio de inclusión-exclusión. Consiste en sumar los cardinales de los conjuntos y a continuación restar las intersecciones de cada par de conjuntos, posteriormente la de cada trío de conjuntos... y así hasta sumar (si es un número impar de conjuntos) o restar(si es un número par de conjuntos) la intersección de todos.
Por ejemplo:


```python
X={1,2,3,4,5,6}
Y={4,5,6,7}
Z={6,7,8,9,10,11}
```


```python
len(X|Y|Z)     # len() dice el cardinal, y | significa unión.
```




    11



Python cuenta con una función que lo hace, pero, ¿y si no la tuviéramos?


```python
len(X)+len(Y)+len(Z)-len(X&Y)-len(X&Z)-len(Y&Z)+len(X&Y&Z)   # & hace la intersección de conjuntos
```




    11



Ahora un ejemplo práctico, veamos cuántos números binarios de 6 cifras no continen la secuencia 101. Para ello es más fácil empezar calulando los que sí la contienen. La primera cifra ha de ser un 1, luego tendremos que considerar 4 conjuntos, que son las 4 formas diferentes de que aparezca la secuencia:

$
1. A:   1 0 1 _ _ _     (8)
2. B:   1 1 0 1 _ _     (4)        
3. C:   1 _ 1 0 1 _     (4)
4. D:   1 _ _ 1 0 1     (4)
$

A la derecha está el cardinal de cada conjunto, que corresponde al número de posibilidades en cada posición (2, 1 ó 0) elevado al número de posiciones. Ahora consideremos las intersecciones de de cada par de conjuntos. Por ejemplo, el cardinal de A&C es 2, ya que sólo queda un hueco libre ($2^1$), el de A&D es 1 ($2^0$) y el de A$B es 0 porque no existen números binarios que tengan el 0 y el 1 a la vez en la misma posición.

$
- A&B:             (0)
- A&C: 1 0 1 0 1 _ (2)
- A&D: 1 0 1 1 0 1 (1)
- B&C:             (0)
- B&D: 1 1 0 1 0 1 (1)
- C&D:             (0)
- A&B&C, A&B&D, A&C&D, B&C&D    (0) 
- A&B&CD           (0)
$

El cálculo que necesitamos hacer será |A|+|B|+|C|+|D|-|A&B|-|A&C|-|A&D|-|B&C|-|B&D|-|C&D|+|A&B&C|+|A&B&D|+|A&C&D|+|B&C&D|-|A&B&C&D|



```python
8+4+4+4-0-2-1-0-1-0+0+0+0+0-0
```




    16



Como hay 32 números binarios de 6 cifras (5 huecos libres, $2^5$) y 16 contienen la secuencia 101, 32-16 = 16 números binarios de 6 cifras no la contendrán.

#### Listas

En un conjunto de $n$ elementos, podemos formar $n^k$ listas de k elementos diferentes. Si en cada lista no se pueden repetir elementos, para el número es $n$ elevado a $k$ descendente, es decir, $n\times(n-1)\times...\times(n-k)\times(n-k+1)$. Definamos una función que calcula las variaciones simples (sin repetición) de $k$ entre $n$ elementos.


```python
def V(n,k):
    v = n;
    for i in range(1,k):   # Hace iteraciones con i=1, i=2,...,i=k-1
        v = v*(n-i)        # n(n-1)(n-2)...(n-(k-1))
    return v
        
```


```python
V(7,3)    # 7*6*5
```




    210




```python
V(7,9)    # Hay 0 formas de escoger 9 elementos diferentes en un conjunto de 7 (el bucle llega a 0 y empieza a multiplicar 0)
```




    0




```python
def perm(n): return V(n,n)    # Serían las posibles permutaciones, n!
```


```python
perm(6)
```




    720




```python
def perm_circ(n): return perm(n-1)     # Permutaciones circulares, (n-1)!
```


```python
perm_circ(6)
```




    120



#### Combinaciones

Las combinaciones son listas en las que no importa el orden, por lo que tendremos que dividir el número de listas entre las formas de ordenarlas, las combinaciones simples equivalen a los números combinatorios.


```python
def combs(n,k): 
    if k == 0:
        return 1
    else:
        return V(n,k)/perm(k)  # Es lo mismo que n!/(k!(n-k)!) 
```


```python
combs(4,2)     # 4 sobre 2
```




    6.0




```python
def combs_rep(n,k): return factorial(n+k-1)/(factorial(k)*factorial(n-1))    # Ahora las combinaciones con repetición
```


```python
combs_rep(3,3)
```




    10




```python
a,b = symbols("a,b")
```


```python
expand((a+b)**5)
```




    a**5 + 5*a**4*b + 10*a**3*b**2 + 10*a**2*b**3 + 5*a*b**4 + b**5



Podemos definir una función que dada una lista de exponentes calcule el coeficiente multinomial que les corresponde.


```python
def coef_multinomial(X):
    dividendo = 0
    for k in X:
        dividendo += k
    dividendo = factorial(dividendo)
    divisor = 1
    for k in X:
        divisor *= factorial(k)
    return dividendo/divisor
```


```python
coef_multinomial([2,2,1])
```




    30




```python
x,y,z,c,d = symbols("x,y,z,c,d")
```


```python
pprint(coef_multinomial([a,b,c,d]))
```

    (a + b + c + d)!
    ────────────────
      a!⋅b!⋅c!⋅d!   



```python
expand((x+y+z)**5)
```




    x**5 + 5*x**4*y + 5*x**4*z + 10*x**3*y**2 + 20*x**3*y*z + 10*x**3*z**2 + 10*x**2*y**3 + 30*x**2*y**2*z + 30*x**2*y*z**2 + 10*x**2*z**3 + 5*x*y**4 + 20*x*y**3*z + 30*x*y**2*z**2 + 20*x*y*z**3 + 5*x*z**4 + y**5 + 5*y**4*z + 10*y**3*z**2 + 10*y**2*z**3 + 5*y*z**4 + z**5




```python
pprint(_)  # Efectivamente podemos comprobar que el coeficiente del término x^2 y^2 z es 30
```

     5      4        4         3  2       3           3  2       2  3       2  2  
    x  + 5⋅x ⋅y + 5⋅x ⋅z + 10⋅x ⋅y  + 20⋅x ⋅y⋅z + 10⋅x ⋅z  + 10⋅x ⋅y  + 30⋅x ⋅y ⋅z
    
           2    2       2  3        4         3           2  2           3        
     + 30⋅x ⋅y⋅z  + 10⋅x ⋅z  + 5⋅x⋅y  + 20⋅x⋅y ⋅z + 30⋅x⋅y ⋅z  + 20⋅x⋅y⋅z  + 5⋅x⋅z
    
    4    5      4         3  2       2  3        4    5
      + y  + 5⋅y ⋅z + 10⋅y ⋅z  + 10⋅y ⋅z  + 5⋅y⋅z  + z 


Esto significa que existen 30 formas de repartir 5 objetos diferentes en 3 cajas con 2 objetos en la primera, dos en la segunda y uno en la última. Tendría ${5\choose 2}$ opciones para la primera caja, y a partir de ahí ${3\choose 2}$ para la segunda, obviamente en la tercera va el que quede.


```python
combs(5,2) * combs(3,2)
```




    30.0



#### Particiones

Los números de Stirling de segunda clase representan las formas de dividir un conjunto en varios subconjuntos disjuntos, no vacíos tales que su unión es el total. No es difícil definir una función recursiva para calcularlo.


```python
def Stirling2(n,k):
    if k > n:
        raise TypeError("El segundo argumento nunca puede se mayor que el primero")
    if n == k or k == 1:
        return 1
    else:
        return Stirling2(n-1,k-1) + k*Stirling2(n-1,k)
```


```python
Stirling2(5,3)
```




    25



También podemos definir una función (no muy eficiente) que calcule el n-ésimo número de Bell, que representa el número de particiones de un conjunto con n elementos.


```python
def Bell(n):
    bell = 0
    for k in range(1,n+1):
        bell += Stirling2(n,k)
    return bell
        
```

Ahora definamos una función que calcule las particiones de un número natural n con k o menos sumandos.


```python
import functools           # Utilizaremos la memoization, porque esta función no va a ser nada eficiente.
```


```python
@functools.lru_cache(maxsize=None)
def part_nat(n,k):
    if k == 1:
        return 1
    if k == n:
        return part_nat(n,n-1) + 1
    if k > n:
        return part_nat(n,n)
    if k < n:
        return part_nat(n,k-1) + part_nat(k,n-k)
```


```python
part_nat(7,7)
```




    15



#### Aplicaciones


```python
n, k = symbols("n, k")
```

Consideremos las aplicaciones de un conjunto A, de cardinal $n$ en un conjunto B, de cardinal $k$.

El número de aplicaciones totales es de $k^n$, ya que cada aplicación es una lista de $n$ elementos elegidos entre $k$.

El número de aplicaciones inyectivas es el mismo que el de listas sin repetición, requiere que $n$ sea menor o igual que $k$.

El número de aplicaciones biyectivas es el mismo que el de las permutaciones de cualquiera de los conjuntos ($n!$), requiere que $k$ sea igual a $n$.

Para las aplicaciones sobreyectivas, la fórmula es más complicada y hace uso del principio de inclusión-exclusión: 

$T(n,k)=\sum_{i=0}^{k-1}{{k \choose i}\times (-1)^i\times (k-i)^n}$

Posteriormente definiremos una función para calcularla.


```python
V(5,2)          # Un ejemplo de aplicaciones inyectivas de un conjunto de 2 elementos en otro de 5
```




    20




```python
def T(n,k):
    t = 0
    for i in range(0,k):
        t += combs(k,i)*(-1)**i*(k-i)**n
    return t
```


```python
T(5,3)
```




    150.0



También se puede calcular como $S(n,k)\times k!$


```python
def T_(n,k):
    return perm(k)*Stirling2(n,k)
```


```python
T_(5,3)
```




    150



#### Desbarajustes

Los desbarajustes de $n$ son las formas de ordenar n elementos de forma que ninguno de ellos quede en su sitio, cumplen la ecuación:

$D(1)=0, D(n)=n\times D(n-1) + (-1)^n$


```python
def D(n):
    if n <= 1:
        return 0
    return n*D(n-1)+(-1)**n
    
```


```python
D(7)
```




    1854



Aunque podemos definirla por una fórmula iterativa:

$D(n)=n!\times \sum_{i=0}^{n}{\frac{(-1)^i}{i!}}$


```python
def D(n):
    suma = 0
    for i in range(0,n+1):
        suma += (-1)**i/factorial(i)
    return factorial(n)*suma
```


```python
D(7)
```




    1854



19ce89c1d07c4ca0a5a24181f4bdd66496032e47
ipynb
Jupyter Notebook
GuionesPracticas/Naturales.ipynb
dcabezas98/LMD
2f1430bdf14ae0baa936782a3afc36108b323b42
MIT
GuionesPracticas/Naturales.ipynb
dcabezas98/LMD
2f1430bdf14ae0baa936782a3afc36108b323b42
MIT
GuionesPracticas/Naturales.ipynb
dcabezas98/LMD
2f1430bdf14ae0baa936782a3afc36108b323b42
MIT
Qwen/Qwen-72B
1. YES
2. YES