Kombinatorika a grafy I

(1)

Kombinatorika a grafy I

Martin Balko

2. pˇredn´ aˇska

26. ´unora 2019

(2)

Vytvoˇruj´ıc´ı funkce

(3)

Pˇr´ıklad ze ˇzivota

• Kolika zp˚usoby m˚uˇzeme naplnit koˇs´ıkn ∈N0 kousky ovoce tak, aby:

◦ poˇcet jablek byl sud´y,

◦ poˇcetˇsvestek byl n´asobek pˇeti,

◦ v koˇs´ıku byly nanejv´yˇs ˇctyˇripomeranˇce

◦ a nanejv´yˇs jedno avok´ado?

Zdroj: https://123RF.com

• Zaj´ımá nás koeficient u xⁿ v mocninné ˇradˇe

(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +x+· · ·+x⁴)(1 +x).

• Se znalostmi z dneˇsn´ı pˇredn´aˇsky budeme schopni naj´ıt odpovˇed’: n+ 1.

(4)

Pˇr´ıklad ze ˇzivota

(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +x+· · ·+x⁴)(1 +x).

(5)

Pˇr´ıklad ze ˇzivota

(1 +x² +x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +x+· · ·+x⁴)(1 +x).

(6)

Pˇr´ıklad ze ˇzivota

(1 +x² +x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +x+· · ·+x⁴)(1 +x).

• Se znalostmi z dneˇsn´ı pˇredn´aˇsky budeme schopni naj´ıt odpovˇed’:

n+ 1.

(7)

Pˇr´ıklad ze ˇzivota

(1 +x² +x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +x+· · ·+x⁴)(1 +x).

(8)

Z´ akladn´ı operace s mocninn´ ymi ˇradami

a(x) +b(x) (a₀+b₀,a₁+b₁,a₂+b₂, . . .)

αa(x) (αa₀, αa₁, αa₂, . . .)

xⁿa(x) (0, . . . ,0,a₀,a₁,a₂, . . .) (n nul na zaˇc´atku)

a(x)−a₀−···−an−1xⁿ⁻¹

xⁿ (a_n,a_n+1,a_n+2, . . .)

a(αx) (a₀, αa₁, α²a₂, . . . , αⁱa_i, . . .)

a(xⁿ) (a0,0, . . . ,0,a1,0, . . .) (stˇr´ıdavˇe n−1 nul) a⁰(x) (a₁,2a₂,3a₃, . . . ,ia_i, . . .)

Rx

0 a(t)dt (0,a₀,â₂¹,â₃², . . . ,_i+1âⁱ , . . .)

a(x)b(x) (c₀,c₁,c₂, . . .), kde c_n=Pn

i=0a_ib_n−i

(9)

K pˇr´ıkladu ze ˇzivota

• Zaj´ımá nás koeficientan v mocninné ˇradˇe

∞

X

n=0

a_nxⁿ =(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +· · ·+x⁴)(1 +x)

= 1

1−x² · 1

1−x⁵ · 1−x⁵

1−x ·(1 +x)= 1 (1−x)².

• Plat´ı _1−x¹ 0

= _(1−x)¹ 2 a tedy podle operace derivace m´ame koeficient a_n=n+ 1.

(10)

K pˇr´ıkladu ze ˇzivota

• Zaj´ımá nás koeficienta_n v mocninné ˇradˇe

∞

X

n=0

a_nxⁿ =(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +· · ·+x⁴)(1 +x)

= 1

1−x² · 1

1−x⁵ · 1−x⁵

1−x ·(1 +x)= 1 (1−x)².

• Plat´ı _1−x¹ 0

(11)

K pˇr´ıkladu ze ˇzivota

∞

X

n=0

a_nxⁿ =(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +· · ·+x⁴)(1 +x)

= 1

1−x² · 1

1−x⁵ · 1−x⁵

1−x ·(1 +x)

= 1

(1−x)².

• Plat´ı _1−x¹ 0

(12)

K pˇr´ıkladu ze ˇzivota

∞

X

n=0

a_nxⁿ =(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +· · ·+x⁴)(1 +x)

= 1

1−x² · 1

1−x⁵ · 1−x⁵

1−x ·(1 +x)= 1 (1−x)².

• Plat´ı _1−x¹ 0

(13)

K pˇr´ıkladu ze ˇzivota

∞

X

n=0

a_nxⁿ =(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +· · ·+x⁴)(1 +x)

= 1

1−x² · 1

1−x⁵ · 1−x⁵

1−x ·(1 +x)= 1 (1−x)².

• Plat´ı _1−x¹ 0

= _(1−x)¹ 2 a tedy podle operace derivace m´ame koeficient

a_n=n+ 1.

(14)

K pˇr´ıkladu ze ˇzivota

∞

X

n=0

a_nxⁿ =(1 +x²+x⁴+· · ·)(1 +x⁵+x¹⁰+· · ·)(1 +· · ·+x⁴)(1 +x)

= 1

1−x² · 1

1−x⁵ · 1−x⁵

1−x ·(1 +x)= 1 (1−x)².

• Plat´ı _1−x¹ 0

(15)

Fibonacciho ˇc´ısla

• Definov´ana rekurzivnˇe: F0 = 0, F1 = 1 aFn =Fn−1+Fn−2 pro n≥2.

• V Indii zn´ama jiˇz od starovˇeku, v Evropˇe poprv´e zm´ınˇena v knize Liber Abaci (1202) odFibonacciho (1170–1250).

• Mnoˇzstv´ıaplikac´ıv matematice a informatice (sloˇzitost Eukleidova algoritmu, Fibonacciho haldy, Fibonacciho k´odov´an´ı ˇc´ısel, . . .).

• Fibonacciho ˇc´ısla souvis´ı se zlat´ym ˇrezem ¹⁺

√ 5

2 = 1.618. . .

Obr´azek:Fibonacciho spir´ala a kde ji (ne)hledat.

Zdroj: http://pixdaus.com

(16)

Fibonacciho ˇc´ısla

• Definov´ana rekurzivnˇe: F0 = 0, F1 = 1 aFn =Fn−1+Fn−2 pro n ≥2.

• V Indii zn´ama jiˇz od starovˇeku, v Evropˇe poprv´e zm´ınˇena v knize Liber Abaci (1202) odFibonacciho (1170–1250).

√ 5

2 = 1.618. . .

(17)

Fibonacciho ˇc´ısla

• V Indii zn´ama jiˇz od starovˇeku, v Evropˇe poprv´e zm´ınˇena v knize Liber Abaci(1202) od Fibonacciho (1170–1250).

√ 5

2 = 1.618. . .

21

13

5 8 3 2

Zdroj: http://insteading.com

(34)

Binet˚ uv vzorec

• Vytvoˇruj´ıc´ı funkce lze pouˇz´ıt k odvozen´ıBinetova vzorce: F_n = 1

√5

" 1 +√

5 2

!n

− 1−√ 5 2

!n#

Obr´azek:Jacques P. M. Binet(1786–1856) aAbraham de Moivre (1667–1754).

Zdroje: http://matematicaenigmatica.blogspot.com a http://cs.wikipedia.org

(35)

Binet˚ uv vzorec

• Vytvoˇruj´ıc´ı funkce lze pouˇz´ıt k odvozen´ıBinetova vzorce:

F_n = 1

√5

"

1 +√ 5 2

!n

− 1−√ 5 2

!n#

(36)

Binet˚ uv vzorec

• Vytvoˇruj´ıc´ı funkce lze pouˇz´ıt k odvozen´ıBinetova vzorce:

F_n = 1

√5

"

1 +√ 5 2

!n

− 1−√ 5 2

!n#

(37)

Kuchaˇrka: rozklad na parci´ aln´ı zlomky

• Vstup: pod´ıl ^p(x)_q(x) polynom˚u s st(p(x))<st(q(x)), kdeq(x) m´a rozklad q(x) = (x−a1)ⁿ¹· · ·(x−aN)ⁿ^N(x²+α1x+β1)^m¹· · ·(x²+αMx+βM)^m^M.

• Výstup: rozklad R racionáln´ı funkce ^p(x)_q(x) na parciáln´ı zlomky.

• Metoda: Za kaˇzd´y ˇclen (x−ai)ⁿⁱ pˇridat do rozkladuR A_i_,1

x −a_i + A_i,2

(x −a_i)² +· · ·+ A_i_,n_i (x −a_i)ⁿⁱ a za kaˇzd´y ˇclen (x²+α_ix+β_i)^mⁱ pˇridat do rozkladu R

B_i,1x+C_i,1 x²+αix +βi

+ B_i,2x +C_i_,2

(x²+αix +βi)² +· · ·+ B_i_,m_ix +C_i_,m_i (x²+αix +βi)^mⁱ.

Rovnici ^p(x)_q(x) =R vynásobit ˇclenem q(x) a po pokrácen´ı dostat za kaˇzdý ˇclen výsledného polynomuRq(x) jednu rovnici. Celkovˇe dostaneme systém lineárn´ıch rovnic s n₁ +· · ·+n_N+ 2m₁+· · ·+ 2m_M promˇennými Ai,j, Bi,j a Ci,j. Ten pak staˇc´ı vyˇreˇsit.

(38)

Zdroj: Good Will Hunting.

Dˇekuji za pozornost.

(39)

Zdroj: Good Will Hunting.