Matematické Fórum

elite1989 · 28. 02. 2010 22:13

Zdravím všechny matematiky,

prosím Vás......mám se dokázat, že množina všech podmnožin základního prostoru Ω=(ω1,ω2,ω3....ωn) má právě 2 na n prvků. (Návod: zkuste použít binomickou větu nebo matematickou indukci)

Takhle zní zadání (včetně nápovědy :-D). No profesor říkal, že to je na jedno odpoledne....já sem to řešil pár hodin a sem z toho jalovej. Tak pls, kdo ví, ať pomůže. Děkuji

Pavel Brožek · 28. 02. 2010 22:42

Zdravím, zkusím dát nápovědu, kdyžtak se ptej dál.

Binomickou větou: Kolik je podmnožin velkosti 0? Velikosti 1? ... Velikosti n? A když to všechno sečteme?

Indukcí: Pro n=0 triviální. Máme množinu o velikosti n+1. Kolik bude podmnožin obsahujících ω1? Kolik těch, které ω1 neobsahují?

Ještě se to dá dělat pomocí bijekce: Máme množinu velikosti n. Každé podmnožině přiřadíme n-tici čísel 0 nebo 1. Na i-té pozici bude 0, pokud ωi je v podmnožině, 1, pokud ωi není v podmnožině. Tohle zobrazení je zřejmě bijekce mezi podmnožinami a n-ticemi nul a jedniček. Je už asi zřejmé, kolik takových n-tic bude.

elite1989 · 28. 02. 2010 23:25

↑ BrozekP:

:-D no po 1 přednášce z pravděpodobnosti z toho nejsem moc moudrej :-D ale co se týká tý binomický věty..přes kterou sem se to snažil udělat.....když dam suma (0+1+2+....+n)...tak to nedokážu matematicky upravit aby mi vyšlo 2na n. A protože sem si timhle řešenim nebyl jistý, tak jsem sem dal raději rovnou zadání :-) ...sčítal sem to jako polynom (ikdyž to neni polynom), pak sem zkoušel Einsteinovu konvenci...ale prostě at to udělam jak chci 2 na n nevyjde. abych se styděl co :-(

Stýv · 01. 03. 2010 00:01 — Editoval Stýv (01. 03. 2010 00:39)

nemáš sčítat čísla 0,...,n, ale počty podmnožin velikosti 0,...,n

EDIT: opraveno

Pavel Brožek · 01. 03. 2010 00:20

↑ Stýv:

Počty podmnožin velikosti 0, ..., n.

↑ elite1989:

Einsteinovu konvenci? Možná má Einstein víc konvencí, já znám pouze tu, že se nepíše suma a sčítá se přes stejný dolní a horní index. Tou ale podle mě nic nemůžeš sečíst, pouze zjednodušit zápis. Jak se "sčítá jako polynom" mně teď taky nedochází.

Kolika způsoby můžeš z n prvků vybrat k prvků, přičemž nezáleží na pořadí vybraných prvků? (To je to samé jako vybrat podmnožinu o velikosti k z množiny o velikosti n.) Pokud na tuto otázku nedokážeš odpovědět, pak je nejprve nutné nastudovat teorii - v tomto případě Kombinace.

elite1989 · 01. 03. 2010 23:30

↑ BrozekP:

na mě musíte pomalu :-)

došlo mi že ta kombinace bude teda n nad k, jenže když n a tedy i k je nekonečno, tak pořád nevim jak dostanu 2 na n. Zkoušel sem si dosadit (1 nad 1)+ (2nad1)...atd...a nic moc. Pak jsem zkusil přímo do binomický věty za x a y 1...a ano pak mi vyjde 2 na n = n nad k. Ale jako to je pokus omyl...nevim co mi na to řeknete :-) Jinak teda už opravdu nevím....:-( omlouvam se

Kondr · 01. 03. 2010 23:33

↑ elite1989: Myslím, že zde žádná nekonečna nevystupují.

elite1989 · 01. 03. 2010 23:38

↑ Kondr:

ano...jasně..je to konečný počet....jako 2 na n, jenže do čeho to dosadim nebo jakym způsobem z n nad k dostanu to 2 na n to je mi záhada.

Kondr · 01. 03. 2010 23:50

Do čeho dosadit? Spousty možností

a) kombinatoricky: první prvek prostoru do podmnožiny dám nebo nedám (dvě možnosti), druhý tam dám nebo nedám (2 možnosti) ... takto mám dvě možnosti rozhodnutí pro n prvků a to nezávisle, proto celkem 2^n možností.

b) z binomické věty: ta pro x=1, y=1 dává $(1+1)^n={n\choose 0}+{n\choose 1}+\cdots+{n\choose n}$ . To nalevo je $2^n$ , to napravo je počet podmnožin naší množiny.

c) indukcí: bázový krok triviální. V indukčním máme 2^t množin velikosti t, k nim buď přidáme nebo nepřidáme t+1. prvek, to jsou dvě možnosti, celkem 2^(t+1) množin.

d) indukcí přes ${n+1\choose k+1}={n\choose k+1}+{n\choose k}$

e) ...

elite1989 · 02. 03. 2010 00:35

↑ Kondr:

tak to nemá chybu. děkuju Pavlovi který mi to vysvětlil na binomický větě a vlastně i kombinatoricky...a když sem si ted přečetl report od kondra, tak mi to úplně doteklo. Jen doufám, že si to v hlavě udržím dýl než většinu matematických pojmů :-D. Tak díky všem co jsou díky mě o pár let starší....bohužel nemohu slíbit, že sem už nikdy nenapíšu :-))

Matematické Fórum

#1 28. 02. 2010 22:13

Pravděpodobnost-důkaz

#2 28. 02. 2010 22:42

Re: Pravděpodobnost-důkaz

#3 28. 02. 2010 23:25

Re: Pravděpodobnost-důkaz

#4 01. 03. 2010 00:01 — Editoval Stýv (01. 03. 2010 00:39)

Re: Pravděpodobnost-důkaz

#5 01. 03. 2010 00:20

Re: Pravděpodobnost-důkaz

#6 01. 03. 2010 23:30

Re: Pravděpodobnost-důkaz

#7 01. 03. 2010 23:33

Re: Pravděpodobnost-důkaz

#8 01. 03. 2010 23:38

Re: Pravděpodobnost-důkaz

#9 01. 03. 2010 23:50

Re: Pravděpodobnost-důkaz

#10 02. 03. 2010 00:35

Re: Pravděpodobnost-důkaz

Zápatí