#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