%\documentclass[dvips,12pt]{amsart}
\documentclass[pdftex,12pt]{amsart}
\usepackage{amsmath}
\usepackage[portuges]{babel}
\usepackage{enumerate}

\usepackage{hyperref}
\def\hbref#1#2#3{\href{#1#2}{#3}}

\def\crseurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/lpii}

\def\cwurl{\crseurl/page/cw/0/}

\def\inmacros#1{\input{$HOME/tex/macros/#1}}

\inmacros{defport}
\inmacros{deflogic}
\inmacros{defseqs}

\def\course{Projeto e An\'alise Algoritmos}
\def\thisdoc{Lista $\mathcal{CA}_0$}
\title{\course\\ \thisdoc}



\author{Raul H.C. Lopes}
\def\radixsort{\emph{radix sort}}
\def\splitter{\emph{splitter}}
\def\quicksort{\emph{quick sort}}
\def\mergesort{\emph{merge sort}}
\def\prefsum{prefix sum}
\def\real{Real}

\def\loop{\emph{loop}}

\def\scref#1{sc. \ref{#1}}
\def\exref#1{ex. \ref{ex:#1}}
\def\tabref#1{tab. \ref{tab:#1}}
\def\stdin{\emph{stdin}}

\begin{document}

\maketitle

\section{Introdu\c{c}\~ao}
Os seguintes exerc\'{\i}cios ser\~ao usados como roteiro de aula. 

\section{Os exerc\'{\i}cios}

\begin{ex}
	Quantos n\'umeros de nove d\'{\i}gitos cont\^em o d\'{\i}gito $1$?
\end{ex}

\begin{ex}
	Calcule o n\'umero de subconjuntos de um conjunto de $n$ elementos.
\end{ex}


\begin{ex}
	Qual \'e o n\'umero de endere\c cos dispon\'{\i}veis no protocolo 
	\textbf{IPV4}?
\end{ex}

\begin{ex}
	Dado um conjunto de cardinalidade $n$, calcule o n\'umero de 
	sele\c c\~oes ordenadas de $r$ elementos do mesmo.
\end{ex}


\begin{ex}
	\label{ex:tsp0}
	Calcule o n\'umero de arranjos poss\'{\i}veis para sentar $n$ pessoas
	em uma fila.
\end{ex}

\begin{ex}
	\label{ex:tsp1}
	Calcule o n\'umero de arranjos poss\'{\i}veis para sentar $n$ pessoas
	em um c\'{\i}rculo.
\end{ex}

\def\tsp{\textbf{TSP}}
\begin{ex}
	\label{ex:tsp2}
	Relacione os resultados de \exref{tsp0} e \exref{tsp1} com a complexidade
	de solu\c c\~ao od \tsp.
\end{ex}

\begin{ex}
	Calcule a quantidade de n\'umeros inteiros com dois d\'{\i}gitos. 
\end{ex}

\begin{ex}
	Dado um conjunto de cardinalidade $n$, calcule o n\'umero de 
	sele\c c\~oes ordenadas de $r$ elementos do mesmo, usando a regra da soma.
\end{ex}

\begin{ex}
	Calcule o n\'umero de \textit{interleavings} de um conjunto de $m$
	\textit{threads}.
\end{ex}

\begin{ex}
	Dado um conjunto de $n$ elementos, calcule o n\'umero de $r$-sele\c c\~oes
	ordenadas, adimitindo-se repeti\c c\~ao irrestrita. 
\end{ex}

\begin{ex}\label{ex:rcombs}
	Dado um conjunto de $n$ elementos, calcule o n\'umero de $r$-sele\c c\~oes
	n\~ao ordenadas.
\end{ex}

\begin{ex}
	Use exref{rcombs}, para calcular o n\'umero de subconjuntos de um conjunto.
\end{ex}

\section{Argumento combinatorial}
Apresente ao menos duas  provas, usando argumento combinatorial e alg\'ebrico,
para cada uma das identidades abaixo.
\begin{ex}
	$$\binom nr = \binom n{n-r}$$
\end{ex}

\begin{ex}
	$$\bndmsum{\lele0ir}{\binom{n+i}{i}}=\binom{n+r+1}{r}$$
\end{ex}

\begin{ex}
	$$\binom nr \binom rk = \binom nk\binom{n-k}{r-k}$$
\end{ex}

\begin{ex}
	$$(x+y)^n = \bndmsum{\lele 0in}{\binom ni x^{n-i}y^i}$$
\end{ex}

\begin{ex}
	$$\bndmsum{\lele 0in}{\binom ni} = 2^n$$
\end{ex}

\begin{ex}
	$$\bndmsum{\lele 0in}{(-1)^i\binom ni} = 0$$
\end{ex}

\begin{ex}
	$$\binom{n+m}r = \bndmsum{\lele 0ir}{\binom ni\binom m{r-i}}$$
\end{ex}

\begin{ex}
	$$\binom{n+m}n = \bndmsum{\lele 0in}{\binom mi \binom ni}$$
\end{ex}


\end{document}

