\documentstyle{article}
\setlength{\textheight}{25cm}
\setlength{\headsep}{0cm}
\setlength{\oddsidemargin}{-.55in}
\setlength{\textwidth}{18cm}
\setlength{\linewidth}{18cm}
\pretolerance=10000
\tolerance=10000
\begin{document}
%\pagestyle{empty}
\centerline{\Large \bf  Primera prueba (MD 2)}
\vspace{0.25cm} 
\begin{enumerate}
\item 
	\begin{enumerate}
 	\item Probar que $\sum_{k=0}^{n}(2\,k+1) \,=\, (n+1)^2$
 	\begin{quote}\small{
 	  Es la suma de n+1 t\'erminos de una progresi\'on aritm\'etica
 	de raz\'on 2, primer t\'ermino 1 y \'ultimo $2\,n+1$}
 	\end{quote}
 	\item Dada una funci\'on generatriz $G(x) = \sum_{n \geq 0}\,g_n\,x^n,$
 	probar que $$\frac{1}{(1-x)}\,G(x) = \sum_{n \geq 0}\left( \sum_{k \leq n}g_k \right) \, x^n $$
 	Usar este hecho para probar que $\frac{x+x^2}{(1-x)^3}$ es
 	 la funci\'on generatriz de la serie cuyo
 	$n$-\'esimo coeficiente es $n^2$
 	\begin{quote}
 	  \small{
 		\begin{itemize}
 		\item $\frac{1}{(1-x)^2}\,=\,1+2x+3x^2+4x^3+5x^4+\cdots$
 		\item $\frac{x}{(1-x)^2}\,=\,   x+2x^2+3x^3+4x^4+\cdots$ por lo tanto
 		\item $\frac{1+x}{(1-x)^2}\,=\,1+3x+5x^2+7x^3+9x^4+\cdots$ y se tiene:
 		\item $\frac{x(1+x)}{(1-x)^2}\,=\,x+3x^2+5x^3+7x^4+9x^5+\cdots 
 		= \sum_{n \geq 0}(2\,n+1)x^{n+1}$
 		\end{itemize}
 	Si aplicamos ahora la f\'ormula $\frac{1}{(1-x)}\,G(x) = \sum_{n \geq 0}
 	\left( \sum_{k \leq n}g_k \right) \, x^n ,$ se tiene,(en virtud del
 	apartado a)) el resultado.}
 	\end{quote} 
 	\item Aplicando lo anterior, o de otro modo, encontrar la funci\'on generatriz
 	de la serie cuyo $n$-\'esimo coeficiente es $(n+1)\,(n-1).$
 	\begin{quote}\small{
 	  La serie con $a_n=n^2 -1$ tendr\'a como funci\'on generatriz
 	la de $n^2$ ( es decir: $\frac{x+x^2}{(1-x)^3}$) menos la de la sucesi\'on
 	constante $1$ (o sea $\frac{1}{(1-x)}$), lo que da:
 	$$\frac{3x-1}{(1-x)^3}$$}
 	\end{quote}
	\end{enumerate}
Tener en cuenta la funci\'on generatriz: $\frac{1}{(1-x)^2}\,=\,\sum_{n \geq 0}\,(n+1)\,x^n,$
\item Describir el uso de las funciones generatrices para resolver recurrencias y
poner un ejemplo sencillo.
No es necesario dar una justificaci\'on del m\'etodo.


\item Describe un algoritmo que calcule el n\'umero de formas distintas de 
repartir $n$ objetos iguales entre tres receptores A, B y C de modo que A reciba al menos cuatro y B y C reciban
al menos dos, pero que C no reciba m\'as de cinco.
	\begin{quote}\small{
	 Para resolver el problema con un n\'umero $n$ (adecuado) se
	ha de calcular el coeficiente de $x^n$ en la siguiente serie:
	$$(x^4+x^5+\cdots )\,(x^2+x^3+\cdots)\,(x^2+x^3+x^4+x^5)$$}
	\end{quote}

 
\item Calcular la probabilidad de que una permutaci\'on $\sigma$ de $\{1,2,\dots,n\}$
satisfaga la propiedad: $$\exists\, i \in \{1,2,\dots,n\} \; {\rm tal \; que} \;\sigma(i)=i$$
justificando la respuesta.
	\begin{quote}\small{
	 Se puede utilizar el hecho de que  $D(n)=n!\,\sum _{k=0}^{n} 
	 \frac{(-1)^k}{k!}$
	 donde $D(n)$ es el n\'umero de desarreglos de $n$ objetos y por lo
	 tanto, el n\'umero de permutaciones de $n$ objetos que satisface la
	 propiedad propuesta es $n!-D(n)$ y pa probabilidad solicitada es:
	 $$\frac{n!-D(n)}{n!}\,=\,1-\frac{D(n)}{n!}$$ que es una cantidad que
	 tiende a $\frac{e-1}{e}$ cuando $n$ crece.
	 \begin{verbatim}
	 $ maple                           
    |\^/|     Maple V Release 2 (Universidade Da Coruna)
._|\|   |/|_. Copyright (c) 1981-1993 by the University of Waterloo.
 \  MAPLE  /  All rights reserved. Maple and Maple V are registered
 <____ ____>  trademarks of Waterloo Maple Software.
      |       Type ? for help.


> p:= n -> 1-(sum('(-1)**k/k!','k'=0..n));

                                       /   n           \
                                       | -----       k |
                                       |  \      (-1)  |
                         p := n -> 1 - |   )    '-----'|
                                       |  /        k!  |
                                       | -----         |
                                       \'k' = 0        /
--------------------------------------------------------------------------------
> for r from 0 to 20 do evalf(p(r)) od;

                                        0

                                       1.

                                   .5000000000

                                   .6666666667

                                   .6250000000

                                   .6333333333

                                   .6319444444

                                   .6321428571

                                   .6321180556

                                   .6321208113

                                   .6321205357

                                   .6321205608

                                   .6321205587

                                   .6321205588

                                   .6321205588

                                   .6321205588

                                   .6321205588

                                   .6321205588

                                   .6321205588

                                   .6321205588

                                   .6321205588
--------------------------------------------------------------------------------
>  evalf((1-1/E));

                                   .6321205588
--------------------------------------------------------------------------------
> 
 \end{verbatim}
 }
	\end{quote}
\end{enumerate}

 
\end{document}

