\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage[magyar]{babel}

\setlength{\hoffset}{-3 cm}
\setlength{\voffset}{-4 cm}
\addtolength{\textwidth}{5 cm}
\addtolength{\textheight}{8 cm}

\newcommand{\Komp}{\overline}


\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
2. Gyakorlat
}
\end{center}

\large
\begin{enumerate}
\item Igazoljuk, hogy $\binom{n-1}{k-1}+\binom{n-1}k = \binom nk$. 

\item Mennyi egy $n$ elemű halmaz összes részhalmazainak száma?
Mennyi egy $n$ elemű halmaz összes $k$ elemű részhalmazainak száma?

\item Bizonyítsuk be az előbbi feladat felhasználásával, hogy 
$\sum_{k=0}^n \binom nk = 2^n$. Igazoljuk ugyanezt a binomiális 
tétel segítségével! Végül próbáljuk meg indukcióval is megmutatni 
az állítást!

\item Bizonyítsuk be, hogy $\sum_{k=0}^n (-1)^k \binom nk = 0$.

\item Egy 15 tagú klub elnököt, titkárt és jegyzőt választ. Hányféleképpen 
tehetik ezt meg, ha a népszerű (és befolyásos) Kovács úrnak mindenképpen 
szeretnének valamilyen tisztséget adni?

\item Egy négyzetrács $(0,0)$ pontjából a rácsegyenesek mentén jobbra 
vagy felfele lépve hányféleképpen juthatunk el az $(u,v)$  pontba?

\item Hányféleképp fedhető le a $2 \times k$-as téglalap $k$ darab 
$2 \times 1$-es dominóval? (Útmutatás: próbálkozzunk rekurzióval.)

\item Van-e olyan összefüggő gráf, amelyben:
\begin{enumerate}
\item pontosan egy legolcsóbb él van, és az nem minden 
minimális összsúlyú feszítőfában szerepel;
\item pontosan négy legdrágább él van, és mindegyik szerepel 
minden minimális összsúlyú fában;
\item pontosan négy legdrágább él van, és a minimális feszítőfák
között van olyan, amelyben mind a négy szerepel, és van olyan is,
amelyben nem mindegyik?
\end{enumerate}

\item Hány különböző minimális súlyú feszítőfája van az alábbi
gráfoknak:
\vskip 3 cm

\item Mely fák Prüfer kódjai a $447741$ illetve a $224447$ sorozatok?

\item Egy $F$ fa Prüfer-kódja csupa különböző számból áll. Hogyan 
jellemezhetjük $F$-et?

\item Egy $F$ fa Prüfer-kódja csupa azonos számból áll. Hogyan 
jellemezhetjük $F$-et?

\end{enumerate}
 
\end{document}
