\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ciência da Computação
\hfill ICEx/UFMG \\
{\it Matemática Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \hfill www.dcc.ufmg.br/\verb+~+nvieira\\
\underline{Segunda Lista de Exercícios/Solução do professor}

\vspace*{4mm}
\noindent {\bf Combinatória Elementar}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize De quantas maneiras se pode arranjar as letras em GUARATINGUETA:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item No total?
        \item Com todos os As consecutivos?
        \item Com todas as vogais consecutivas?
        \item De forma que não existam (dois) A's consecutivos?
       \end{list}}

       \textit{Solução}:

			 Números de letras: 3 A, 2 G, 2 T, 2 U, 1 R, 1 I, 1 N, 1 E. Total: 13 letras.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P(13;3,2,2,2,1,1,1,1)=13!/(3!2!2!2!)$.
        \item $P(11;2,2,2,1,1,1,1)=11!/(2!2!2!)$.
        \item $P(7;2,2,1,1,1)\times P(7;3,2,1,1)=[7!/(2!2!)]\times[7!/(3!2!)]=(7!7!)/(3!2!2!2!)$.
        \item $P(10;2,2,2,1,1,1,1)\times C(11,3)=(C(11,3)\times 10!)/(2!2!2!)$.
       \end{list}

 \item {\footnotesize Determine o número de seleções de 6 bolas de sorvete a partir de bolas de 20 sabores diferentes,
       de forma que não sejam selecionadas mais de duas bolas com o mesmo sabor.}

       \textit{Solução}:
			 \begin{enumerate}
			  \item[1.] Todas as 6 bolas de sabores diferentes: $C(20,6)$;
				\item[2.] 2 bolas de mesmo sabor e 4 de sabores diferentes: $C(20,1)\times C(19,4)$;
				\item[3.] 2 bolas de um sabor, 2 bolas de outro sabor e 2 bolas de sabores diferentes dos dois primeiros
				          e diferentes entre si: $C(20,2)C(18,2)$.
				\item[4.] 2 bolas de um sabor, 2 bolas de outro sabor e 2 bolas de um sabor diferentes dos dois primeiros:
				          $C(20,3)C(17,0)$.
			 \end{enumerate}
       Resposta: $C(20,6)+C(20,1)C(19,4)+C(20,2)C(18,2)+C(20,3)C(17,0)$.

 \item {\footnotesize Em uma transferência (simultânea) de 12 bandidos de uma penitenciária para outra eles
       devem ser acompanhados cada um por um policial.  Quantos grupos de 12 pares podem ser constituídos a partir
			 dos 12 bandidos e 12 policiais?}

       \textit{Solução}:  $12!$.

 \item {\footnotesize Um batalhão de 50 soldados deve fazer 5 filas de 10 elementos. A única restrição é que os 5
       maiores soldados devem encabeçar as 5 filas. Quantas possibilidades existem para isso?}

       \textit{Solução}:  Retirando-se os 5 soldados maiores, os restantes 45 devem ser distribuídos dentre as 5
			     filas, uma para cada um dos maiores soldados. Resposta: $45!$.

 \item {\footnotesize De quantas maneiras 5 homens e 5 mulheres podem ser dispostos lado a lado de forma
       que homens não fiquem juntos?}

       \textit{Solução}:
			 \begin{enumerate}
			  \item[1.] Disposição das mulheres: $5!$;
				\item[2.] seleção de 5 posições dentre 6 para colocar os homens: $C(6,5)$;
				\item[3.] disposição dos homens nas 5 posições escolhidas: $5!$.
			 \end{enumerate}
       Resposta: $5!\times 6 \times 5!$.

 \item {\footnotesize Uma fazendeiro produz laranjas de 5 diferentes qualidades. Supondo que ele vá
       selecionar 10 laranjas para presentear o vizinho, quantas seleções são possíveis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se uma seleção pode ser constituída de quaisquer qualidades de
              laranjas?
        \item Se uma seleção deve ter pelo menos uma laranja de cada tipo?
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(5-1+10,10)=C(14,10)$.
        \item $C(5-1+5,5)=C(9,5)$.
       \end{list}

 \item {\footnotesize Um grupo de estudos de 10 pessoas deve ser formado a partir de uma turma de 12 alunos e 6 alunas. De
       quantas maneiras é possível fazer essa formação, supondo que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Deva haver exatamente 5 alunas no grupo?
        \item Deva haver, no mínimo, 4 alunas no grupo?
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(6,5)C(12,5)$.
        \item $C(6,4)C(12,6)+C(6,5)C(12,5)+C(6,6)C(12,4)$.
       \end{list}

 \item {\footnotesize Um grupo de 18 políticos deve formar um ``trem da alegria'', de forma que 3 deles viajem para
       Nova Iorque, 4 para Los Angeles, 5 para Orlando e 6 para Las Vegas. De quantas formas tal grupo pode ser assim
			 particionado?}

       \textit{Solução}: $C(18;3,4,5,6)=18!/(3!4!5!6!)$.

 \item {\footnotesize Se $n$ objetos distintos são distribuídos em $n$ caixas distintas, qual é a probabilidade que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Nenhuma caixa fique vazia?
        \item Exatamente uma caixa fique vazia?
       \end{list}}

       \textit{Solução}:
			 O número de distribuições de $n$ objetos distintos em $n$ caixas distintas é $n^n$. Segue-se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Probabilidade: $n!/n^n$.
        \item \begin{enumerate}
			         \item[1.] Escolhas para a caixa vazia: $C(n,1)$;
	        		 \item[2.] Escolhas para a caixa com dois objetos: $C(n-1,1)$;
				       \item[3.] Escolhas dos dois objetos para compartilhar uma caixa: $C(n,2)$.
			         \item[4.] Distribuições dos $n-2$ objetos restantes em $n-2$ caixas distintas: $(n-2)!$.
		          \end{enumerate}
               Resposta: $n(n-1)C(n,2)(n-2)!/n^n=$.
       \end{list}

% Townsend 2.3, pag. 68, ex. 24

 \item {\footnotesize As 52 cartas do baralho são distribuídas em número igual para 4 pessoas distintas.
       Qual é a probabilidade que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada pessoa receba um dos ases?
        \item Uma pessoa receba todos os ases?
       \end{list}}

       \textit{Solução}:
			 O espaço amostral consta de $C(52;13,13,13,13)=52!/(13!13!13!13!)$ distribuições possíveis.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada pessoa recebe um dos ases em $P(4,4)\times C(48;12,12,12,12)$ distribuições. Logo a probabilidade é
				      $[4!\times 48!/(12!12!12!12!]/[52!/(13!13!13!13!)]=(24\times 13^4)/(52\times 51\times 50\times 49)=
							 (6\times 13^3)/(51\times 50\times 49)\simeq 0,105$.
        \item Uma pessoa receba todos os ases em $C(4,1)\times C(48;13,13,13,9)$  distribuições. Logo a probabilidade é
				      $[4\times 48!/(13!13!13!9!)]/[52!/(13!13!13!13!)]=
							 (12\times 11\times 10)/(51\times 50\times 49)\simeq 0,011$.
       \end{list}

% Townsend 2.4, pag. 75, ex. 12

 \item {\footnotesize Quantas sequências ternárias de 30 dígitos têm exatamente dez 1s?}

       \textit{Solução}:
			 \begin{enumerate}
			  \item[1.] Escolhas para as posições dos 10 1s: $C(30,10)$;
	      \item[2.] Distribuições de dígitos 0 e 2 nas 20 posições restantes: $2^{20}$.
		   \end{enumerate}
       Resposta: $C(30,10)2^{20}$.

 \item {\footnotesize Escreva problemas equivalentes do tipo ``soluções em inteiros de uma equação''
       para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O número de maneiras de distribuir $r$ bolas idênticas em $n$ caixas distintas com pelo menos $k$ bolas
				      na primeira caixa.
        \item O número de maneiras de distribuir $r$ bolas idênticas em $n$ caixas distintas de forma que nenhuma caixa
				      contenha mais de duas bolas.
        \item O número de subconjuntos de três elementos de $\{A,B,C,D,E\}$.
        \item O número de maneiras de distribuir $r$ bolas idênticas em $n$ caixas
              distintas de forma que as primeiras duas caixas contenham um total de $p$ bolas.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+\cdots+x_n=r$, com $x_1\geq k$ e $x_i\geq 0$ para $i\geq 2$.
        \item $x_1+x_2+\cdots+x_n=r$, com $0\leq x_i\leq 2$.
        \item $x_1+x_2+x_3+x_4+x_5=3$, com $x_i\in\{0,1\}$.
        \item  $x_1+x_2+\cdots+x_n=r$, com $x_i\geq 0$ e $x_1+x_2=p$.
       \end{list}

% Townsend 2.5, pag. 81, ex. 1

 \item {\footnotesize Encontrar o número de soluções em inteiros não-negativos
       para o sistema de equações:
       
       \[\left. \begin{array}{l}
                 x_1+x_2+x_3+x_4+x_5=20 \\
                 x_1+x_2+x_3=8
                \end{array} \right\} \mbox{ com } x_k\geq 0 \]}

       \textit{Solução}: O número de soluções para $x_1+x_2+x_3=8$ com $x_k\geq 0$ é $C(3-1+8,8)$.
			 O número de soluções para $8+x_4+x_5=20$ é $C(2-1+12,12)$. Logo, a resposta é:
			 $C(3-1+8,8)C(2-1+12,12)=C(10,8)C(13,12)=[10\times9/2]\times 13=585$.

 \item {\footnotesize Qual é o coeficiente de $x^{10}$ em $(1-2x-3y)^{20}$?}

       \textit{Solução}: $C(20;10,10,0)1^{10}(-2)^{10}(-3)^0=[20!/10!10!]2^{10}$.

 \item {\footnotesize Prove, por indução, que $C(n+1,r+1)=\sum_{k=r}^{n}C(k,r)$.}

       \textit{Solução}: Para $n=r$, tem-se: $C(r+1,r+1)=1=C(r,r)$. Seja $n\geq r$ arbitrário.
       Suponha, como hip\'otese de indução, que $C(n+1,r+1)=\sum_{k=r}^{n}C(k,r)$.
       Tem-se:

       $\begin{array}{ccll}
         \sum_{k=r}^{n+1}C(k,r) & = & \sum_{k=r}^{n}C(k,r) + C(n+1,r) &
               \mbox{pela definição de somat\'oria} \\
               & = & C(n+1,r+1) + C(n+1,r) & \mbox{pela hip\'otese de indução} \\
               & = & C(n+2,r+1) & \mbox{pela identidade de Pascal.} \\
         \end{array}$

 \item {\footnotesize Prove, usando raciocínio combinatório:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^{n}C(n,k)^2=C(2n,n)$.
        \item $\sum_{k=0}^{r}C(m,k)C(n,r-k)=C(m+n,r)$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sejam $A$ e $B$ dois conjuntos disjuntos de tamanho $n$. $C(2n,n)$ é o número de subconjuntos de
				      tamanho $n$ de $A\cup B$. E:
              \begin{itemize}
               \item $C(n,0)^2=C(n,0)C(n,n)$ é o número de subconjuntos de tamanho $n$ de $A\cup B$, com $0$ elementos
							       de $A$ e $n$ elementos de $B$;
               \item $C(n,1)^2=C(n,1)C(n,n-1)$ é o número de subconjuntos de tamanho $n$ de $A\cup B$, com $1$ elemento
							       de $A$ e $n-1$ elementos de $B$;
               \item $\vdots$
               \item $C(n,n)^2=C(n,n)C(n,0)$ é o número de subconjuntos de tamanho $n$ de $A\cup B$, com $n$ elementos
							       de $A$ e $0$ elementos de $B$.
              \end{itemize}
        \item Sejam $A$ e $B$ dois conjuntos disjuntos, $A$ de tamanho $m$ e $B$ de tamanho $n$. $C(m+n,r)$ é o número
				      de subconjuntos de tamanho $r$ de $A\cup B$. E:
              \begin{itemize}
               \item $C(m,0)C(n,r)$ é o número de subconjuntos de tamanho $r$ de $A\cup B$, com $0$ elementos de $A$
							       e $r$ elementos de $B$;
               \item $C(m,1)C(n,r-1)$ é o número de subconjuntos de tamanho $r$ de $A\cup B$, com $1$ elemento de $A$
							       e $r-1$ elementos de $B$;
               \item $\vdots$
               \item $C(m,r)C(n,0)$ é o número de subconjuntos de tamanho $r$ de $A\cup B$, com $r$ elementos
							       de $A$ e $0$ elementos de $B$.
              \end{itemize}
       \end{list}

 \item {\footnotesize Avalie, usando o teorema binomial:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^{n}2^kC(n,k)$.
        \item $\sum_{k=0}^{n}k3^kC(n,k)$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Substituindo-se $x$ por 2: $\sum_{k=0}^{n}2^kC(n,k)=3^n$.
        \item Derivando-se, multiplicando-se por $x$ e substituindo-se $x$ por 3: $\sum_{k=0}^{n}k3^kC(n,k)=3n.4^{n-1}$.
       \end{list}
\end{enumerate}

\vspace*{4mm}
\noindent{\bf Funções Geradoras}
 
\vspace*{2mm}
\begin{enumerate}
 \item[18.] {\footnotesize Apresente funções geradoras para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O número de sequências binárias de $r$ dígitos.
        \item O número de multiconjuntos de $r$ elementos tomados de $\{x_1,x_2,\ldots,x_n\}$.
        \item O número de multiconjuntos de $r$ elementos tomados de $\{x_1,x_2,\ldots,x_n\}$,
              nos quais cada elemento aparece pelo menos uma vez.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $1+2x+2^2x^2+2^3x^3+\cdots=\sum_{r\geq 0}2^rx^r$.
        \item $C(n-1+0,0)+C(n-1+1,1)x+C(n-1+2,2)x^2+C(n-1+3,3)x^3+\cdots=
               \sum_{r\geq 0}C(n-1+r,r)x^r$.
        \item $C(n-1+0,0)x^n+C(n-1+1,1)x^{n+1}+C(n-1+2,2)x^{n+2}+\cdots=
              \sum_{r\geq n}C(n-1+r-n,r-n)x^r=\sum_{r\geq n}C(r-1,r-n)x^r$.
       \end{list}

 \item[19.] {\footnotesize Apresente funções geradoras para os seguintes problemas de equações inteiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+x_3+x_4+x_5=r$, com $x_1+x_2=6$ e $x_k\geq 0$.
        \item $x_1+x_2+x_3<r$, com $k\leq x_k<2k$.
        \item $2x_1+3x_2+5x_3=r$, com $x_k>k$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O número de soluções para $x_1+x_2=6$, com $x_k\geq 0$, é $C(2-1+6,6)$. Logo, o número de soluções é $C(7,6)$
              multiplicado pelo número de soluções para $x_3+x_4+x_5=r$, com $x_3,x_4,x_5\geq 2$ (``distribuindo-se''
							6 igualmente entre as variáveis). Assim, a função geradora é
							$C(7,6)\times(x^2+x^3+x^4+\cdots)^3=7x^6(1+x+x^2+\cdots)^3$.
        \item O número de soluções é o mesmo que para $x_1+x_2+x_3+x_4=r$, com $1\leq x_1< 2$, $2\leq x_2< 4$,
				      $3\leq x_3< 6$ e $x_4\geq 1$. Assim, a função geradora é $x(x^2+x^3)(x^3+x^4+x^5)(x+x^2+x^3+\cdots)$.
        \item O número de soluções é o mesmo que para $y_1+y_2+y_3=r$, com $y_1=4,6,8,\ldots$, $y_2=9,12,15,\ldots$,
				      $y_3=20,25,30,\ldots$. Assim, a função geradora é $(x^4+x^6+x^8+\cdots)(x^9+x^{12}+x^{15}+\cdots)
							(x^{20}+x^{25}+x^{30}+\cdots)$.
       \end{list}

 \item[20.] {\footnotesize Encontre a função geradora para o número de maneiras em que o lançamento de
       3 dados distintos pode produzir um soma de, no máximo, $r$.}

       \textit{Solução}: O problema equivale a encontrar a função geradora para o número de soluções inteiras de
			 $x_1+x_2+x_3\leq r$, com $1\leq x_k\leq 6$, que é o número de soluções inteiras para $x_1+x_2+x_3+y=r$, com
			 $1\leq x_k\leq 6$ e $y\geq 0$. Assim, a função geradora é $(x+x^2+x^3+x^4+x^5+x^6)^3(1+x+x^2+\cdots)$.

 \item[21.] {\footnotesize Encontre os coeficientes dos seguintes termos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x^{24}$ em $(x^3+x^4+\cdots+x^{12})^4$.
        \item $x^{6}$ em $(x+x^2+\cdots)^2(1-x^{3})^3$.
        \item $x^{5}$ em $(1-x^2)^{12}/(1-x)^3$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item  \begin{eqnarray*}
                \lefteqn{(x^3+x^4+\cdots+x^{12})^4} \\
                 & & =x^{12}(1+x^2+x^3\cdots+x^9)^4
                       =x^{12}(1-x^{10})^4(1+x+x^2\cdots)^4 \\
                 & & =x^{12}(C(4,0)-C(4,1)x^{10}+C(4,2)x^{20}-C(4,3)x^{30}+
                     C(4,4)x^{40}) \\
                 & & \;\;\;\;\;\;\;\;\, (C(4-1+0)+C(4-1+1,1)x+C(4-1+2,2)x^2+\cdots)
              \end{eqnarray*}
              
              Coeficiente de $x^{24}$: $C(4,0)C(4-1+12,12)-C(4,1)C(4-1+2,2)=415$.
        
        \item \begin{eqnarray*}
                \lefteqn{(x+x^2+\cdots)^2(1-x^{3})^3 = x^2(1+x+x^2\cdots)^2
                 (1-x^3)^3} \\
                  & & =x^2(C(2-1+0)+C(2-1+1,1)x+C(2-1+2,2)x^2+\cdots) \\
                  & & \;\;\;\;\;\;\; (C(3,0)-C(3,1)x^{3}+C(3,2)x^{6}-C(3,3)x^{9})
              \end{eqnarray*}
              
              Coeficiente de $x^{6}$: $C(2-1+4,4)C(3,0)-C(2-1+1,1)C(3,1)=-1$.
        
        \item \begin{eqnarray*}
                \lefteqn{(1-x^2)^{12}/(1-x)^3 = (1-x^2)^{12}(1+x+x^2\cdots)^3}
                    \\
                  & & =(C(12,0)-C(12,1)x^{2}+C(12,2)x^{4}-\cdots+C(12,12)x^{24})
                        \\
                  & & \;\;\;\; (C(3-1+0)+C(3-1+1,1)x+C(3-1+2,2)x^2+\cdots)
              \end{eqnarray*}
              
              Coeficiente de $x^5$: $C(12,0)C(3-1+5,5)-C(12,1)C(3-1+3,3)+
              C(12,2)C(3-1+1,1)=99$.
       \end{list}

 \item[22.] {\footnotesize Encontre funções geradoras para os seguintes $a_n$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_n=3n-4$.
        \item $a_n=n(n-1)$.
        \item $a_n=n^4$.
        \item $a_n=n^23^n$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_n=3n-4$.
        
              FG para $1$: $1/(1-x)$.
        
              FG para $n$: $x(1/(1-x))'=x/(1-x)^2$.
        
              FG para $3n$: $3x/(1-x)^2$.
        
              FG para $3n-4$: $3x/(1-x)^2-4/(1-x)=(7x-4)/(1-x)^2$.
        
        \item $a_n=n(n-1)$.
        
              FG para $n-1$: $x/(1-x)^2-1/(1-x)=(2x-1)/(1-x)^2$.
        
              FG para $n(n-1)$: $x[(2x-1)/(1-x)^2]'=2x^2/(1-x)^3$.
        
        \item $a_n=n^4$.
        
              FG para $n^2$: $x[x/(1-x)^2]'=(x+x^2)/(1-x)^3$.
        
              FG para $n^3$: $x[(x+x^2)/(1-x)^3]'=(x^3+4x^2+x)/(1-x)^4$.
        
              FG para $n^4$: $x[(x^3+4x^2+x)/(1-x)^4]'=(x^4+11x^3+11x^2+x)/
                             (1-x)^5$.
        
        \item $a_n=n^23^n$.
        
              FG para $3^n$: $1/(1-3x)$.
        
              FG para $n3^n$: $x[1/(1-3x)]'=3x/(1-3x)^2$.
        
              FG para $n^23^n$: $x[3x/(1-3x)^2]'=3x(1+3x)/(1-3x)^3$.
        
       \end{list}


 \item[23.] {\footnotesize Use as funções geradoras do exercício anterior para avaliar as seguintes somas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^n(3k-4)$.
        \item $2\times 1+3\times 2+\cdots+n(n-1)$.
        \item $\sum_{k=1}^n n^4$.
        \item $3+2^23^2\cdots+n^23^n$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item FG para $3n-4$: $(7x-4)/(1-x)^2$.

              FG para $\sum_{k=0}^{n}(3k-4)$: $(7x-4)/(1-x)^3=(7x-4)[C(3-1+0)+C(3-1+1,1)x+C(3-1+2,2)x^2+\cdots]$.
							O coeficiente de $x^n$ é $7C(3-1+n-1,n-1)-4C(3-1+n,n)=(n+1)(3n-8)/2$.
        
        \item FG para $n(n-1)$: $2x^2/(1-x)^3$.
        
              FG para $\sum_{k=0}^{n}[k(k-1)]$: $2x^2/(1-x)^4=2x^2[C(4-1+0,0)+C(4-1+1,1)x+C(4-1+2,2)x^2+\cdots]$.
							O coeficiente de $x^n$ é $2C(4-1+n-2,n-2)=2C(n+1,n-2)=n(n^2-1)/3$.

        \item FG para $n^4$: $(x^4+11x^3+11x^2+x)/(1-x)^5$.
        
              FG para $\sum_{k=0}^{n}k^4$: $(x^4+11x^3+11x^2+x)/(1-x)^6=(x^4+11x^3+11x^2+x)[C(6-1+0,0)+C(6-1+1,1)x+
							C(6-1+2,2)x^2+\cdots]$. O coeficiente de $x^n$ é $C(6-1+n-4,n-4)+11C(6-1+n-3,n-3)+11C(6-1+n-2,n-2)+
							C(6-1+n-1,n-1)=C(n+1,n-4)+11C(n+2,n-3)+11C(n+3,n-2)+C(n+4,n-1)=n(n+1)(6n^3+9n^2+n-1)/30$.

        \item FG para $n^23^n$: $3x(1+3x)/(1-3x)^3$.
        
              FG para $\sum_{k=0}^{n}[k^23^k]$: $3x(1+3x)/(1-3x)^3(1-x)$. Decompondo em frações parciais, obtém-se
              $[3/(1-3x)^3]-[6/(1-3x)^2]+[9/2(1-3x)]-[3/2(1-x)]= 3(1+(3x)+(3x)^2+\cdots)^3-6(1+(3x)+(3x)^2+\cdots)^2+
              (9/2)(1+(3x)+(3x)^2+\cdots)-(3/2)(1+x+x^2+\cdots)$. O coeficiente de $x^n$ é $3C(3-1+n,n)3^n-
							6C(2-1+n,n)3^n+(9/2)3^n-(3/2)=[3^{n+1}(n^2-n+1)-3]/2$.
       \end{list}

 \item[24.] {\footnotesize Utilizando funções geradoras, determine o número de soluções
       inteiras para as seguintes equações:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+x_3+x_4=10$, com $1\leq x_i\leq 6$.
        \item $x_1+x_2+x_3=6$, com $1\leq x_1\leq 5$, $x_2\geq 2$ e $x_3\geq 3$.
        \item $x_1+x_2+x_3+x_4\leq 10$, com $1\leq x_i\leq 10$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Função geradora:
              
              \begin{eqnarray*}
                \lefteqn{(x+x^2+x^3+x^4+x^5+x^6)^4=x^4(1+x+x^2+x^3+x^4+x^5)^4}
                   \\
                  & & =x^4(1-x^6)^4(1+x+x^2+\cdots)^4 \\
                  & & =x^4(C(4,0)-C(4,1)x^{6}+C(4,2)x^{12}-C(4,3)x^{18}+
                        C(4,4)x^{24}) \\
                  & & \;\;\;\;\;\;\; (C(4-1+0)+C(4-1+1,1)x+C(4-1+2,2)x^2+\cdots)
              \end{eqnarray*}
              
              Coeficiente de $x^{10}$: $C(4,0)C(4-1+6,6)-C(4,1)C(4-1+0,0)=C(9,6)-4=80$.
        
        \item Função geradora: $(x+x^2+x^3+x^4+x^5)(x^2+x^3+\cdots)(x^3+x^4+\cdots)=x^6(1+x+x^2+x^3+x^4)(1+x+x^2+\cdots)^2=
              x^6(1+x+x^2+x^3+x^4)[C(2-1+0,0)+C(2-1+1,1)x+C(2-1+2,2)x^2+\cdots)]$.
              
              Coeficiente de $x^{6}$: $1\times 1\times C(1,0)=1$.
        
        \item Função geradora: $(x+x^2+\cdots+x^{10})^4(1+x+x^2+\cdots)=x^4(1+x+x^2+\cdots+x^9)^4(1+x+x^2+\cdots)=
				      x^4(1-x^{10})^4(1+x+x^2+\cdots)^5=x^4[C(4,0)-C(4,1)x^{10}+C(4,2)x^{20}-C(4,3)x^{30}+C(4,4)x^{40}]
							[C(5-1+0,0)+C(5-1+1,1)x+C(5-1+2,2)x^2+\cdots)]$.
              
              Coeficiente de $x^{10}$: $C(4,0)C(5-1+6,6)=C(10,6)=210$.
       \end{list}

 \item[25.] {\footnotesize De quantas maneiras se pode distribuir $13$ reais a 30 crianças, se cada
       criança recebe no máximo 2 reais?}

       \textit{Solução}: A resposta é o número de soluções inteiras para $x_1+\cdots+x_{30}=13$,
			 com $x_i\leq 2$. A função geradora é $(1+x+x^2)^{30}=(1+x+x^2+\cdots)^{30}(1-x^3)^{30}=
       [C(30-1+0,0)+C(30-1+1,1)x+\cdots][C(30,0)-C(30,1)x^3+C(30,2)x^6+\cdots+(-1)^{30}C(30,30)x^{90}]$.
       
       Coeficiente de $x^{13}$: $C(30-1+1,1)C(30,12)-C(30-1+4,4)C(30,9)+C(30-1+7,7)C(30,6)-C(30-1+10,10)C(30,3)
			 +C(30-1+13,13)C(30,0)$.

       \textbf{Atenção: falta conferir esta solução.}
% Townsend 3.4, pag. 116, ex. 7

 \item[26.] {\footnotesize Quantas maneiras existem de distribuir 20 cédulas de 1 real a 10 meninas e $r$ meninos,
       se cada menina recebe no mínimo 1 real e cada menino recebe no máximo 3 reais?}

       \textit{Solução}: A resposta é o número de soluções inteiras para $x_1+\cdots+x_{10}+y_1+\cdots+y_r=20$,
			 com $x_i\geq 1$ e $y_k\leq 3$. A função geradora é $(x+x^2+x^3+\cdots)^{10}(1+x+x^2+x^3)^r=
       x^{10}(1+x+x^2+\cdots)^{10}(1-x^4)^r(1+x+x^2+\cdots)^r=x^{10}(1-x^4)^r(1+x+x^2+\cdots)^{10+r}=
			 x^{10}[C(r,0)-C(r,1)x^4+C(r,2)x^8-\cdots+(-1)^rC(r,r)x^{4r}][C(r+10-1+0,0)+C(r+10-1+1,1)x+\cdots]$.
       
       Coeficiente de $x^{20}$: $C(r,0)C(r+10-1+10,10)-C(r,1)C(r+10-1+6,6)+C(r,2)C(r+10-1+2,2)=C(r+19,10)-
			 rC(r+15,6)+(r(r-1)/2)C(r+11,2)$.

 \item[27.] {\footnotesize Use função geradora para encontrar o número de maneiras de pintar 20 quartos
       idênticos de um hotel com 5 cores, se existe tintas das cores azul, cor-de-rosa e verde suficientes para
			 pintar no máximo 3 quartos (para cada uma das cores).}

       \textit{Solução}: A função geradora é $(1+x+x^2+x^3)^3(1+x+x^2+\cdots)^2$. O coeficiente de $x^{20}$:
			 $C(3,0)C(5-1+20,20)-C(3,1)C(5-1+16,16)+C(3,2)C(5-1+12,12)-C(3,3)C(5-1+8,8)$.

 \item[28.] {\footnotesize Quantas maneiras existem de selecionar $4r$ bolas a partir de $2r$ bolas vermelhas idênticas,
       $2r$ bolas verdes idênticas e $2r$ bolas brancas idênticas?}

       \textit{Solução}: A resposta é o número de soluções inteiras para $x_1+x_2+x_3=4r$, com $0\leq x_i\leq 2r$.
       A função geradora é $(1+x+x^2+\cdots+x^{2r})^3$. Isto é igual a $(1-x^{2r+1})^3(1+x+x^2+\cdots)^3$, que é igual a
			 $[C(3,0)-C(3,1)x^{2r+1}+C(3,2)x^{4r+2}+C(3,3)x^{6r+3}]\times[C(3-1+0,0)+C(3-1+1,1)x+C(3-1+2,2)x^2+\cdots]$.

       Coeficiente de $x^{4r}$: $C(3,0)C(3-1+4r,4r)-C(3,1)C(3-1+2r-1,2r-1)$.

\end{enumerate}

\end{document}
