1 files changed, 7105 insertions, 0 deletions
diff --git a/šola/komb/teor.lyx b/šola/komb/teor.lyx
new file mode 100644
index 0000000..5f60d51
--- /dev/null
+++ b/šola/komb/teor.lyx
@@ -0,0 +1,7105 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass article
+\begin_preamble
+\usepackage{hyperref}
+\usepackage{siunitx}
+\usepackage{pgfplots}
+\usepackage{listings}
+\usepackage{multicol}
+\sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}}
+\usepackage{amsmath}
+\usepackage{tikz}
+\newcommand{\udensdash}[1]{%
+    \tikz[baseline=(todotted.base)]{
+        \node[inner sep=1pt,outer sep=0pt] (todotted) {#1};
+        \draw[densely dashed] (todotted.south west) -- (todotted.south east);
+    }%
+}%
+\DeclareMathOperator{\Lin}{\mathcal Lin}
+\DeclareMathOperator{\rang}{rang}
+\DeclareMathOperator{\sled}{sled}
+\DeclareMathOperator{\Aut}{Aut}
+\DeclareMathOperator{\red}{red}
+\DeclareMathOperator{\karakteristika}{char}
+\DeclareMathOperator{\Ker}{Ker}
+\DeclareMathOperator{\Slika}{Ker}
+\DeclareMathOperator{\sgn}{sgn}
+\DeclareMathOperator{\End}{End}
+\DeclareMathOperator{\n}{n}
+\DeclareMathOperator{\Col}{Col}
+\usepackage{algorithm,algpseudocode}
+\providecommand{\corollaryname}{Posledica}
+\usepackage[slovenian=quotes]{csquotes}
+\end_preamble
+\use_default_options true
+\begin_modules
+enumitem
+theorems-ams
+theorems-ams-extended
+\end_modules
+\maintain_unincluded_children no
+\language slovene
+\language_package default
+\inputencoding auto-legacy
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement H
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref true
+\pdf_bookmarks true
+\pdf_bookmarksnumbered false
+\pdf_bookmarksopen false
+\pdf_bookmarksopenlevel 1
+\pdf_breaklinks false
+\pdf_pdfborder false
+\pdf_colorlinks false
+\pdf_backref false
+\pdf_pdfusetitle true
+\papersize default
+\use_geometry true
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification false
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\leftmargin 2cm
+\topmargin 2cm
+\rightmargin 2cm
+\bottommargin 2cm
+\headheight 2cm
+\headsep 2cm
+\footskip 1cm
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style german
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Title
+Teorija Kombinatorike —
+ IŠRM 2024/25
+\end_layout
+
+\begin_layout Author
+
+\noun on
+Anton Luka Šijanec
+\end_layout
+
+\begin_layout Date
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+today
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Abstract
+Povzeto po zapiskih s predavanj profesorja Konvalinke.
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset toc
+LatexCommand tableofcontents
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Osnovni principi kombinatorike
+\end_layout
+
+\begin_layout Standard
+Pri tem predmetu velja 
+\begin_inset Formula $\mathbb{N}\coloneqq\mathbb{N}_{0}$
+\end_inset
+
+ ZDB 
+\begin_inset Formula $0\in\mathbb{N}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Funkcija/preslikava
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $f:X\to Y$
+\end_inset
+
+ je formalno množica parov 
+\begin_inset Formula $f\subseteq X\times Y$
+\end_inset
+
+ s pogojem 
+\begin_inset Formula $\forall x\in X\exists!y\in Y\ni:\left(x,y\right)\in f$
+\end_inset
+
+ ZDB za vsak 
+\begin_inset Formula $x\in X$
+\end_inset
+
+ je 
+\begin_inset Formula $f\left(x\right)$
+\end_inset
+
+ enolično definiran.
+\end_layout
+
+\begin_layout Standard
+Funkcijo podamo tako,
+ da:
+\end_layout
+
+\begin_layout Enumerate
+naštejemo vse elemente 
+\begin_inset Formula $f$
+\end_inset
+
+ —
+ vse pare (puščični diagram med množicama)
+\end_layout
+
+\begin_layout Enumerate
+povemo predpis za preslikanje elementa —
+ 
+\begin_inset Formula $f:\mathbb{N}\to\mathbb{N};x\mapsto x^{2}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+z rekurzijo —
+ 
+\begin_inset Formula $f:\mathbb{N}\to\mathbb{N},f\left(0\right)=1,f\left(1\right)=1,f\left(n\right)=f\left(n-1\right)+f\left(n-2\right)$
+\end_inset
+
+ za 
+\begin_inset Formula $n\geq2$
+\end_inset
+
+ (fibbonaccijevo zaporedje)
+\end_layout
+
+\begin_layout Definition*
+Zaporedje je preslikava iz naravnih števil v katerokoli neprazno množico.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Lastnosti preslikav.
+ Naj bo 
+\begin_inset Formula $f:A\to B$
+\end_inset
+
+ preslikava.
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $f$
+\end_inset
+
+ injektivna 
+\begin_inset Formula $\Leftrightarrow\forall a\in A,b\in B:f\left(a\right)=f\left(b\right)\Rightarrow a=b$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f$
+\end_inset
+
+ surjektivna 
+\begin_inset Formula $\Leftrightarrow\forall a\in A\exists b\in B\ni:f\left(b\right)=a$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f$
+\end_inset
+
+ bijektivna 
+\begin_inset Formula $\Leftrightarrow\forall a\in A\exists!b\in B\ni:f\left(b\right)=a$
+\end_inset
+
+ ZDB 
+\begin_inset Formula $f$
+\end_inset
+
+ injektivna in 
+\begin_inset Formula $f$
+\end_inset
+
+ surjektivna hkrati
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Kombinatorika je odkrivanje moči množic.
+ Tu često želimo dokazati enakost moči dveh množic,
+ najlepše to storimo s konstrukcijo bijekcije,
+ saj velja:
+\end_layout
+
+\begin_layout Theorem*
+Naj bo 
+\begin_inset Formula $f:X\to Y$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f$
+\end_inset
+
+ injektivna 
+\begin_inset Formula $\Rightarrow\left|X\right|\leq\left|Y\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f$
+\end_inset
+
+ surjektivna 
+\begin_inset Formula $\Rightarrow\left|Y\right|\leq\left|X\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f$
+\end_inset
+
+ bijektivna 
+\begin_inset Formula $\Rightarrow\left|X\right|=\left|Y\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Imejmo 
+\begin_inset Formula $n$
+\end_inset
+
+ kroglic in 
+\begin_inset Formula $k$
+\end_inset
+
+ škatel.
+ Vsako kroglico damo v eno od teh škatel.
+ Postavitev kroglic v škatle je preslikava iz množice kroglic v množico škatel (
+\begin_inset Formula $\left\{ 1..5\right\} \to\left\{ a,b,c\right\} $
+\end_inset
+
+).
+ Injektivnost te preslikave pomeni,
+ da ni praznih škatel,
+ surjektivnost pa da je v vsaki škatli vsaj ena kroglica.
+\end_layout
+
+\begin_layout Definition*
+Nekaj oznak v kombinatoriki:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\mathbb{N}\coloneqq\left\{ 0,1,2,\dots\right\} \sim$
+\end_inset
+
+ možne moči končnih množic
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\left[n\right]\coloneqq\left\{ 1..n\right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula $\left[0\right]\coloneqq\emptyset$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\left|\left[n\right]\right|=n$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+množica podmnožic 
+\begin_inset Formula $A$
+\end_inset
+
+ (potenčna množica 
+\begin_inset Formula $A$
+\end_inset
+
+) 
+\begin_inset Formula $\eqqcolon2^{A}$
+\end_inset
+
+,
+ velja 
+\begin_inset Formula $\left|2^{A}\right|=2^{\left|A\right|}$
+\end_inset
+
+,
+ odtod tudi ta oznaka
+\end_layout
+
+\begin_layout Itemize
+množica preslikav 
+\begin_inset Formula $X\to Y\eqqcolon Y^{X}$
+\end_inset
+
+,
+ saj 
+\begin_inset Formula $\left|Y^{X}\right|=\left|Y\right|^{\left|X\right|}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\sum_{k}\sim$
+\end_inset
+
+ vsota po vseh 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\sum_{k\geq a}\sim$
+\end_inset
+
+ vsota po vseh 
+\begin_inset Formula $k\in\mathbb{N},k\geq a$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Theorem*
+Binomski izrek.
+\begin_inset Formula 
+\[
+\left(1+x\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Dirichletovo načelo (angl.
+ Pigeonhole principle)
+\end_layout
+
+\begin_layout Standard
+Če obstaja injekcija 
+\begin_inset Formula $X\to Y$
+\end_inset
+
+,
+ je 
+\begin_inset Formula $\left|X\right|\leq\left|Y\right|$
+\end_inset
+
+.
+ Če torej 
+\begin_inset Formula $\left|X\right|\geq\left|Y\right|$
+\end_inset
+
+,
+ ne obstaja injekcija 
+\begin_inset Formula $X\to Y$
+\end_inset
+
+.
+ Če imamo 
+\begin_inset Formula $n$
+\end_inset
+
+ kroglic v 
+\begin_inset Formula $k$
+\end_inset
+
+ škatlah in 
+\begin_inset Formula $n>k$
+\end_inset
+
+,
+ bosta gotovo vsaj v eni škatli vsaj dve kroglici.
+\end_layout
+
+\begin_layout Paragraph
+Uporaba načela
+\end_layout
+
+\begin_layout Itemize
+ob trinajstih ljudeh imata vsaj dva rojstni dan v istem mesecu.
+ Kroglice so ljudje,
+ škatle so meseci,
+ preslikava je iz človeka v mesec rojstva.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $X\subseteq\mathbb{N}$
+\end_inset
+
+;
+ 
+\begin_inset Formula $\left|X\right|=n+1$
+\end_inset
+
+.
+ 
+\begin_inset Formula $\exists x,y\in X\ni:n\vert\left(x-y\right)\wedge x\not=y$
+\end_inset
+
+.
+ Trditev je ekvivalentna temu,
+ da sta v 
+\begin_inset Formula $X$
+\end_inset
+
+ dve števili z istim ostankom pri deljenju z 
+\begin_inset Formula $n$
+\end_inset
+
+.
+ Kroglice so števila,
+ škatle so možni ostanki pri deljenju z 
+\begin_inset Formula $n$
+\end_inset
+
+.
+ Preslikava 
+\begin_inset Formula $x\mapsto x\mod n$
+\end_inset
+
+.
+ Kroglic je 
+\begin_inset Formula $n+1$
+\end_inset
+
+,
+ škatel je 
+\begin_inset Formula $n\Rightarrow$
+\end_inset
+
+ po dirichletu trditev velja.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $n$
+\end_inset
+
+ ljudi.
+ Trdimo,
+ da 
+\begin_inset Formula $\exists2$
+\end_inset
+
+ človeka,
+ ki poznata enako število ljudi.
+ Imamo torej 
+\begin_inset Formula $n$
+\end_inset
+
+ kroglic —
+ ljudi in 
+\begin_inset Formula $n$
+\end_inset
+
+ škatel —
+ št.
+ poznanstev (
+\begin_inset Formula $\in\left\{ 0..\left(n-1\right)\right\} $
+\end_inset
+
+).
+ Preslikava preslika človeka v število njegovih znancev.
+ Sicer velja 
+\begin_inset Formula $n=n$
+\end_inset
+
+,
+ toda ne moremo imeti hkrati nekoga,
+ ki pozna 0 oseb in hkrati nekoga,
+ ki pozna 
+\begin_inset Formula $n-1$
+\end_inset
+
+ oseb,
+ torej je število različnih poznanstev največ 
+\begin_inset Formula $n-1$
+\end_inset
+
+.
+ Dirichlet pove,
+ da obstaja dve osebi,
+ ki poznata enako število ljudi.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $X\subseteq\left\{ 1..100\right\} $
+\end_inset
+
+;
+ 
+\begin_inset Formula $\left|X\right|=10$
+\end_inset
+
+.
+ Trdimo,
+ da obstajata dve disjunktni podmnožici 
+\begin_inset Formula $X$
+\end_inset
+
+,
+ ki imata enako vsoto.
+ Kroglice so podmnožice 
+\begin_inset Formula $X$
+\end_inset
+
+ —
+ 
+\begin_inset Formula $2^{10}=1024$
+\end_inset
+
+ jih je.
+ Škatle so možne vsote elementov,
+ torej 
+\begin_inset Formula $\in\left\{ 55..955\right\} $
+\end_inset
+
+.
+ Injekcije iz podmnožic 
+\begin_inset Formula $X$
+\end_inset
+
+ dolžine 10 v možne vsote po dirichletu ni,
+ zato obstajata vsaj dve podmnožici,
+ ki imata isto vsoto.
+ Če sta nedisjunktni,
+ jima odstranimo presek,
+ pa dobimo disjunktni,
+ ne da bi spremenili vsoto elementov.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $X\subseteq\left\{ 1..2n\right\} $
+\end_inset
+
+;
+ 
+\begin_inset Formula $\left|X\right|=n+1$
+\end_inset
+
+.
+ Trdimo,
+ da 
+\begin_inset Formula $\exists x,x'\in X\ni:x|x'\wedge x\not=x'$
+\end_inset
+
+.
+ Kroglice so 
+\begin_inset Formula $X$
+\end_inset
+
+.
+ Za katerokoli število velja 
+\begin_inset Formula $x=2^{a}\cdot b$
+\end_inset
+
+,
+ kjer je 
+\begin_inset Formula $b$
+\end_inset
+
+ liho.
+ Škatle so liha števila v 
+\begin_inset Formula $\left[2n\right]$
+\end_inset
+
+.
+ Preslikava slika 
+\begin_inset Formula $x\to b$
+\end_inset
+
+ za 
+\begin_inset Formula $b$
+\end_inset
+
+ od prej.
+ Ker je kroglic več kot škatel,
+ velja 
+\begin_inset Formula $\exists x,x'\in X\ni:x=2^{a}b\wedge x'=2^{a'}b$
+\end_inset
+
+.
+ Če je 
+\begin_inset Formula $a<a'$
+\end_inset
+
+,
+ je 
+\begin_inset Formula $x'\vert x$
+\end_inset
+
+,
+ sicer je 
+\begin_inset Formula $x\vert x'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Načelo vsote in produkta
+\end_layout
+
+\begin_layout Theorem*
+Načelo vsote.
+ Naj bosta 
+\begin_inset Formula $A,B$
+\end_inset
+
+ množici.
+ Če sta disjunktni,
+ 
+\begin_inset Formula $\left|A\cup B\right|=\left|A\right|+\left|B\right|$
+\end_inset
+
+.
+ Če nista nujno disjunktni,
+ velja 
+\begin_inset Formula $\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|$
+\end_inset
+
+.
+ Splošneje:
+ 
+\begin_inset Formula $A_{1},\dots,A_{n}$
+\end_inset
+
+ disjunktne 
+\begin_inset Formula $\Rightarrow\left|\bigcup_{k=1}^{n}A_{k}\right|=\sum_{k=1}^{n}\left|A_{k}\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Interpretacija:
+ Če so elementi množice bodisi tipa 1 bodisi tipa 2 (ne pa obeh hkrati),
+ je skupno število vsota števila elementov tipa 1 in števila elementov tipa 2.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Načelo produkta.
+ Naj bosta 
+\begin_inset Formula $A,B$
+\end_inset
+
+ množici.
+ 
+\begin_inset Formula $\left|A\times B\right|=\left|A\right|\cdot\left|B\right|$
+\end_inset
+
+.
+ Splošneje:
+ 
+\begin_inset Formula $A_{1},\dots,A_{n}$
+\end_inset
+
+ množice 
+\begin_inset Formula $\Rightarrow\left|\Pi_{k=1}^{n}A_{k}\right|=\Pi_{k=1}^{n}\left|A_{k}\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Interpretacija:
+ Izberemo element iz 
+\begin_inset Formula $A$
+\end_inset
+
+ na toliko načinov,
+ kolikor je elementov 
+\begin_inset Formula $A$
+\end_inset
+
+,
+ nato še neodvisno od prve izbire izberemo element iz 
+\begin_inset Formula $B$
+\end_inset
+
+ itd.
+\end_layout
+
+\begin_layout Example*
+Primeri.
+\end_layout
+
+\begin_layout Itemize
+oblačenje.
+ Bodisi formalno bodisi neformalno (pravilo vsote).
+ Formalna oprava sestoji iz ene izmed enajstih srajc in enih izmed petih hlač,
+ neformalna pa iz ene izmed devetinpetdesetih majic in enih izmed štirih kavbojk (pravili produkta).
+ Možnih oprav je torej 
+\begin_inset Formula $11\cdot5+59\cdot4=55+236=291$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $n-$
+\end_inset
+
+mestna števila,
+ ki vsebujejo štirico in same različne števke.
+ Štirica je lahko na enem izmed 
+\begin_inset Formula $n$
+\end_inset
+
+ mest (pravilo vsote).
+ Za preostale števke pa uporabimo varianto načela produkta,
+ kjer število možnih izbir ni odvisno od prej izbranih elementov.
+ Iskanih števil je 
+\begin_inset Formula $\frac{9!}{\left(10-n\right)!}+\left(n-1\right)\frac{8!\cdot8}{\left(10-n\right)!}$
+\end_inset
+
+ (levi člen za štirico na prvem mestu,
+ desni člen za štirico na preostalih 
+\begin_inset Formula $n-1$
+\end_inset
+
+ mestih).
+\end_layout
+
+\begin_layout Itemize
+figure pri šahu razporedimo po 1.
+ vrsti:
+ 
+\begin_inset Formula $8$
+\end_inset
+
+ za tekača 1 in 
+\begin_inset Formula $7$
+\end_inset
+
+ za tekača 2 (skupaj 
+\begin_inset Formula $56/2$
+\end_inset
+
+ —
+ lovcev medsebojno ne ločimo),
+ 
+\begin_inset Formula $6$
+\end_inset
+
+ za konja 1 in 
+\begin_inset Formula $5$
+\end_inset
+
+ za konja 2 (skupaj 
+\begin_inset Formula $30/2$
+\end_inset
+
+),
+ 
+\begin_inset Formula $4$
+\end_inset
+
+ za trdnjavo 1 in 
+\begin_inset Formula $3$
+\end_inset
+
+ za trdnjavo 2 (skupaj 
+\begin_inset Formula $12/2$
+\end_inset
+
+),
+ 
+\begin_inset Formula $2$
+\end_inset
+
+ za kraljico in 1 za kralja (skupaj 
+\begin_inset Formula $2$
+\end_inset
+
+).
+ Torej je možnih razporeditev 
+\begin_inset Formula $\frac{56}{2}\cdot\frac{30}{2}\cdot\frac{12}{2}\cdot2=5040$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+Fischerjev naključni šah (chess960).
+ Figure so naključno razporejene po prvi vrsti z naslednjimi omejitvami:
+ tekača sta na različnih barvah,
+ kralj je med trdnjavama (da dopustimo rošadi).
+ 
+\begin_inset Formula $4$
+\end_inset
+
+ za tekača 1 in 
+\begin_inset Formula $4$
+\end_inset
+
+ za tekača 2 (skupaj 
+\begin_inset Formula $8$
+\end_inset
+
+),
+ 
+\begin_inset Formula $6$
+\end_inset
+
+ za konja 1 in 
+\begin_inset Formula $5$
+\end_inset
+
+ za konja 2 (skupaj 
+\begin_inset Formula $30/2=15$
+\end_inset
+
+),
+ 
+\begin_inset Formula $4$
+\end_inset
+
+ za kraljico in 1 za trdnjavi in kralja (preostanejo le še tri nedodeljena mesta).
+ Torej je možnih razporeditev = 
+\begin_inset Formula $8\cdot15\cdot4=960$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+dokaži 
+\begin_inset Formula $\left|2^{A}\right|=2^{\left|A\right|}$
+\end_inset
+
+ za končno množico 
+\begin_inset Formula $A\sim$
+\end_inset
+
+ najdi bijekcijo 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ med 
+\begin_inset Formula $\left\{ 0,1\right\} ^{\left|A\right|}\tilde{=}\left\{ 0..2^{\left|A\right|}-1\right\} $
+\end_inset
+
+ in 
+\begin_inset Formula $2^{A}$
+\end_inset
+
+.
+ 
+\begin_inset Formula $\Phi^{-1}\left(B\right)=\left\{ a_{i}\in A;B_{i}=1\right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula $\Phi\left(B\right)=\left(a_{1}\in B,a_{2}\in B,\dots,a_{n}\in B\right)$
+\end_inset
+
+.
+ Velja 
+\begin_inset Formula $\Phi^{-1}\circ\Phi=id$
+\end_inset
+
+ in 
+\begin_inset Formula $\Phi\circ\Phi^{-1}=id$
+\end_inset
+
+.
+ S kombinatoriko pa lahko to dokažemo malce bolj intuitivno.
+ Za vsak element se odločimo,
+ ali je v podmnožici al,i ne.
+ 2 izbiri za vsakega in izbire so neodvisne 
+\begin_inset Formula $\Rightarrow2^{\left|A\right|}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Permutacija 
+\begin_inset Formula $X$
+\end_inset
+
+ je bijekcija 
+\begin_inset Formula $X\to X$
+\end_inset
+
+.
+ Množica permutacij 
+\begin_inset Formula $X$
+\end_inset
+
+ je 
+\begin_inset Formula $S_{X}$
+\end_inset
+
+ ali 
+\begin_inset Formula $S\left(X\right)$
+\end_inset
+
+.
+ Množica permutacij 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ je 
+\begin_inset Formula $S_{\left[n\right]}$
+\end_inset
+
+ ali 
+\begin_inset Formula $S_{n}$
+\end_inset
+
+.
+ Permutacijo zapišemo z dvovrstično notacijo,
+ primer:
+ 
+\begin_inset Formula $\left(\begin{array}{ccccc}
+1 & 2 & 3 & 4 & 5\\
+2 & 4 & 3 & 1 & 5
+\end{array}\right)$
+\end_inset
+
+,
+ ali pa z enovrstično,
+ primer:
+ 
+\begin_inset Formula $\begin{array}{ccccc}
+2 & 4 & 3 & 1 & 5\end{array}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $a_{n}\sim b_{n}$
+\end_inset
+
+ (
+\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$
+\end_inset
+
+ je asimptotsko enako 
+\begin_inset Formula $\left(b_{n}\right)_{n\in\mathbb{N}}$
+\end_inset
+
+) 
+\begin_inset Formula $\Leftrightarrow\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $n!=n\cdot\left(n-1\right)!$
+\end_inset
+
+ za 
+\begin_inset Formula $n\geq1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $0!=1$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Velja 
+\begin_inset Formula $\left|S_{n}\right|=n\cdot\left(n-1\right)\cdot\cdots\cdot\left(n-\left(n-1\right)\right)=n!$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Fact*
+Stirlingova formula.
+ 
+\begin_inset Formula $n!\sim\left(\frac{n}{3}\right)^{n}\cdot\sqrt{2\sqrt{n}}$
+\end_inset
+
+,
+ kjer 
+\begin_inset Formula $\sim$
+\end_inset
+
+ predstavlja asimptotsko enakost.
+\end_layout
+
+\begin_layout Standard
+Permutacije lahko medsebojno komponiramo.
+ Temu pravimo množenje.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\begin{array}{ccccc}
+4 & 1 & 3 & 2 & 5\end{array}\circ\begin{array}{ccccc}
+1 & 4 & 3 & 5 & 2\end{array}=\begin{array}{ccccc}
+4 & 2 & 3 & 5 & 1\end{array}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Za 
+\begin_inset Formula $A$
+\end_inset
+
+ množico vseh permutacij neke množice je 
+\begin_inset Formula $\left(A,\circ\right)$
+\end_inset
+
+ grupa.
+\end_layout
+
+\begin_layout Proof
+Dokažimo le asociativnost,
+ obstoj enote in inverz:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\left(\pi\circ\varphi\right)\circ\tau=\pi\circ\left(\varphi\circ\tau\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\pi\circ id=id\circ\pi=\pi$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\forall\pi\in A\exists\tau\in A\ni:\pi\circ\tau=\tau\circ\pi=id$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Remark*
+Velja 
+\begin_inset Formula $\left|S_{n}\right|=n$
+\end_inset
+
+.
+ Naj bo 
+\begin_inset Formula $\pi\in S_{n}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k\in\left[n\right]$
+\end_inset
+
+.
+ Oglejmo si zaporedje 
+\begin_inset Formula $k,\pi k,\pi^{2}k,\dots$
+\end_inset
+
+.
+ Po dirichletu 
+\begin_inset Formula $\exists i>j\ni:\pi^{i}\left(k\right)=\pi^{j}\left(k\right)\Rightarrow\pi^{j-i}\left(k\right)=k$
+\end_inset
+
+ in imamo ciklično zaporedje 
+\begin_inset Formula $k,\pi k,\pi^{2}k,\dots,k$
+\end_inset
+
+.
+ Cikel označimo z 
+\begin_inset Formula $\left(k,\pi k,\dots,k\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Corollary*
+Vsaka permutacija je produkt disjunktnih ciklov.
+\begin_inset Formula 
+\[
+\left(\begin{array}{cccccccc}
+1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
+4 & 2 & 7 & 6 & 3 & 8 & 1 & 5
+\end{array}\right)=\left(1,4,6,8,5,3,7\right)\left(2\right)=\left(1,4,6,8,5,3,7\right)
+\]
+
+\end_inset
+
+Disjunktni cikli medsebojno komutirajo.
+ Cikel je invarianten za ciklično shiftanje/zamikanje/vrtenje.
+ Do vrstnega reda ciklov in znotrajciklične ureditve je zapis permutacije kot produkt disjunktnih ciklov enoličen.
+\end_layout
+
+\begin_layout Claim*
+Naj bosta 
+\begin_inset Formula $N,K$
+\end_inset
+
+ množici,
+ 
+\begin_inset Formula $\left|N\right|=n,\left|K\right|=k$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Preslikav iz 
+\begin_inset Formula $N$
+\end_inset
+
+ v 
+\begin_inset Formula $K$
+\end_inset
+
+ je 
+\begin_inset Formula $\left|K^{N}\right|=\left|K\right|^{\left|N\right|}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Injektivnih preslikav iz 
+\begin_inset Formula $N$
+\end_inset
+
+ v 
+\begin_inset Formula $K$
+\end_inset
+
+ je 
+\begin_inset Formula $k\left(k-1\right)\left(k-2\right)\cdots\left(k-n+1\right)\eqqcolon k^{\underline{n}}$
+\end_inset
+
+ (pravimo 
+\begin_inset Formula $k$
+\end_inset
+
+ na 
+\begin_inset Formula $n$
+\end_inset
+
+ padajoče)
+\end_layout
+
+\end_deeper
+\begin_layout Proof
+Intuitiven dokaz.
+ Naj bo 
+\begin_inset Formula $N=\left\{ x_{1},\dots,x_{n}\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Za vsak 
+\begin_inset Formula $x_{i}$
+\end_inset
+
+ imamo 
+\begin_inset Formula $k$
+\end_inset
+
+ izbir,
+ kam se bo preslikal in izbire so neodvisne:
+ 
+\begin_inset Formula $k\cdot\cdots\cdot k=k^{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Za 
+\begin_inset Formula $x_{1}$
+\end_inset
+
+ je 
+\begin_inset Formula $k$
+\end_inset
+
+ izbir,
+ za 
+\begin_inset Formula $x_{2}$
+\end_inset
+
+ je 
+\begin_inset Formula $k-1$
+\end_inset
+
+ izbir itd.
+ Če je 
+\begin_inset Formula $\left|K\right|>\left|N\right|$
+\end_inset
+
+,
+ bomo na neki točki vse skupaj množili z 0 in dobili 0,
+ s čimer ustrezamo dirichletu.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+Formalnejši dokaz.
+\end_layout
+
+\begin_layout Enumerate
+Iščemo bijekcijo med 
+\begin_inset Formula $K^{N}$
+\end_inset
+
+ in 
+\begin_inset Formula $\left[k\right]^{n}$
+\end_inset
+
+ TODO XXX FIXME
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Section
+Podmnožice in načrti
+\end_layout
+
+\begin_layout Subsection
+Binomski koeficienti
+\end_layout
+
+\begin_layout Definition*
+Naj bo 
+\begin_inset Formula $k,n\in\mathbb{N}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $A$
+\end_inset
+
+ množica.
+ 
+\begin_inset Formula ${A \choose k}\coloneqq\left\{ B\subseteq A;\left|B\right|=k\right\} $
+\end_inset
+
+ ZDB vse 
+\begin_inset Formula $k-$
+\end_inset
+
+elementne podmnožice 
+\begin_inset Formula $A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula ${\left[4\right] \choose 2}=\left\{ \left\{ 1,2\right\} ,\left\{ 1,3\right\} ,\left\{ 1,4\right\} ,\left\{ 2,3\right\} ,\left\{ 2,4\right\} ,\left\{ 3,4\right\} \right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula ${\left[4\right] \choose 4}=\left\{ \left\{ 1,2,3,4\right\} \right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula ${\left[4\right] \choose 1}=\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3\right\} ,\left\{ 4\right\} \right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula ${\left[4\right] \choose 0}=\left\{ \left\{ \right\} \right\} =\left\{ \emptyset\right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula ${\left[4\right] \choose -1}=\left\{ \right\} =\emptyset$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\bigcup_{k=0}^{\left|A\right|}{A \choose k}=2^{A}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Binomski koeficient/simbol.
+ Naj bo 
+\begin_inset Formula $n,k\in\mathbb{N}$
+\end_inset
+
+.
+ 
+\begin_inset Formula ${n \choose k}\coloneqq\left|{\left[n\right] \choose k}\right|$
+\end_inset
+
+.
+ Rečemo 
+\begin_inset Formula $n$
+\end_inset
+
+ nad 
+\begin_inset Formula $k$
+\end_inset
+
+ (angl.
+ 
+\begin_inset Formula $n$
+\end_inset
+
+ choose 
+\begin_inset Formula $k$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula ${n \choose 0}=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula ${n \choose 1}=n$
+\end_inset
+
+,
+ 
+\begin_inset Formula ${n \choose 2}=\frac{n\left(n-1\right)}{2}$
+\end_inset
+
+ (neurejeni pari)
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula 
+\[
+{n \choose n-k}={n \choose k}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Bijekcija 
+\begin_inset Formula $\Phi:{\left[n\right] \choose k}\to\binom{\left[n\right]}{n-k}$
+\end_inset
+
+ s predpisom 
+\begin_inset Formula $\Phi\left(B\right)=B^{\mathcal{C}}$
+\end_inset
+
+ in 
+\begin_inset Formula $\Phi^{-1}\left(B\right)=B^{\mathcal{C}}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula 
+\[
+{n \choose k}=\frac{n^{\underline{k}}}{k!}=\begin{cases}
+\frac{n!}{k!\left(n-k\right)!} & ;0\leq k\leq n\\
+0 & ;\text{ sicer}
+\end{cases}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Dva načina.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Izberemo 
+\begin_inset Formula $1-$
+\end_inset
+
+elementne podmnožice na 
+\begin_inset Formula $n$
+\end_inset
+
+ načinov,
+ 
+\begin_inset Formula $2-$
+\end_inset
+
+elementne na 
+\begin_inset Formula $n-1$
+\end_inset
+
+ načinov,
+ ...,
+ 
+\begin_inset Formula $k-$
+\end_inset
+
+elementne na 
+\begin_inset Formula $n-k+1$
+\end_inset
+
+ načinov.
+ Delimo s številom permutacij 
+\begin_inset Formula $\left[k\right]$
+\end_inset
+
+,
+ ker vrstni red izbire teh podmnožic ni pomemben.
+ Podmnožic je torej 
+\begin_inset Formula $\frac{n^{\underline{k}}}{k!}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Preštejemo urejene izbire brez ponavljanja na dva načina:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $n^{\underline{k}}$
+\end_inset
+
+:
+ Izberemo 
+\begin_inset Formula $k$
+\end_inset
+
+ elementov,
+ za prvega imamo 
+\begin_inset Formula $n$
+\end_inset
+
+ možnosti,
+ za drugega 
+\begin_inset Formula $n-1$
+\end_inset
+
+,
+ ...
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $k!\cdot\binom{n}{k}$
+\end_inset
+
+:
+ Izberemo 
+\begin_inset Formula $k-$
+\end_inset
+
+elementno podmnožico in ji določimo vrstni red.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+\Rightarrow n^{\underline{k}}=k!\cdot\binom{n}{k}
+\]
+
+\end_inset
+
+Če 
+\begin_inset Formula $k<0$
+\end_inset
+
+ ali 
+\begin_inset Formula $k>0$
+\end_inset
+
+ je 
+\begin_inset Formula $\binom{n}{k}=0$
+\end_inset
+
+,
+ sicer 
+\begin_inset Formula $\frac{n^{\underline{k}}}{k!}\cdot\frac{\left(n-k\right)!}{\left(n-k\right)!}=\frac{n!}{k!\left(n-k\right)!}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Example*
+\begin_inset Formula 
+\[
+\binom{10}{7}=?=\binom{10}{3}=\frac{10\cdot9\cdot8}{6}=120
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Claim*
+Rekurzivna zveza za binomske koeficiente:
+\begin_inset Formula 
+\[
+\forall n,k\in\mathbb{N}:\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Dva načina:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Računsko.
+\begin_inset Formula 
+\[
+\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{\left(n-1\right)^{\underline{k-1}}}{\left(k-1\right)!}+\frac{\left(n-1\right)^{\underline{k}}}{k!}=\frac{k\left(n-1\right)^{\underline{k-1}}+\left(n-1\right)^{\underline{k}}}{k!}=\frac{\left(n-1\right)^{\underline{k-1}}\left(\cancel{k}+n\cancel{-1}\cancel{-k}\cancel{+1}\right)}{k!}=\frac{\left(n-1\right)^{\underline{k-1}}n}{k!}=\frac{n^{\underline{k-1}}}{k!}={n \choose k}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+Bijektivno z načelom vsote.
+ Vzemimo 
+\begin_inset Formula $k-$
+\end_inset
+
+podmnožico
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $k-$
+\end_inset
+
+elementno podmnožico
+\end_layout
+
+\end_inset
+
+ 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+.
+ Klasificirajmo jo glede na vsebnost 
+\begin_inset Formula $n$
+\end_inset
+
+ na dve očitno disjunktni podmnožici:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $n$
+\end_inset
+
+ je element te podmnožice.
+ Takih je 
+\begin_inset Formula $\binom{n-1}{k-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $n$
+\end_inset
+
+ ni element te podmnožice.
+ Takih je 
+\begin_inset Formula $\binom{n-1}{k}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Formalno iščemo bijekcijo 
+\begin_inset Formula $\Phi:{\left[n\right] \choose k}\to\binom{\left[n-1\right]}{k-1}\cup\binom{\left[n-1\right]}{k}$
+\end_inset
+
+.
+ Predpis 
+\begin_inset Formula $\Phi\left(B\right)=B\setminus\left\{ n\right\} $
+\end_inset
+
+,
+ 
+\begin_inset Formula $\Phi^{-1}$
+\end_inset
+
+
+\begin_inset Formula $\left(B\right)=\begin{cases}
+B\cup\left\{ n\right\}  & ;\left|B\right|=k-1\\
+B & ;\left|B\right|=k
+\end{cases}$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Standard
+Skica pascalovega trikotnika prepuščena bralcu.
+ TODO XXX FIXME.
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula 
+\[
+\sum_{k=0}^{n}{n \choose k}=2^{n}\sim\bigcup_{k=0}^{n}{\left[n\right] \choose k}=2^{\left[n\right]}\overset{\text{disjunktne}}{\Longrightarrow}\left|\bigcup_{k=0}^{n}\binom{\left[n\right]}{k}\right|=\left|2^{\left[n\right]}\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Binomski izrek.
+ Za 
+\begin_inset Formula $a,b$
+\end_inset
+
+ elementa komutativnega kolobarja (polja) in za 
+\begin_inset Formula $n\in\mathbb{N}$
+\end_inset
+
+ velja
+\begin_inset Formula 
+\[
+\left(a+b\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Več načinov.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Induktivno.
+ Baza 
+\begin_inset Formula $n=0$
+\end_inset
+
+:
+ 
+\begin_inset Formula $1={0 \choose 0}a^{0}b^{0}=1$
+\end_inset
+
+.
+ Korak 
+\begin_inset Formula $n-1\to n$
+\end_inset
+
+:
+ 
+\begin_inset Formula 
+\[
+\left(a+b\right)^{n}\left(a+b\right)^{n-1}\left(a+b\right)\overset{\text{I.P.}}{=}\left(\sum_{k=0}^{n-1}{n-1 \choose k}a^{n-1-k}b^{k}\right)\left(a+b\right)=\sum_{k=0}^{n-1}\binom{n-1}{k}a^{n-k}b^{k}+\sum_{k=0}^{n-1}{n-1 \choose k}a^{n-1-k}b^{k+1}=
+\]
+
+\end_inset
+
+...
+ v desni vsoti naj bo 
+\begin_inset Formula $k'\coloneqq k+1$
+\end_inset
+
+ ...
+\begin_inset Formula 
+\[
+=\sum_{k=0}^{n-1}\binom{n-1}{k}a^{n-k}b^{k}+\sum_{k'=1}^{n}\binom{n-1}{k'-1}a^{n-k'}b^{k'}=
+\]
+
+\end_inset
+
+...
+ levo zgornjo mejo povečamo za 1,
+ prav tako desno spodnjo,
+ s čimer dodamo le dva ničelna člena.
+ vezano spremenljivko 
+\begin_inset Formula $k'$
+\end_inset
+
+ preimenujemo v 
+\begin_inset Formula $k$
+\end_inset
+
+ ...
+\begin_inset Formula 
+\[
+=\sum_{k=0}^{n}\binom{n-1}{k}a^{n-k}b^{k}+\sum_{k=0}^{n}\binom{n-1}{k-1}a^{n-k}b^{k}=\sum_{k=0}^{n}\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]a^{n-1}b^{k}=\sum_{k=0}^{n}\binom{n}{k}a^{n-1}b^{k}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+Enako kot prej,
+ le da se ne utrujamo z mejami.
+ Vse meje razširimo na vsa cela števila in s tem le dodamo neskončno ničelnih členov.
+ Baza 
+\begin_inset Formula $n=0$
+\end_inset
+
+ velja kot prej.
+ Korak 
+\begin_inset Formula $n-1\to n$
+\end_inset
+
+:
+\begin_inset Formula 
+\[
+\left(a+b\right)^{n}=\left(a+b\right)^{n-1}\left(a+b\right)=\left(\sum_{k}\binom{n-1}{k}a^{n-1-k}b^{k}\right)\left(a+b\right)=\sum_{k}\binom{n-1}{k}a^{n-k}b^{k}+\sum_{k}\binom{n-1}{k}a^{n-1-k}b^{k+1}=
+\]
+
+\end_inset
+
+...
+ zamaknemo 
+\begin_inset Formula $k\coloneqq k+1$
+\end_inset
+
+ v desni vsoti ...
+\begin_inset Formula 
+\[
+=\sum_{k}\binom{n-1}{k}a^{n-k}b^{k}+\sum_{k}\binom{n-1}{k-1}a^{n-k}b^{k}=\sum_{k}\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]a^{n-k}b^{k}=\sum_{k}\binom{n}{k}a^{n-k}b^{k}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+Kombinatorično.
+ 
+\begin_inset Formula $\left(a+b\right)^{n}=\left(a+b\right)\cdot\cdots\cdot\left(a+b\right)$
+\end_inset
+
+.
+ Po distributivnosti je to vsota členov,
+ ki so produkt enega člena iz prvega oklepaja,
+ enega iz drugega,
+ enega iz tretjega,
+ itd.
+ Če smo 
+\begin_inset Formula $k-$
+\end_inset
+
+krat izbrali 
+\begin_inset Formula $b$
+\end_inset
+
+,
+ smo 
+\begin_inset Formula $n-k-$
+\end_inset
+
+krat izbrali 
+\begin_inset Formula $a$
+\end_inset
+
+ (skupno imamo 
+\begin_inset Formula $n$
+\end_inset
+
+ izbir).
+ Torej je vsak člen oblike 
+\begin_inset Formula $a^{n-k}b^{k}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $0\leq k\leq n$
+\end_inset
+
+.
+ Člen 
+\begin_inset Formula $a^{n-k}b^{k}$
+\end_inset
+
+ dobimo na 
+\begin_inset Formula $\binom{n}{k}$
+\end_inset
+
+ načinov,
+ ker moramo izmed 
+\begin_inset Formula $n$
+\end_inset
+
+ oklepajev (faktorjev) izbrati tistih 
+\begin_inset Formula $k$
+\end_inset
+
+,
+ pri katerih vzamemo 
+\begin_inset Formula $b$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Corollary*
+\begin_inset Formula $\left(1+x\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}$
+\end_inset
+
+.
+ Za 
+\begin_inset Formula $x=1$
+\end_inset
+
+:
+ 
+\begin_inset Formula $2^{n}=\sum_{k=0}^{n}\binom{n}{k}$
+\end_inset
+
+.
+ Za 
+\begin_inset Formula $x=-1$
+\end_inset
+
+:
+ 
+\begin_inset Formula $0^{n}=\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}=\delta_{n,0}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Kronekerjeva delta.
+ 
+\begin_inset Formula $\delta_{i,j}\coloneqq\begin{cases}
+1 & ;i=j\\
+0 & ;i\not=j
+\end{cases}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $\forall n>0:\sum_{k\text{ sod}}\binom{n}{k}=\sum_{k\text{ lih}}\binom{n}{k}$
+\end_inset
+
+ ZDB 
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+hypertarget{l=s}{število lihih podmnožic}
+\end_layout
+
+\end_inset
+
+ neprazne končne množice 
+\begin_inset Formula $A$
+\end_inset
+
+ je enako številu sodih podmnožic 
+\begin_inset Formula $A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Izberemo in fiksiramo element 
+\begin_inset Formula $u\in A$
+\end_inset
+
+.
+ Bijekcija 
+\begin_inset Formula $\Phi\left(B\right)=\begin{cases}
+B\cup\left\{ u\right\}  & ;u\not\in B\\
+B\setminus\left\{ u\right\}  & ;u\in B
+\end{cases}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Izbori
+\end_layout
+
+\begin_layout Standard
+Imamo 
+\begin_inset Formula $n$
+\end_inset
+
+ kroglic,
+ 
+\begin_inset Formula $k$
+\end_inset
+
+ jih izberemo.
+ Vprašamo se,
+ ali je vrstni red pomemben in ali kroglice med izbirami vračamo v boben (nabor možnih kroglic za novo izbiro).
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float table
+placement document
+alignment document
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset Tabular
+<lyxtabular version="3" rows="3" columns="3">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+s ponavljanjem
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+brez ponavljanja
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+vrstni red je pomemben —
+ variacije
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $n^{k}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $n^{\underline{k}}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+vrstni red ni pomemben —
+ kombinacije
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n+k-1}{k}$
+\end_inset
+
+ —
+ 
+\begin_inset Formula $1\leq i_{1}\leq i_{2}\leq\cdots\leq i_{k}\leq n$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{k}$
+\end_inset
+
+ —
+ 
+\begin_inset Formula $1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Izbori
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Kombinacij s ponavljanjem je 
+\begin_inset Formula $\binom{n+k-1}{k}$
+\end_inset
+
+.
+ Iščemo število rešitev sistema 
+\begin_inset Formula $1\leq i_{1}\leq i_{2}\leq\cdots\leq i_{k}\leq n$
+\end_inset
+
+.
+ Naj bo 
+\begin_inset Formula $j_{1}\coloneqq i_{1}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $j_{2}\coloneqq i_{2}+1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $j_{3}\coloneqq i_{3}+2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $j_{4}\coloneqq i_{4}+3$
+\end_inset
+
+,
+ ...
+ 
+\begin_inset Formula $j_{k}\coloneqq i_{k}+k-1$
+\end_inset
+
+.
+ Dobimo sistem 
+\begin_inset Formula $1\leq j_{1}<j_{2}<\cdots<j_{k}\leq n+k-1$
+\end_inset
+
+,
+ ki ima enako rešitev kot prvotni sistem.
+ Ta sistem pa ima 
+\begin_inset Formula $\binom{n+k-1}{k}$
+\end_inset
+
+ rešitev (kombinacije brez ponavljanja).
+\end_layout
+
+\begin_layout Example*
+Primer za 
+\begin_inset Formula $n=3$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k=3$
+\end_inset
+
+:
+ Kombinacije s ponavljanjem:
+ 111,
+ 112,
+ 122,
+ 123,
+ 133,
+ 222,
+ 223,
+ 233,
+ 333.
+ Kombinacije brez ponavljanja za 
+\begin_inset Formula $n\coloneqq n+k-1=5$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k\coloneqq k=3$
+\end_inset
+
+:
+ 123,
+ 124,
+ 134,
+ 135,
+ 145,
+ 234,
+ 235,
+ 245,
+ 345.
+\end_layout
+
+\begin_layout Subsection
+Kompozicije
+\end_layout
+
+\begin_layout Definition*
+Naj bo 
+\begin_inset Formula $n\in\mathbb{N}$
+\end_inset
+
+.
+ Pravimo,
+ da je 
+\begin_inset Formula $\left(\lambda_{1},\dots,\lambda_{l}\right)\in\mathbb{N}^{l}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\forall i\in\left[l\right]:\lambda_{i}\geq1$
+\end_inset
+
+,
+ kjer 
+\begin_inset Formula $\sum_{i=1}^{l}\lambda_{i}=n$
+\end_inset
+
+,
+ kompozicija števila 
+\begin_inset Formula $n$
+\end_inset
+
+.
+ Pravimo,
+ da je 
+\begin_inset Formula $\left(\lambda_{1},\dots,\lambda_{l}\right)\in\mathbb{N}_{0}^{l}$
+\end_inset
+
+,
+ kjer 
+\begin_inset Formula $\sum_{i=1}^{l}\lambda_{l}=n$
+\end_inset
+
+,
+ šibka kompozicija števila 
+\begin_inset Formula $n$
+\end_inset
+
+.
+ 
+\begin_inset Formula $\lambda_{1},\dots,\lambda_{l}$
+\end_inset
+
+ so členi kompozicije,
+ 
+\begin_inset Formula $l$
+\end_inset
+
+ je njena dolžina,
+ 
+\begin_inset Formula $n$
+\end_inset
+
+ pa njena velikost.
+\end_layout
+
+\begin_layout Example*
+Vse kompozicije 
+\begin_inset Formula $n=3$
+\end_inset
+
+:
+ 
+\begin_inset Formula $\left(3\right),\left(2,1\right),\left(1,2\right),\left(1,1,1\right)$
+\end_inset
+
+,
+ kajti 
+\begin_inset Formula $3=3=2+1=1+2=1+1+1$
+\end_inset
+
+.
+ Ena šibka kompozicija 
+\begin_inset Formula $n=3$
+\end_inset
+
+ (vseh je neskončno):
+ 
+\begin_inset Formula $\left(2,0,0,0,1,0,0,0\right)$
+\end_inset
+
+,
+ kajti 
+\begin_inset Formula $3=2+0+0+0+1+0+0+0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Question*
+Koliko je kompozicij za dan 
+\begin_inset Formula $n$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Theorem*
+Število kompozicij 
+\begin_inset Formula $n=2^{n-1}$
+\end_inset
+
+ za 
+\begin_inset Formula $n\geq1$
+\end_inset
+
+.
+ Število kompozicij 
+\begin_inset Formula $n$
+\end_inset
+
+ dolžine 
+\begin_inset Formula $k={n-1 \choose k-1}$
+\end_inset
+
+ za 
+\begin_inset Formula $n\geq1,k\geq1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Kompozicijo si predstavljajmo kot kroglice in pregrade:
+ 
+\begin_inset Formula $4+2+2+3+1\sim\circ\circ\circ\circ\vert\circ\circ\vert\circ\circ\vert\circ\circ\circ|\circ$
+\end_inset
+
+.
+ Kompozicija števila 
+\begin_inset Formula $n$
+\end_inset
+
+:
+ 
+\begin_inset Formula $n-1$
+\end_inset
+
+ možnih pregrad 
+\begin_inset Formula $\tilde{=}$
+\end_inset
+
+ vsi dvojiški nizi dolžine 
+\begin_inset Formula $n-1\Rightarrow2^{n-1}$
+\end_inset
+
+.
+ Da bo 
+\begin_inset Formula $k$
+\end_inset
+
+ členov,
+ moramo vstaviti (izbrati mesta za) 
+\begin_inset Formula $k-1$
+\end_inset
+
+ pregrad:
+ 
+\begin_inset Formula ${n-1 \choose k-1}$
+\end_inset
+
+ možnosti.
+\end_layout
+
+\begin_layout Theorem*
+Število šibkih kompozicij 
+\begin_inset Formula $n\geq1$
+\end_inset
+
+ s 
+\begin_inset Formula $k\geq1$
+\end_inset
+
+ členi je 
+\begin_inset Formula ${n+k-1 \choose k-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Več načinov.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Kroglice in pregrade.
+ Ker so členi lahko ničelni,
+ sta lahko tudi dve pregradi na istem mestu.
+ Imamo torej 
+\begin_inset Formula $n+k-1$
+\end_inset
+
+ 
+\begin_inset Quotes gld
+\end_inset
+
+mest
+\begin_inset Quotes grd
+\end_inset
+
+.
+ Na vsakem mestu je lahko bodisi kroglica bodisi pregrada.
+ 
+\begin_inset Formula $k-1$
+\end_inset
+
+ mest za pregrade izberemo na 
+\begin_inset Formula $\binom{n+k-1}{k-1}$
+\end_inset
+
+ načinov.
+ Kroglice so na preostalih mestih.
+\end_layout
+
+\begin_layout Enumerate
+Iščemo število rešitev enačbe 
+\begin_inset Formula $x_{1}+\cdots+x_{k}=n$
+\end_inset
+
+ 
+\begin_inset Formula $\left(\forall i\in\left[k\right]:x_{i}\geq0\right)$
+\end_inset
+
+.
+ Vzemimo 
+\begin_inset Formula $\forall i\in\left[k\right]:y_{i}\coloneqq x_{i}+1$
+\end_inset
+
+.
+ Sedaj je 
+\begin_inset Formula $y_{i}\geq1$
+\end_inset
+
+ in velja 
+\begin_inset Formula $y_{1}+\cdots+y_{k}=n+k$
+\end_inset
+
+.
+ To pa so običajne kompozicije števila 
+\begin_inset Formula $n+k$
+\end_inset
+
+ s 
+\begin_inset Formula $k$
+\end_inset
+
+ členi:
+ 
+\begin_inset Formula $\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$
+\end_inset
+
+ rešitev.
+\end_layout
+
+\begin_layout Enumerate
+Kombinatorično.
+ Opazimo podobnost formule za število šibkih kompozicij in število kombinacij s ponavljanjem?
+ 
+\begin_inset Formula $x_{i}$
+\end_inset
+
+ ponazarja,
+ kolikokrat izberemo 
+\begin_inset Formula $i-$
+\end_inset
+
+to kroglico:
+ 
+\begin_inset Formula $x_{i}\in\left\{ 0..n\right\} $
+\end_inset
+
+.
+ 
+\begin_inset Formula $k$
+\end_inset
+
+ predstavlja število izbranih kroglic,
+ 
+\begin_inset Formula $n$
+\end_inset
+
+ pa število različnih kroglic.
+ Izmed 
+\begin_inset Formula $k$
+\end_inset
+
+ različnih kroglic izberemo 
+\begin_inset Formula $n$
+\end_inset
+
+ kroglic s ponavljanjem (vsako kroglico od 
+\begin_inset Formula $0$
+\end_inset
+
+ do 
+\begin_inset Formula $n-$
+\end_inset
+
+krat).
+\end_layout
+
+\end_deeper
+\begin_layout Subsection
+Načelo vključitev in izključitev —
+ NVI (angl.
+ principle of inclusion and exclusion —
+ PIE)
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+A\cap B=\emptyset\Rightarrow\left|A\cup B\right|=\left|A\right|+\left|B\right|
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|A\cap C\right|-\left|B\cap C\right|+\left|A\cap B\cap C\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Naj bo 
+\begin_inset Formula $A_{1},\dots,A_{n}\subseteq A$
+\end_inset
+
+ in 
+\begin_inset Formula $M=\left\{ A_{1},\cdots,A_{n}\right\} $
+\end_inset
+
+.
+ Za poljubno 
+\begin_inset Formula $I\subseteq\left[n\right]$
+\end_inset
+
+ označimo 
+\begin_inset Formula $A_{I}\coloneqq\bigcap_{i\in I}A_{i}$
+\end_inset
+
+ (npr.
+ 
+\begin_inset Formula $A_{\left\{ 2,4,8\right\} }=A_{2}\cap A_{4}\cap A_{8}$
+\end_inset
+
+).
+ Tedaj 
+\begin_inset Formula 
+\[
+\left|\bigcup_{i=1}^{n}A_{i}\right|=\left|A_{1}\right|+\cdots\left|A_{n}\right|-\left|A_{1}\cap A_{2}\right|-\cdots-\left|A_{n-1}\cap A_{n}\right|+\left|A_{1}\cap A_{2}\cap A_{3}\right|+\cdots
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+-\left|A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\right|+\cdots-\cdots+\cdots+\left(-1\right)^{n+1}\left|A_{1}\cap\cdots\cap A_{n}\right|=
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+=\sum_{i=1}^{n}\left(-1\right)^{i-1}\sum_{1\leq j_{1}<\cdots<j_{i}\leq n}\left|A_{j_{1}}\cap A_{j_{2}}\cap\cdots\cap A_{j_{i}}\right|=\sum_{i=1}^{n}\left(-1\right)^{i-1}\sum_{X\in2^{M}}\left|\begin{cases}
+\emptyset & ;\left|X\right|\not=i\\
+\bigcap_{Y\in X}Y & ;\text{ sicer}
+\end{cases}\right|=\sum_{\emptyset\not=I\subseteq\left[n\right]}\left(-1\right)^{\left|I\right|-1}\left|A_{I}\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Naj bo 
+\begin_inset Formula $x\in\bigcup_{i=1}^{n}A_{i}$
+\end_inset
+
+.
+ Denimo,
+ da je 
+\begin_inset Formula $x$
+\end_inset
+
+ element natanko 
+\begin_inset Formula $m$
+\end_inset
+
+ (gotovo 
+\begin_inset Formula $\geq1$
+\end_inset
+
+) množic izmed 
+\begin_inset Formula $A_{1},\dots,A_{n}$
+\end_inset
+
+.
+ Koliko je potem doprinos 
+\begin_inset Formula $x$
+\end_inset
+
+ k vsoti na desni?
+ Uporabimo dejstvo,
+ da je 
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+hyperlink{l=s}{število lihih podmnožic enako številu sodih}
+\end_layout
+
+\end_inset
+
+.
+\begin_inset Formula 
+\[
+m-{m \choose 2}+{m \choose 3}-{m \choose 4}+\cdots=\cancel{-\left(\binom{m}{0}-\binom{m}{1}+\binom{m}{2}-\binom{m}{3}+\cdots\right)}+1=1
+\]
+
+\end_inset
+
+Vsak element smo šteli natanko enkrat.
+\end_layout
+
+\begin_layout Theorem*
+NVI,
+ druga verzija.
+ 
+\begin_inset Formula 
+\[
+\left|\bigcap_{i=1}^{n}A_{i}^{\mathcal{C}}\right|=\sum_{I\subseteq\left[n\right]}\left(-1\right)^{\left|I\right|}\left|A_{I}\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Pri zadnjem enačaju uporabimo dejstvo,
+ da je prazen produkt univerzum (
+\begin_inset Formula $A_{\emptyset}=A$
+\end_inset
+
+).
+\begin_inset Formula 
+\[
+\left|\bigcap_{i=1}^{n}A_{i}^{\mathcal{C}}\right|=\left|\left(\bigcup_{i=1}^{n}A_{i}\right)^{\mathcal{C}}\right|=\left|A\right|-\left|\bigcup_{i=1}^{n}A_{i}\right|=\left|A\right|+\sum_{\emptyset\not=I\subseteq\left[n\right]}\left(-1\right)^{\left|I\right|}\left|A_{I}\right|=\sum_{I\subseteq\left[n\right]}\left(-1\right)^{\left|I\right|}\left|A_{I}\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+Naloge.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Preštej permutacije brez negibnih točk v 
+\begin_inset Formula $S_{n}$
+\end_inset
+
+.
+ 
+\begin_inset Formula $a_{0}=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a_{1}=0$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a_{2}=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a_{3}=2=\left|\left\{ \left(132\right),\left(123\right)\right\} \right|$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a_{4}=6=\left|\left\{ \left(1234\right),\left(1243\right),\left(1324\right),\left(1342\right),\left(1423\right),\left(1432\right)\right\} \right|$
+\end_inset
+
+,
+ ...
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Naj bo 
+\begin_inset Formula $A\coloneqq S_{n}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $A_{i}\coloneqq\left\{ \pi\in S_{n};\pi\left(i\right)=i\right\} $
+\end_inset
+
+ ZDB vse permutacije,
+ kjer je 
+\begin_inset Formula $i$
+\end_inset
+
+ negibna točka.
+ Iščemo torej 
+\begin_inset Formula $\bigcap_{i=1}^{n}A_{i}^{\mathcal{C}}=\left\{ \pi\in S_{n};\pi\text{ nima negibne točke}\right\} $
+\end_inset
+
+.
+ Izračunajmo moči presekov:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left|A_{i}\right|=\left(n-1\right)!$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\left|A_{i}\cap A_{j}\right|=\left(n-2\right)!$
+\end_inset
+
+,
+ ...,
+ splošno:
+ 
+\begin_inset Formula $\left|A_{I}\right|=\left(n-\left|I\right|\right)!$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+a_{n}=\sum_{I\subseteq\left[n\right]}\left(-1\right)^{\left|I\right|}\left|A_{I}\right|=\sum_{I\subseteq\left[n\right]}\left(-1\right)^{\left|I\right|}\left(n-\left|I\right|\right)!=
+\]
+
+\end_inset
+
+...
+ imamo odvisnost le od moči 
+\begin_inset Formula $I$
+\end_inset
+
+,
+ ne pa tudi od vsebine 
+\begin_inset Formula $I$
+\end_inset
+
+.
+ Moč 
+\begin_inset Formula $i$
+\end_inset
+
+ se ponovi 
+\begin_inset Formula ${n \choose i}-$
+\end_inset
+
+krat ...
+\begin_inset Formula 
+\[
+=\sum_{i=0}^{n}\left(-1\right)^{i}\left(n-i\right)!{n \choose i}=\sum_{i=0}^{n}\left(-1\right)^{i}\cancel{\left(n-i\right)!}\frac{n!}{i!\cancel{\left(n-i\right)!}}=n!\sum_{i=0}^{n}\frac{\left(-1\right)^{i}}{i!}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Kakšna je verjetnost,
+ da je naključno izbrana permutacija brez negibne točke?
+\begin_inset Formula 
+\[
+\lim_{n\to\infty}\frac{\cancel{n!}\sum_{i=0}^{n}\frac{\left(-1\right)^{i}}{i!}}{\cancel{n!}}=\lim_{n\to\infty}\sum_{i=0}^{n}\frac{\left(-1\right)^{i}}{i!}=e^{-1}
+\]
+
+\end_inset
+
+Velja namreč 
+\begin_inset Formula $e^{x}=\sum_{n=0}^{\infty}\frac{x^{n}}{n!}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Preštej surjekcije 
+\begin_inset Formula $\left[n\right]\to\left[k\right]$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Formula 
+\[
+A\coloneqq\left[k\right]^{\left[n\right]}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\forall i\in k:A_{i}\coloneqq\left\{ f:\left[n\right]\to\left[k\right];\forall i\in\left\{ 1..n\right\} :f\left(j\right)\not=i\right\} =\left\{ f:\left[n\right]\to\left[k\right]\setminus\left\{ i\right\} \right\} 
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\left|A_{i}\right|=\left(k-1\right)^{n}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+A_{i}\cap A_{j}=\left\{ f:\left[n\right]\to\left[k\right]\setminus\left\{ i,j\right\} \right\} 
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\left|A_{i}\cap A_{j}\right|=\left(k-2\right)^{n}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+A_{I}=\left\{ f:\left[n\right]\to\left[k\right]\setminus I\right\} 
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\left|A_{I}\right|=\left(k-\left|I\right|\right)^{n}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\left|\left\{ f:\left[n\right]\to\left[k\right];f\text{ surjekcija}\right\} \right|=\left|\bigcap_{i=1}^{k}A_{i}^{\mathcal{C}}\right|=\sum_{I\subseteq\left[k\right]}\left(-1\right)^{\left|I\right|}\left(k-\left|I\right|\right)^{n}=\sum_{i=0}^{k}\left(-1\right)^{i}\left(k-i\right)^{n}{k \choose i}\overset{j\coloneqq k-i}{=}\sum_{j=0}^{k}\left(-1\right)^{k-j}{k \choose j}j^{n}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Koliko je surjekcij v množico z 2 elementoma?
+ 
+\begin_inset Formula $k=2$
+\end_inset
+
+.
+ 
+\begin_inset Formula $\delta_{n,0}-2+2^{n}$
+\end_inset
+
+.
+ S tremi?
+ 
+\begin_inset Formula $k=3$
+\end_inset
+
+.
+ 
+\begin_inset Formula $-\delta_{n,0}+3-3\cdot2^{n}+3^{n}$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Definition*
+Eulerjeva funkcija 
+\begin_inset Formula $\phi$
+\end_inset
+
+ (angl.
+ totient function).
+ 
+\begin_inset Formula $\phi\left(n\right)=\left|\left\{ i\in\left[n\right];\gcd\left(i,n\right)=1\right\} \right|$
+\end_inset
+
+ ZDB št.
+ elementov,
+ ki so manjši ali enaki 
+\begin_inset Formula $n$
+\end_inset
+
+ in tuji 
+\begin_inset Formula $n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float table
+placement document
+alignment document
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset Tabular
+<lyxtabular version="3" rows="2" columns="13">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $n$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+7
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+8
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+9
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+10
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+11
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+12
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\phi\left(n\right)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+10
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Eulerjeva funkcija 
+\begin_inset Formula $\phi$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Remark*
+Za praštevilo 
+\begin_inset Formula $p$
+\end_inset
+
+ velja 
+\begin_inset Formula $\phi\left(p\right)=p-1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\phi\left(p^{2}\right)=p^{2}-p$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\phi\left(p^{k}\right)=p^{k}-p^{k-1}=p^{k}\left(1-\frac{1}{p}\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $\sum_{d\vert n}\phi\left(d\right)=n$
+\end_inset
+
+ (vsota slik s 
+\begin_inset Formula $\phi$
+\end_inset
+
+ deliteljev 
+\begin_inset Formula $n$
+\end_inset
+
+ je 
+\begin_inset Formula $n$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Proof
+Oglejmo si 
+\begin_inset Formula $\frac{1}{n},\frac{2}{n},\frac{3}{n},\dots,\frac{n}{n}$
+\end_inset
+
+ in okrajšajmo,
+ kolikor se le da.
+ Primer:
+ 
+\begin_inset Formula $\frac{1}{12},\frac{2}{12},\frac{3}{12},\frac{4}{12},\frac{5}{12},\frac{6}{12},\frac{7}{12},\frac{8}{12},\frac{9}{12},\frac{10}{12},\frac{11}{12},\frac{12}{12}\to\frac{1}{12},\frac{1}{6},\frac{1}{4},\frac{1}{3},\frac{5}{12},\frac{1}{2},\frac{7}{12},\frac{2}{3},\frac{3}{4},\frac{5}{6},\frac{11}{12},\frac{1}{1}$
+\end_inset
+
+.
+ Možni imenovalci so delitelji 
+\begin_inset Formula $n$
+\end_inset
+
+,
+ možnih števcev z imenovalcem 
+\begin_inset Formula $d$
+\end_inset
+
+ pa je 
+\begin_inset Formula $\phi\left(d\right)$
+\end_inset
+
+.
+ Če torej grupiramo te ulomke (skupaj jih je 
+\begin_inset Formula $n$
+\end_inset
+
+ —
+ desna stren enačbe) po imenovalcih (deliteljih),
+ bo pri vsakem delitelju 
+\begin_inset Formula $\phi\left(d\right)$
+\end_inset
+
+ ulomkov (leva stran enačbe).
+\end_layout
+
+\begin_layout Standard
+Izrazimo 
+\begin_inset Formula $\phi\left(n\right)$
+\end_inset
+
+.
+ Naj bo 
+\begin_inset Formula $n=p_{1}^{\alpha_{1}}\cdot\cdots\cdot p_{k}^{\alpha_{k}}$
+\end_inset
+
+ in 
+\begin_inset Formula $\forall i\in\left[k\right]:\alpha_{i}\geq1$
+\end_inset
+
+.
+ 
+\begin_inset Formula $A=\left[n\right]$
+\end_inset
+
+;
+ 
+\begin_inset Formula $\forall i\in\left\{ 1..k\right\} :A_{i}\coloneqq\left\{ \text{večkratniki }p_{i}\text{ v }\left[n\right]\right\} $
+\end_inset
+
+.
+ Presek komplementov so števila,
+ tuja 
+\begin_inset Formula $n$
+\end_inset
+
+.
+ 
+\begin_inset Formula $\left|A_{i}\right|=\left\lfloor \frac{n}{p_{i}}\right\rfloor =\frac{n}{p_{i}}$
+\end_inset
+
+ (kajti 
+\begin_inset Formula $p_{i}\vert n$
+\end_inset
+
+),
+ 
+\begin_inset Formula $\left|A_{i}\cap A_{j}\right|=\frac{n}{p_{i}\cdot p_{j}}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\left|A_{I}\right|=\frac{n}{\prod_{i\in I}p_{i}}$
+\end_inset
+
+.
+\begin_inset Formula 
+\[
+\phi\left(n\right)=\sum_{I\subseteq\left[k\right]}\left(-1\right)^{\left|I\right|}\frac{n}{\prod_{i\in I}p_{i}}=n\sum_{I\subseteq\left[k\right]}\left(-1\right)^{\left|I\right|}\frac{1}{\prod_{i\in I}p_{i}}=n\sum_{I\subseteq\left[k\right]}\left(-1\right)^{\left|I\right|}\prod_{i\in I}p_{i}^{-1}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Primer za 
+\begin_inset Formula $k=2$
+\end_inset
+
+ (število 
+\begin_inset Formula $n$
+\end_inset
+
+ je produkt dveh praštevil):
+\begin_inset Formula 
+\[
+\phi\left(n\right)=n\sum_{I\subseteq\left\{ 1,2\right\} }\left(-1\right)^{\left|I\right|}\prod_{i\in I}p_{i}^{-1}=n\left(1-p_{1}^{-1}-p_{2}^{-1}+p_{1}^{-1}p_{2}^{-1}\right)=n\left(1-p_{1}^{-1}\right)\left(1-p_{2}^{-1}\right)
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Primer za splošen 
+\begin_inset Formula $k$
+\end_inset
+
+ (po distributivnosti):
+\begin_inset Formula 
+\[
+\phi\left(n\right)=n\left(1-p_{1}^{-1}\right)\left(1-p_{2}^{-1}\right)\cdots\left(1-p_{k}^{-1}\right)=n\prod_{p\vert n\text{\text{ praštevilski delitelji }}}\left(1-p^{-1}\right)
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Multinomski koeficient in multinomski izrek
+\end_layout
+
+\begin_layout Question*
+Denimo,
+ da imamo multimnožico (množico,
+ v kateri dovolimo ponavljanje elementov) 
+\begin_inset Formula $M\coloneqq\left\{ 1^{a_{1}},2^{a_{2}},\dots,n^{a_{n}}\right\} $
+\end_inset
+
+ (
+\begin_inset Formula $i-$
+\end_inset
+
+ti element se ponovi 
+\begin_inset Formula $a_{i}-$
+\end_inset
+
+krat).
+ Primer:
+ 
+\begin_inset Formula $M=\left\{ 1,1,1,2,3,3\right\} =\left\{ 1^{3},2^{1},3^{2}\right\} $
+\end_inset
+
+.
+ Koliko je permutacij multimnožice?
+\end_layout
+
+\begin_layout Standard
+Naj bo 
+\begin_inset Formula $N=\sum_{i=1}^{n}a_{i}$
+\end_inset
+
+.
+ Enice razporedimo na 
+\begin_inset Formula $\binom{N}{a_{1}}$
+\end_inset
+
+ načinov,
+ dvojke na 
+\begin_inset Formula $\binom{N-a_{1}}{a_{2}}$
+\end_inset
+
+,
+ trojke na 
+\begin_inset Formula $\binom{N-a_{1}-a_{2}}{a_{3}}$
+\end_inset
+
+,
+ itd.
+ Skupaj je permutacij torej 
+\begin_inset Formula 
+\[
+\binom{N}{a_{1}}\binom{N-a_{1}}{a_{2}}\binom{N-a_{1}-a_{2}}{a_{3}}\cdots=\frac{\left(a_{1}+\cdots+a_{n}\right)!}{a_{1}!\cancel{\left(a_{2}+\cdots+a_{n}\right)!}}\cdot\frac{\cancel{\left(a_{2}+\cdots+a_{n}\right)!}}{a_{2}!\left(a_{3}+\cdots+a_{n}\right)}\cdot\cdots=\frac{N!}{a_{1}}\cdot\frac{1}{a_{2}}\cdot\frac{1}{a_{3}}\cdot\cdots=\frac{\left(a_{1}+\cdots+a_{n}\right)!}{a_{1}!\cdot a_{2}!\cdot\cdots\cdot a_{n}!}\eqqcolon\binom{N}{a_{1},\dots,a_{n}}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Drug način razmišljanja (intuitiven):
+ Ponavljajoče elemente sprva tretiramo kot različne (
+\begin_inset Formula $N!$
+\end_inset
+
+ načinov),
+ nato pa delimo s fakultetami frekvenc posameznih unikatnih elementov,
+ saj teh elementov nočemo razlikovati.
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula 
+\[
+\binom{a+b}{a,b}=\frac{\left(a+b\right)!}{a!b!}=\binom{a+b}{a}=\binom{a+b}{b}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Multinomski izrek.
+ Kako razpisati multinom na 
+\begin_inset Formula $n-$
+\end_inset
+
+to potenco:
+\begin_inset Formula 
+\[
+\left(x_{1}+\cdots+x_{k}\right)^{n}=\sum_{i_{1}+\cdots+i_{k}=n;i_{1},\dots,i_{k}\geq0\text{ (šibke kompozicije \ensuremath{n} dolžine \ensuremath{k})}}\binom{n}{i_{1},\dots,i_{k}}x_{1}^{i_{1}}\cdots x_{k}^{i_{k}}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Načrti in 
+\begin_inset Formula $t-$
+\end_inset
+
+načrti
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $S\subseteq X\times Y$
+\end_inset
+
+ je relacija.
+ Za 
+\begin_inset Formula $x\in X$
+\end_inset
+
+ in 
+\begin_inset Formula $y\in Y$
+\end_inset
+
+ velja 
+\begin_inset Formula $xSy\Leftrightarrow\left(x,y\right)\in S$
+\end_inset
+
+.
+ Za 
+\begin_inset Formula $x\in X$
+\end_inset
+
+ označimo 
+\begin_inset Formula $v_{x}\left(S\right)\coloneqq\left|\left\{ y\in Y;xSy\right\} \right|$
+\end_inset
+
+ (število kljukic v vrstici 
+\begin_inset Formula $x$
+\end_inset
+
+).
+ Za 
+\begin_inset Formula $y\in Y$
+\end_inset
+
+ označimo 
+\begin_inset Formula $s_{y}\left(S\right)\coloneqq\left|\left\{ x\in X;xSy\right\} \right|$
+\end_inset
+
+ (število kljukic v stolpcu 
+\begin_inset Formula $y$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Definition*
+Velja 
+\begin_inset Formula $\left|S\right|=\sum_{x\in X}v_{x}\left(S\right)=\sum_{y\in Y}s_{y}\left(S\right)$
+\end_inset
+
+.
+ Kdaj se zgodi,
+ da je 
+\begin_inset Formula $\forall x,x'\in X:v_{x}\left(S\right)=v_{x'}\left(S\right)$
+\end_inset
+
+,
+ tedaj označimo kar 
+\begin_inset Formula $v\left(S\right)$
+\end_inset
+
+ in analogno za 
+\begin_inset Formula $s\left(x\right)$
+\end_inset
+
+ in tedaj velja 
+\begin_inset Formula $\sum_{x\in X}v_{x}\left(S\right)=v\left(s\right)\left|X\right|$
+\end_inset
+
+.
+ Če to velja za stolpce in vrstice,
+ velja 
+\begin_inset Formula $v\left(S\right)\cdot\left|X\right|=s\left(S\right)\cdot\left|Y\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+Dva primera.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Trianguilacija ravninskega grafa je ravninski graf in zanjo velja,
+ da so vsa lica 
+\begin_inset Formula $3-$
+\end_inset
+
+cikli.
+ Za vsak ravninski graf je moč najti triangulacijo ravninskega grafa.
+ Naj bo 
+\begin_inset Formula $G$
+\end_inset
+
+ triangulacija ravninskega grafa.
+ Za relacijo 
+\begin_inset Formula $S=EG\times FG$
+\end_inset
+
+ s predpisom 
+\begin_inset Formula $eSf\Leftrightarrow e\in f$
+\end_inset
+
+ velja 
+\begin_inset Formula $\forall e,e'\in EG:v_{e}\left(S\right)=v_{e'}\left(S\right)=2$
+\end_inset
+
+ in 
+\begin_inset Formula $\forall f,f'\in FG:s_{f}\left(S\right)=s_{f'}\left(S\right)=3$
+\end_inset
+
+.
+ Torej 
+\begin_inset Formula $v\left(S\right)=2$
+\end_inset
+
+ in 
+\begin_inset Formula $s\left(S\right)=3$
+\end_inset
+
+,
+ sledi 
+\begin_inset Formula $3\left|F\right|=2\left|E\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Koliko deliteljev ima v povprečju število 
+\begin_inset Formula $n$
+\end_inset
+
+?
+ Naj bo 
+\begin_inset Formula $S=\left[n\right]\times\left[n\right]$
+\end_inset
+
+ s predpisom 
+\begin_inset Formula $xSy\Leftrightarrow x\vert y$
+\end_inset
+
+.
+ Velja 
+\begin_inset Formula $s_{y}\left(S\right)=$
+\end_inset
+
+ število deliteljev 
+\begin_inset Formula $y$
+\end_inset
+
+ in 
+\begin_inset Formula $v_{x}\left(S\right)=\left\lfloor \frac{n}{x}\right\rfloor $
+\end_inset
+
+.
+ 
+\begin_inset Formula $\sum_{i=1}^{n}\left\lfloor \frac{n}{i}\right\rfloor =\sum_{j=1}^{n}$
+\end_inset
+
+št.
+ del.
+ 
+\begin_inset Formula $j$
+\end_inset
+
+.
+ Koliko je povprečje?
+\begin_inset Formula 
+\[
+\frac{1}{n}\sum_{j=1}^{n}\text{\#del.}j\overset{\text{asimptotsko enako}}{\sim}\frac{1}{\cancel{n}}\sum_{j=1}\frac{\cancel{n}}{i}=\sum_{j=1}^{1}\frac{1}{i}=H_{n}=n-\text{to harmonično število}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\lim_{n\to\infty}H_{n}=\ln\left(n\right)
+\]
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Paragraph*
+Motivacija za načrte
+\end_layout
+
+\begin_layout Standard
+Podjetje ima izdelek v več različicah in ga testira na več potrošnikih.
+ Zahteve:
+\end_layout
+
+\begin_layout Enumerate
+hočemo,
+ da vsak potrošnik testira enako različic.
+\end_layout
+
+\begin_layout Enumerate
+hočemo,
+ da je vsaka različica enakokrat testirana.
+\end_layout
+
+\begin_layout Standard
+Temu pravimo načrt.
+ Sledi formalnejša definicija,
+ kjer je število potrošnikov 
+\begin_inset Formula $b$
+\end_inset
+
+,
+ število različic 
+\begin_inset Formula $v$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k$
+\end_inset
+
+ število različic na potrošnika,
+ 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ pa število potrošnikov na različico.
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $B=\left\{ B_{1},\dots,B_{b}\right\} $
+\end_inset
+
+ je načrt s parametri 
+\begin_inset Formula $\left(v,k,\lambda\right)$
+\end_inset
+
+,
+ če velja 
+\begin_inset Formula $B_{1},\dots,B_{b}\subseteq\left[v\right]$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\forall i\in\left[b\right]:\left|B_{i}\right|=k$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\forall i\in\left[v\right]\exists$
+\end_inset
+
+ natanko 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ množic,
+ v katerih je 
+\begin_inset Formula $i$
+\end_inset
+
+ vsebovan.
+\end_layout
+
+\begin_layout Definition*
+Če si predstavljamo relacijo 
+\begin_inset Formula $S\subseteq\left[v\right]\times B$
+\end_inset
+
+ s predpisom 
+\begin_inset Formula $iSB_{j}\Leftrightarrow i\in B_{j}$
+\end_inset
+
+,
+ zanjo velja 
+\begin_inset Formula $v\left(S\right)=\lambda$
+\end_inset
+
+ in 
+\begin_inset Formula $s\left(S\right)=k$
+\end_inset
+
+,
+ torej 
+\begin_inset Formula $v\cdot\lambda=k\cdot b$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+Potreben pogoj za načrt je,
+ da je 
+\begin_inset Formula $v\cdot\lambda=k\cdot b$
+\end_inset
+
+,
+ da 
+\begin_inset Formula $k\vert v\cdot\lambda$
+\end_inset
+
+ in da 
+\begin_inset Formula $b\leq{v \choose k}\Longrightarrow\frac{v\lambda}{k}\leq{v \choose k}\Rightarrow\lambda\leq\frac{\cancel{k}\cancelto{\left(v-1\right)!}{v!}}{\cancelto{\left(k-1\right)!}{k!}\cancel{v}\left(v-k\right)!}={v-1 \choose k-1}$
+\end_inset
+
+ (število 
+\begin_inset Formula $k-$
+\end_inset
+
+elementnih podmnožic 
+\begin_inset Formula $\left[v\right]$
+\end_inset
+
+,
+ ki vsebujejo 
+\begin_inset Formula $i$
+\end_inset
+
+)
+\end_layout
+
+\begin_layout Theorem*
+Načrt s parametri 
+\begin_inset Formula $\left(v,k,\lambda\right)\exists\Leftrightarrow\lambda\leq{v-1 \choose k-1}\wedge k\vert v\lambda$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Dokazujemo ekvivalenco.
+\end_layout
+
+\begin_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+ Že dokazano v zgornji opombi (potreben pogoj).
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+ Po predpostavki 
+\begin_inset Formula $\lambda\leq{v-1 \choose k-1}\wedge k\vert v\lambda$
+\end_inset
+
+.
+ Npr.
+ 
+\begin_inset Formula $v=8,k=4,\lambda=3$
+\end_inset
+
+ ustreza 
+\begin_inset Formula $4\vert8\cdot3$
+\end_inset
+
+ in 
+\begin_inset Formula $3\leq{7 \choose 3}=35$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Izberimo poljubnih 
+\begin_inset Formula $b$
+\end_inset
+
+ različnih 
+\begin_inset Formula $k-$
+\end_inset
+
+podmnožic 
+\begin_inset Formula $\left[v\right]$
+\end_inset
+
+.
+ To lahko storimo,
+ ker je 
+\begin_inset Formula $b=\frac{v\lambda}{k}\leq\frac{v}{k}{v-1 \choose k-1}={v \choose k}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Vzamemo npr.
+ 1234,
+ 1356,
+ 1567,
+ 1568,
+ 2356,
+ 3457.
+ Z 
+\begin_inset Formula $\lambda_{i}$
+\end_inset
+
+ označimo,
+ v koliko blokih je 
+\begin_inset Formula $i$
+\end_inset
+
+.
+ Tedaj 
+\begin_inset Formula $\lambda_{1}=4$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{2}=2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{3}=4$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{4}=2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{5}=5$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{6}=4$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{7}=2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{8}=1$
+\end_inset
+
+.
+ To ni načrt.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $k$
+\end_inset
+
+ kljukic že je v vsakem stolpcu,
+ a v vsaki vrstici ni enako kljukic (v 
+\begin_inset Formula $i-$
+\end_inset
+
+ti jih je 
+\begin_inset Formula $\lambda_{i}$
+\end_inset
+
+).
+ Velja 
+\begin_inset Formula $\sum_{i=1}^{v}\lambda_{i}=k\cdot b=\lambda v\Longrightarrow\frac{\sum_{i=1}^{v}\lambda_{i}}{v}=\overline{\lambda_{i}}=\lambda$
+\end_inset
+
+.
+ Če 
+\begin_inset Formula $\forall i\in\left[v\right]:\lambda_{i}=\lambda$
+\end_inset
+
+,
+ imamo načrt in smo končali,
+ sicer vzamemo 
+\begin_inset Formula $i$
+\end_inset
+
+ in 
+\begin_inset Formula $j$
+\end_inset
+
+,
+ da 
+\begin_inset Formula $\lambda_{i}<\lambda<\lambda_{j}$
+\end_inset
+
+ (gotovo 
+\begin_inset Formula $\exists$
+\end_inset
+
+ zaradi prejšnjega razmisleka o povprečju).
+\end_layout
+
+\begin_layout Standard
+Bloki so štirih disjunktnih tipov:
+ 
+\begin_inset Formula $I:i,j\in B$
+\end_inset
+
+,
+ 
+\begin_inset Formula $II:i\not\in B,j\in B$
+\end_inset
+
+,
+ 
+\begin_inset Formula $III:i\in B,j\not\in B$
+\end_inset
+
+,
+ 
+\begin_inset Formula $IV:i\not\in B,j\not\in B$
+\end_inset
+
+.
+ Velja 
+\begin_inset Formula $\lambda_{i}=\left|I\right|+\left|III\right|$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{j}=\left|I\right|+\left|II\right|$
+\end_inset
+
+.
+ Vemo 
+\begin_inset Formula $\lambda_{i}<\lambda_{j}\Rightarrow\left|III\right|<\left|II\right|\Rightarrow$
+\end_inset
+
+ gotovo 
+\begin_inset Formula $\exists$
+\end_inset
+
+ vsak en blok tipa 
+\begin_inset Formula $II$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Treba je še dokazati,
+ da obstaja blok tipa 
+\begin_inset Formula $II$
+\end_inset
+
+,
+ kjer pri menjavi elementa 
+\begin_inset Formula $j$
+\end_inset
+
+ z elementom 
+\begin_inset Formula $i$
+\end_inset
+
+ dobimo blok,
+ ki še ne obstaja.
+ Vemo,
+ da je blokov tipa 
+\begin_inset Formula $II$
+\end_inset
+
+ gotovo več od blokov tipa 
+\begin_inset Formula $III$
+\end_inset
+
+.
+ Po naši menjavi dobimo iz bloka 
+\begin_inset Formula $II$
+\end_inset
+
+ blok 
+\begin_inset Formula $III$
+\end_inset
+
+.
+ Ker je blokov tipa 
+\begin_inset Formula $II$
+\end_inset
+
+ več od blokov tipa 
+\begin_inset Formula $III$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\exists$
+\end_inset
+
+ blok tipa 
+\begin_inset Formula $II$
+\end_inset
+
+,
+ da ob menjavi dobimo nov blok tipa 
+\begin_inset Formula $III$
+\end_inset
+
+,
+ ki še ni med poprejšnjimi bloki —
+ je nov.
+\end_layout
+
+\begin_layout Standard
+Zakaj se algoritem ustavi?
+ 
+\begin_inset Formula $\sum_{i=1}^{v}\left|\lambda_{i}-\lambda\right|$
+\end_inset
+
+ je na vsakem koraku za 2 manjša.
+ Ko je vsota enaka 1 (nedosegljivo stanje,
+ kajti tedaj 
+\begin_inset Formula $\overline{\lambda_{i}}\not=\lambda$
+\end_inset
+
+) ali 0,
+ se ustavimo in imamo načrt.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Definition*
+\begin_inset Formula $t-$
+\end_inset
+
+načrt.
+ 
+\begin_inset Formula $B=\left\{ B_{1},\dots,B_{b}\right\} $
+\end_inset
+
+ je 
+\begin_inset Formula $t-$
+\end_inset
+
+načrt s parametri 
+\begin_inset Formula $\left(v,k,\lambda_{t}\right),$
+\end_inset
+
+če se ne le vsak element pojavi 
+\begin_inset Formula $t-$
+\end_inset
+
+krat,
+ temveč se celo vsaka 
+\begin_inset Formula $t-$
+\end_inset
+
+elementna podmnožica 
+\begin_inset Formula $\left[v\right]$
+\end_inset
+
+ pojavi natanko 
+\begin_inset Formula $t-$
+\end_inset
+
+krat ZDB 
+\begin_inset Formula $B$
+\end_inset
+
+ je načrt in 
+\begin_inset Formula $\forall A\subseteq\left[v\right]:A\subseteq B_{j}$
+\end_inset
+
+ za natanko 
+\begin_inset Formula $\lambda_{t}$
+\end_inset
+
+ indeksov 
+\begin_inset Formula $j$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+Načrt je isto kot 
+\begin_inset Formula $1-$
+\end_inset
+
+načrt.
+ 
+\begin_inset Formula $t-$
+\end_inset
+
+načrt je posplošitev načrta.
+\end_layout
+
+\begin_layout Example*
+Primeri.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+Fanova ravnina.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Float figure
+placement document
+alignment document
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset Graphics
+	filename fanova_ravnina.png
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Fanova ravnina z 
+\begin_inset Formula $v=7$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+Zapiši vse točke,
+ ki ležijo na isti premici,
+ kjer je rumen krog tudi premica.
+ 123,
+ 156,
+ 147,
+ 257,
+ 345,
+ 362,
+ 264.
+ To je načrt in hkrati 
+\begin_inset Formula $2-$
+\end_inset
+
+načrt s parametri 
+\begin_inset Formula $v=7$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k=3$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{1}=3$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{2}=1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $3-$
+\end_inset
+
+načrt s parametri 
+\begin_inset Formula $\left(8,4,1\right)$
+\end_inset
+
+:
+ 1235,
+ 1248,
+ 1267,
+ 1346,
+ 1378,
+ 1457,
+ 1568,
+ 2347,
+ 2368,
+ 2456,
+ 2578,
+ 3458,
+ 3567,
+ 4678.
+\end_layout
+
+\end_deeper
+\begin_layout Theorem*
+Če je 
+\begin_inset Formula $B$
+\end_inset
+
+ 
+\begin_inset Formula $t-$
+\end_inset
+
+načrt s parametri 
+\begin_inset Formula $\left(v,k,\lambda_{t}\right)$
+\end_inset
+
+,
+ je tudi 
+\begin_inset Formula $\left(t-1\right)-$
+\end_inset
+
+načrt s paramatri 
+\begin_inset Formula $\left(v,k,\lambda_{t-1}\right)$
+\end_inset
+
+,
+ kjer je 
+\begin_inset Formula $\lambda_{t-1}=\frac{v-\left(t-1\right)}{k-\left(t-1\right)}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Naj bo 
+\begin_inset Formula $S\subseteq\left[v\right],\left|S\right|=t-1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{S}\coloneqq$
+\end_inset
+
+ v koliko blokih je 
+\begin_inset Formula $S$
+\end_inset
+
+ vsebovana.
+ Naj bo 
+\begin_inset Formula $R\subseteq\left[v\right]\times B$
+\end_inset
+
+ relacija s predpisom 
+\begin_inset Formula $iRB_{j}\Leftrightarrow i\not\in S\wedge S\cup\left\{ i\right\} \subseteq B_{j}$
+\end_inset
+
+.
+ V vrstici je za dani 
+\begin_inset Formula $i$
+\end_inset
+
+ 0 kljukic,
+ če 
+\begin_inset Formula $i\in S$
+\end_inset
+
+,
+ sicer (če 
+\begin_inset Formula $i\not\in S$
+\end_inset
+
+) pa 
+\begin_inset Formula $\lambda_{t}$
+\end_inset
+
+ kljukic.
+ V stolpcu je za dani 
+\begin_inset Formula $B_{j}$
+\end_inset
+
+ 0 kljukic,
+ če 
+\begin_inset Formula $S\not\subseteq B_{j}$
+\end_inset
+
+,
+ sicer (če 
+\begin_inset Formula $S\subseteq B$
+\end_inset
+
+),
+ pa 
+\begin_inset Formula $k-\left(t-1\right)$
+\end_inset
+
+ kljukic.
+ Pomaga skica tabele 
+\begin_inset Formula $R$
+\end_inset
+
+.
+ V 
+\begin_inset Formula $v-\left(t-1\right)$
+\end_inset
+
+ vrsticah se zgodi,
+ da 
+\begin_inset Formula $i\not\in S$
+\end_inset
+
+.
+ Preštejmo po vrsticah in nato po stolpcih:
+\begin_inset Formula 
+\[
+\left(v-\left(t-1\right)\right)\lambda_{t}=\lambda_{s}\left(k-\left(t-1\right)\right)
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\lambda_{s}=\frac{\left(v-\left(t-1\right)\right)\lambda_{t}}{k-\left(t-1\right)}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\lambda_{t-1}\coloneqq\lambda_{s}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Permutacije,
+ razdelitve,
+ razčlenitve
+\end_layout
+
+\begin_layout Subsection
+Stirlingova števila 1.
+ vrste
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $c\left(n,k\right)=$
+\end_inset
+
+ število permutacij 
+\begin_inset Formula $n$
+\end_inset
+
+ elementov,
+ ki imajo 
+\begin_inset Formula $k$
+\end_inset
+
+ ciklov.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $c\left(3,1\right)=2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(3,2\right)=3$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(3,3\right)=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(4,2\right)=4\cdot2+3=11$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(n,n\right)=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(n,n-1\right)={n \choose 2}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(n,1\right)=\left(n-1\right)!$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\left(n,n\right)=\delta_{0,n}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\sum_{k}c\left(n,k\right)=n!$
+\end_inset
+
+ (vse permutacije 
+\begin_inset Formula $n$
+\end_inset
+
+ elementov).
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $c\left(n,k\right)=c\left(n-1,k-1\right)+c\left(n-1,k\right)\cdot\left(n-1\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Permutacije v 
+\begin_inset Formula $S_{n}$
+\end_inset
+
+ s 
+\begin_inset Formula $k$
+\end_inset
+
+ cikli ločimo na:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+take,
+ ki vsebujejo cikel 
+\begin_inset Formula $\left(n\right)$
+\end_inset
+
+ (
+\begin_inset Formula $n$
+\end_inset
+
+ je negibna točka):
+ teh je 
+\begin_inset Formula $c\left(n-1,k-1\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+take,
+ ki ne vsebujejo cikla 
+\begin_inset Formula $\left(n\right)$
+\end_inset
+
+:
+ teh je 
+\begin_inset Formula $c\left(n-1,k\right)\cdot\left(n-1\right)$
+\end_inset
+
+.
+ Če 
+\begin_inset Formula $n$
+\end_inset
+
+ odstranimo,
+ se število ciklov ne spremeni,
+ vendar ga ne moremo vstaviti nazaj enolično,
+ temveč na 
+\begin_inset Formula $n-1$
+\end_inset
+
+ načinov.
+\end_layout
+
+\end_deeper
+\begin_layout Proof
+\begin_inset Float table
+placement document
+alignment document
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset Tabular
+<lyxtabular version="3" rows="7" columns="7">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+n
+\backslash
+k
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+11
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+24
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+50
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+35
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+10
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Tabela stirlingovih števil.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $\sum_{k=0}^{n}c\left(n,k\right)x^{k}=x^{\overline{n}}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $n=3$
+\end_inset
+
+:
+ 
+\begin_inset Formula $2x^{1}+3x^{2}+1x^{2}=x\left(x^{2}+3x+2\right)=x\left(x+1\right)\left(x+2\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Indukcija po 
+\begin_inset Formula $n\in\mathbb{N}_{0}$
+\end_inset
+
+.
+ Baza 
+\begin_inset Formula $n=0$
+\end_inset
+
+:
+ 
+\begin_inset Formula $1=1$
+\end_inset
+
+.
+ Korak 
+\begin_inset Formula $n-1\to n$
+\end_inset
+
+:
+\begin_inset Formula 
+\[
+x^{\overline{n}}=x^{\overline{n-1}}\left(x+n-1\right)\overset{\text{I. P.}}{=}\sum_{k=0}^{n-1}c\left(n-1,k\right)x^{k}\left(x+n-1\right)=\sum_{k}c\left(n-1,k\right)x^{k+1}+\sum_{k}\left(n-1\right)c\left(n-1,k\right)x^{k}=
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+=\sum_{k}c\left(n-1,k-1\right)x^{k}+\sum_{k}\left(n-1\right)c\left(n-1,k\right)x^{k}=\sum_{k}\left(c\left(n-1,k-1\right)+\left(n-1\right)c\left(n-1,k\right)\right)x^{k}=\sum_{k}c\left(n,k\right)x^{k}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $x=1$
+\end_inset
+
+:
+ število permutacij z vsemi števili ciklov 
+\begin_inset Formula $=\sum_{k}c\left(n,k\right)=x^{\overline{n}}=1^{\overline{n}}=n!=$
+\end_inset
+
+ vse permutacije.
+\end_layout
+
+\begin_layout Subsection
+Stirlingova števila 2.
+ vrste in Bellova števila
+\end_layout
+
+\begin_layout Definition*
+Razdelitev ali razbitje (ali particija) (angl.
+ set partition) množice 
+\begin_inset Formula $A$
+\end_inset
+
+ je množica množic (pravimo jim bloki) 
+\begin_inset Formula $\left\{ B_{1},\dots,B_{k}\right\} $
+\end_inset
+
+,
+ da velja:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\forall i\in\left[k\right]:B_{i}\not=\emptyset$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\forall i,k\in\left[k\right]:i\not=j\Rightarrow B_{i}\cap B_{j}=\emptyset$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\bigcup_{i=1}^{k}B_{i}=A$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Stirlingovo število druge vrste 
+\begin_inset Formula $S\left(n,k\right)$
+\end_inset
+
+ je število razdelitev množice 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ s 
+\begin_inset Formula $k$
+\end_inset
+
+ bloki.
+ Bellovo število 
+\begin_inset Formula $B\left(n\right)$
+\end_inset
+
+ je število vseh razdelive 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $S\left(4,2\right)=7$
+\end_inset
+
+;
+ 
+\begin_inset Formula $\left\{ 1,2,3,4\right\} $
+\end_inset
+
+ razdelimo na 
+\begin_inset Formula $\left\{ \left\{ \_\right\} ,\left\{ \_,\_,\_\right\} \right\} $
+\end_inset
+
+ 
+\begin_inset Formula $\times4$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\left\{ \left\{ \_,\_\right\} ,\left\{ \_,\_\right\} \right\} $
+\end_inset
+
+ 
+\begin_inset Formula $\times3$
+\end_inset
+
+ (fiksiramo enko v prvi blok,
+ imamo še tri izbire za njeno sosedo,
+ v drugem bloku so nato enolično določeni elementi)
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float table
+placement document
+alignment document
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset Tabular
+<lyxtabular version="3" rows="5" columns="2">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $n$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $B\left(n\right)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $S\left(4,1\right)+S\left(4,2\right)+S\left(4,3\right)+S\left(4,4\right)=1+7+6+1=15$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Bellova števila
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula $S\left(n,0\right)=\delta_{0,n}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $S\left(n,n\right)=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $B\left(n\right)=\sum_{k}S\left(n,k\right)$
+\end_inset
+
+,
+ 
+\begin_inset Formula $S\left(n,n-1\right)={n \choose 2}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Claim*
+Rekurzivna zveza.
+ 
+\begin_inset Formula $S\left(n,k\right)=S\left(n-1,k-1\right)+k\cdot S\left(n-1,k\right)$
+\end_inset
+
+,
+ 
+\begin_inset Formula $B\left(n+1\right)=\sum_{k=0}^{n}{n \choose k}B\left(k\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $B\left(4\right)={3 \choose 0}B\left(0\right)+{3 \choose 1}B\left(1\right)+{3 \choose 2}B\left(2\right)+{3 \choose 3}B\left(3\right)=1\cdot1+3\cdot1+3\cdot2+1\cdot5=15$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Ločimo vse razdelitve 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ s 
+\begin_inset Formula $k$
+\end_inset
+
+ bloki na dve disjunktni podmnožici:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\left\{ n\right\} $
+\end_inset
+
+ je blok:
+ takih je 
+\begin_inset Formula $S\left(n-1,k-1\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\left\{ n\right\} $
+\end_inset
+
+ ni blok:
+ takih je 
+\begin_inset Formula $S\left(n-1,k\right)\cdot k$
+\end_inset
+
+ —
+ 
+\begin_inset Formula $\cdot k$
+\end_inset
+
+ ker lahko v razdelitev 
+\begin_inset Formula $\left[n-1\right]$
+\end_inset
+
+ na 
+\begin_inset Formula $k$
+\end_inset
+
+ blokov 
+\begin_inset Formula $n$
+\end_inset
+
+ vstavimo na 
+\begin_inset Formula $k$
+\end_inset
+
+ načinov (v enega izmed 
+\begin_inset Formula $k$
+\end_inset
+
+ blokov)
+\end_layout
+
+\begin_layout Standard
+Vse razdelitve 
+\begin_inset Formula $\left[n+1\right]$
+\end_inset
+
+ —
+ Bellova števila:
+ Naj bo 
+\begin_inset Formula $n+1$
+\end_inset
+
+ v bloku s še 
+\begin_inset Formula $k$
+\end_inset
+
+ elementi,
+ 
+\begin_inset Formula $0\leq k\leq n$
+\end_inset
+
+.
+ Tedaj 
+\begin_inset Formula 
+\[
+B\left(n+1\right)=\sum_{k=0}^{n}{n \choose k}B\left(n+1-k-1\right)=
+\]
+
+\end_inset
+
+...
+ za rekurzijo si oglejmo razdelitve brez bloka z 
+\begin_inset Formula $n+1$
+\end_inset
+
+.
+ 
+\begin_inset Formula ${n \choose k}$
+\end_inset
+
+ predstavlja izbiro elementov,
+ ki so še skupaj z 
+\begin_inset Formula $n$
+\end_inset
+
+ ...
+\begin_inset Formula 
+\[
+=\sum_{k=0}^{n}{n \choose k}B\left(n-k\right)\overset{\text{štejmo v drugo smer}}{=}\sum_{k=0}^{n}{n \choose n-k}B\left(k\right)=\sum_{k=0}^{n}{n \choose k}B\left(k\right)
+\]
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Proof
+\begin_inset Float table
+placement document
+alignment document
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset Tabular
+<lyxtabular version="3" rows="7" columns="8">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $n\backslash k$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $B\left(n\right)$
+\end_inset
+
+ (vsota po vrstici)
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+7
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+25
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+10
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+52
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Stirlingova števila druge vrste
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+To nas spomni na ekvivalenčne razrede.
+\end_layout
+
+\begin_layout Definition*
+Ekvivalenčna relacija je refleksivna (
+\begin_inset Formula $x\sim x$
+\end_inset
+
+),
+ simetrična (
+\begin_inset Formula $x\sim y\Rightarrow y\sim x$
+\end_inset
+
+) in tranzitivna (
+\begin_inset Formula $x\sim y\wedge y\sim z\Rightarrow x\sim z$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Remark*
+Množica razpade na ekvivalenčne razrede,
+ ki tvorijo razdelitev.
+ 
+\begin_inset Formula $S\left(n,k\right)$
+\end_inset
+
+ je število ekvivalenčnih relacij na 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ s 
+\begin_inset Formula $k$
+\end_inset
+
+ ekvivalenčnimi razredi.
+ 
+\begin_inset Formula $B\left(n\right)$
+\end_inset
+
+ je število ekvivalenčnih relacij na 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+Za surjekcijo 
+\begin_inset Formula $f:\left[n\right]\to\left[k\right]$
+\end_inset
+
+ velja 
+\begin_inset Formula $\forall i\in\left[k\right]:f^{-1}\left(i\right)\not=\emptyset$
+\end_inset
+
+ (praslika je neprazna množica).
+ Ker je 
+\begin_inset Formula $f$
+\end_inset
+
+ funkcija,
+ velja 
+\begin_inset Formula $\forall i,j\in\left[k\right]:i\not=j\Rightarrow f^{-1}\left(i\right)\cap f^{-1}\left(i\right)=\emptyset$
+\end_inset
+
+ in 
+\begin_inset Formula $\bigcup_{i=1}^{k}f^{-1}\left(i\right)=\left[n\right]$
+\end_inset
+
+.
+ Surjekcija pa vseeno ni isto kot razdelitev —
+ pomemben je vrstni red blokov.
+\end_layout
+
+\begin_layout Question*
+Koliko surjekcij je iz 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ v 
+\begin_inset Formula $\left[k\right]$
+\end_inset
+
+?
+ Odgovor:
+ 
+\begin_inset Formula $S\left(n,k\right)\cdot k!$
+\end_inset
+
+ —
+ Surjekcija je razdelitev z vrstnim redom blokov.
+ Koliko je 
+\begin_inset Formula $\left[4\right]\to\left[2\right]$
+\end_inset
+
+ surjekcij?
+ Odgovor:
+ 
+\begin_inset Formula $S\left(4,2\right)\cdot2!=7\cdot2=14$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Premestitve so permutacije brez negibne točke.
+\end_layout
+
+\begin_layout Corollary*
+Od prej se spomnimo,
+ da je število surjekcij iz 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ v 
+\begin_inset Formula $\left[k\right]$
+\end_inset
+
+ enako 
+\begin_inset Formula $\sum_{j=0}^{k}\left(-1\right)^{k-j}\binom{k}{j}j^{n}$
+\end_inset
+
+.
+ Posledično je 
+\begin_inset Formula $S\left(n,k\right)=\sum_{j=0}^{k}\frac{\left(-1\right)^{k-j}j^{n}}{j!\left(k-j\right)!}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula 
+\[
+S\left(n,2\right)=\frac{2^{n}}{2}-\frac{1}{1}+\frac{\delta_{0,n}}{2!\cdot0!}=2^{n-1}-1+\frac{\delta_{n,0}}{2}
+\]
+
+\end_inset
+
+Razdelimo 
+\begin_inset Formula $n$
+\end_inset
+
+ elementov v 2 bloka.
+ Fiksirajmo 
+\begin_inset Formula $1$
+\end_inset
+
+ v prvi blok,
+ za vsak preostali (
+\begin_inset Formula $n-1$
+\end_inset
+
+ jih ostane) element pa imamo dvojiški enum,
+ ki pove,
+ v katerem bloku je.
+ 
+\begin_inset Formula $-1$
+\end_inset
+
+ zato,
+ ker mora biti drugi blok neprazen in izločimo opcijo,
+ kjer so vsi dvojiški enumi enaki 0,
+ 
+\begin_inset Formula $\delta_{n,0}$
+\end_inset
+
+ zato,
+ da popravimo primer,
+ ko je 
+\begin_inset Formula $n=0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $\sum_{k}S\left(n,k\right)x^{k}=?$
+\end_inset
+
+ TODO XXX FIXME NE RAZUMEM
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $n=3$
+\end_inset
+
+:
+ 
+\begin_inset Formula $\sum_{k}S\left(3,k\right)x^{k}=x+3x^{2}+x^{3}=?$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $\sum_{k}S\left(n,k\right)x^{\underline{k}}=x^{n}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $n=3$
+\end_inset
+
+:
+ 
+\begin_inset Formula $\sum_{k}S\left(3,k\right)x^{\underline{k}}=x+3x\left(x-1\right)+x\left(x-1\right)\left(x-2\right)=x\left(1\cancel{+3x}-3+x^{2}\cancel{-3x}+2\right)=x\left(\cancel{1-3}+x^{2}\cancel{+2}\right)=x^{3}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Več načinov.
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+Indukcija.
+ (na vajah)
+\end_layout
+
+\begin_layout Itemize
+Kombinatorično:
+ 
+\begin_inset Formula $x^{n}$
+\end_inset
+
+:
+ štetje
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+nizov dolžine 
+\begin_inset Formula $n$
+\end_inset
+
+ z elementi iz 
+\begin_inset Formula $\left[x\right]$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+preslikav iz 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ v 
+\begin_inset Formula $\left[x\right]=\left|\left[x\right]^{\left[n\right]}\right|$
+\end_inset
+
+.
+ Vsaka preslikava je surjekcija na svojo sliko.
+ Oglejmo si vse slike 
+\begin_inset Formula $T\subseteq\left[x\right]$
+\end_inset
+
+:
+\begin_inset Formula 
+\[
+x^{n}=\left|\left[x\right]^{\left[n\right]}\right|=\sum_{T\subseteq\left[x\right]}\left|T\right|!\cdot S\left(n,\left|T\right|\right)\overset{\text{po močeh \left|T\right|}}{=}\sum_{k}k!\cdot S\left(n,k\right){x \choose k}\overset{{x \choose k}=\frac{x^{\underline{k}}}{k!}}{=}\sum_{k}S\left(n,k\right)x^{\underline{k}}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Dokaz je veljaven za 
+\begin_inset Formula $x\in\mathbb{N}_{0}$
+\end_inset
+
+.
+ Da dokažemo,
+ da sta dva polinoma stopnje 
+\begin_inset Formula $\leq n$
+\end_inset
+
+ enaka,
+ je dovolj preveriti ujemanje v 
+\begin_inset Formula $n+1$
+\end_inset
+
+ različnih točkah,
+ kajti razlika je polinom stopnje 
+\begin_inset Formula $\leq n$
+\end_inset
+
+,
+ če ni ničeln ima 
+\begin_inset Formula $\leq n$
+\end_inset
+
+ ničel,
+ kar je v neskladju s tem,
+ da se polinoma ujemata v 
+\begin_inset Formula $n+1$
+\end_inset
+
+ točkah (v ničlah se ne).
+ Nmamo polinoma stopnje 
+\begin_inset Formula $n$
+\end_inset
+
+,
+ ki se ujemata v 
+\begin_inset Formula $\infty$
+\end_inset
+
+ točkah,
+ torej sta enaka.
+ Torej je dokaz veljaven tudi za realna števila.
+\end_layout
+
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout Subsection
+Lahova števila
+\end_layout
+
+\begin_layout Standard
+Imenujejo se po slovenskem aktuarju Ivu Lahu.
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $L\left(n,k\right)$
+\end_inset
+
+ je število razdelitev 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ na 
+\begin_inset Formula $k$
+\end_inset
+
+ linearno urejenih blokov.
+ 
+\begin_inset Formula $\left\{ 142,3674\right\} =\left\{ 3674,152\right\} $
+\end_inset
+
+,
+ toda 
+\begin_inset Formula $\left\{ 152,3674\right\} \not=\left\{ 125,3764\right\} $
+\end_inset
+
+.
+ Vrstni red znotraj bloka je pomemben,
+ ni pa pomemben vrstni red blokov.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $L\left(4,2\right)$
+\end_inset
+
+:
+ 
+\begin_inset Formula $\left\{ \left(\_\right),\left(\_,\_,\_\right)\right\} $
+\end_inset
+
+ 
+\begin_inset Formula $\times4\cdot3!$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\left\{ \left(\_,\_\right),\left(\_,\_\right)\right\} $
+\end_inset
+
+ 
+\begin_inset Formula $\times3\cdot2!\cdot2!$
+\end_inset
+
+ (enka v prvem bloku,
+ vrstni red v 1.
+ bloku,
+ vrstni red v 2.
+ bloku) 
+\begin_inset Formula $\Longrightarrow24+12=36=L\left(4,2\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+Rekurzivna zveza za Lahova števila:
+ 
+\begin_inset Formula $L\left(n,k\right)=L\left(n-1,k-1\right)+L\left(n-1,k\right)\cdot\left(n-1+k\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Ločimo razdelitve 
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+ na 
+\begin_inset Formula $k$
+\end_inset
+
+ linearno urejenih blokov v dve disjunktni podmnožici:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\left(n\right)$
+\end_inset
+
+ je blok:
+ takih je 
+\begin_inset Formula $L\left(n-1,k-1\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\left(n\right)$
+\end_inset
+
+ ni blok:
+ takih je 
+\begin_inset Formula $L\left(n-1,k\right)\cdot\left(n-1+k\right)$
+\end_inset
+
+ —
+ 
+\begin_inset Formula $n$
+\end_inset
+
+ lahko vstavimo nazaj bodisi za nek element (
+\begin_inset Formula $n-1$
+\end_inset
+
+ opcij) ali na začetek enega izmed blokov (
+\begin_inset Formula $k$
+\end_inset
+
+ opcij)
+\end_layout
+
+\end_deeper
+\begin_layout Claim*
+\begin_inset Formula $L\left(n,k\right)=\frac{n!}{k!}{k-1 \choose n-1}$
+\end_inset
+
+ za 
+\begin_inset Formula $n,k\geq1$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $L\left(4,2\right)=\frac{4!}{2!}{3 \choose 1}=36$
+\end_inset
+
+,
+ 
+\begin_inset Formula $L\left(n,n\right)=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $L\left(n,1\right)=n!$
+\end_inset
+
+,
+ 
+\begin_inset Formula $L\left(n,n-1\right)=n\left(n-1\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Preštejmo urejene razdelitve na linearno urejene bloke na dva načina:
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+uredimo bloke in množimo z razdelitvami 
+\begin_inset Formula $=k!\cdot L\left(n,k\right)=n!{n-1 \choose k-1}=$
+\end_inset
+
+ permutacije množimo s kompozicijami (pregrade)
+\end_layout
+
+\end_deeper
+\begin_layout Theorem*
+\begin_inset Formula 
+\[
+\sum_{k}L\left(n,k\right)x^{\underline{k}}=x^{\overline{n}}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Induktivni.
+ Baza 
+\begin_inset Formula $n=0$
+\end_inset
+
+.
+ Korak 
+\begin_inset Formula $n-1\to n$
+\end_inset
+
+:
+\begin_inset Formula 
+\[
+x^{\overline{n}}=x^{\overline{n-1}}\left(x+n-1\right)=\left(\sum_{k}L\left(n-1,k\right)x^{\underline{k}}\right)\cdot\left(x+n-1=\left(x-k\right)+\left(n+k-1\right)\right)=
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+=\sum_{k}L\left(n-1,k\right)x^{\underline{k+1}}\left(+\sum_{k}L\left(n-1,k\right)x^{\underline{k}}\right)\cdot\left(n+k-1\right)=\sum_{k}L\left(n-1,k-1\right)x^{\underline{k}}+\left(\sum_{k}L\left(n-1,k\right)x^{\underline{k}}\right)\cdot\left(n+k-1\right)=\sum_{k}L\left(n,k\right)x^{\underline{k}}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Remark*
+Nekaj opomb.
+\begin_inset Formula 
+\[
+S\left(n,k\right)\leq c\left(n,k\right)\leq L\left(n,k\right)
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\sum_{k}c\left(n,k\right)x^{\underline{k}}=x^{n}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\sum_{k}L\left(n,k\right)x^{\underline{k}}=x^{\overline{n}}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\sum_{k}c\left(n,k\right)\left(-1\right)^{k}x^{k}=\left(-1\right)^{n}x^{\underline{n}}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\sum_{k}\left(-1\right)^{n-k}c\left(n,k\right)x^{k}=x^{\underline{n}}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\sum_{k}\left(-1\right)^{n-k}S\left(n,k\right)x^{\overline{k}}=x^{n}
+\]
+
+\end_inset
+
+
+\begin_inset Formula 
+\[
+\sum_{k}\left(-1\right)^{n-k}L\left(n,k\right)x^{\overline{k}}=x^{\underline{n}}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Paragraph*
+Operacije v algebri
+\end_layout
+
+\begin_layout Standard
+seštevanje,
+ množenje,
+ množenje s skalarjem.
+\end_layout
+
+\begin_layout Standard
+seštevanje+množenje nam data kolobar,
+ seštevanje in množenje s skalarjem vektorski prostor,
+ vse troje pa (komutativno) algebro.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $m\times m$
+\end_inset
+
+ matrike so nekomutativne algebre.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\mathbb{R}\left[x\right]$
+\end_inset
+
+ je neskončnorazsežen vektorski prostor.
+ Ena baza je 
+\begin_inset Formula $\left\{ 1,x,x^{2},\dots\right\} $
+\end_inset
+
+,
+ spet druga je 
+\begin_inset Formula $\left\{ 1,x,x^{\underline{2}},x^{\underline{3}},\dots\right\} $
+\end_inset
+
+,
+ še ena je 
+\begin_inset Formula $\left\{ 1,x,x^{\overline{2}},x^{\overline{3}},\dots\right\} $
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+Naših šest polinomskih zvez nam daje prehodne matrike med bazami.
+ 
+\begin_inset Formula $\left(-1\right)^{n-k}c\left(n,k\right)\eqqcolon s\left(n,k\right)$
+\end_inset
+
+ (predznačeno stirlingovo število prve vrste).
+\end_layout
+
+\begin_layout Subsection
+Razčlenitve in eulerjev petkotniški izrek
+\end_layout
+
+\begin_layout Definition*
+Razčlenitev (angl.
+ integer partition) 
+\begin_inset Formula $n\in\mathbb{N}_{0}$
+\end_inset
+
+ je zaporedje 
+\begin_inset Formula $\lambda_{1},\dots,\lambda_{l}$
+\end_inset
+
+;
+ 
+\begin_inset Formula $\forall i\in\left[l\right]:\lambda_{l}>0$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{l}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda_{1}+\cdots+\lambda_{l}=n$
+\end_inset
+
+.
+ Dodaten pogoj za razliko od kompozicij je linearna urejenost zaporedja (vrstni red ni pomemben).
+ 
+\begin_inset Formula $\lambda_{i}$
+\end_inset
+
+ so členi razčlenitve,
+ 
+\begin_inset Formula $l$
+\end_inset
+
+ je njena dolžina in 
+\begin_inset Formula $n$
+\end_inset
+
+ njena velikost.
+ S 
+\begin_inset Formula $p_{k}\left(n\right)$
+\end_inset
+
+ označimo število razčlenitev 
+\begin_inset Formula $n$
+\end_inset
+
+ dolžine 
+\begin_inset Formula $k$
+\end_inset
+
+,
+ s 
+\begin_inset Formula $\overline{p_{k}}\left(n\right)$
+\end_inset
+
+ označimo število razčlenitev dolžine 
+\begin_inset Formula $\leq k$
+\end_inset
+
+,
+ s 
+\begin_inset Formula $p\left(n\right)$
+\end_inset
+
+ pa število razčlenitev 
+\begin_inset Formula $n$
+\end_inset
+
+ (vseh dolžin).
+\end_layout
+
+\end_body
+\end_document