#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
