Dva pitanja, jedno bez ideje :( (SUMA)

Re: Dva pitanja, jedno bez ideje :( (SUMA) 03.05.2012. u 12:02 · pre 176 meseci #21

Jel' moze neko objasnjenje zasto je $|S|= {{n+10}\choose{11}}$ ?

Re: Dva pitanja, jedno bez ideje :( (SUMA) 03.05.2012. u 13:53 · pre 176 meseci #22

Citat:

Kako na pocetku broja? 003 je trocifren broj? Pa onda je i stocifren :) Ako se trazi tako nesto onda je pogresno reci n-tocifren broj, mozda uredjena n-torka cifara ili slicno...

ma imao sam neku ideju preko kombinacija ali bi ona ukljucivala i nule na pocetku broja, sto je problematicno...

Re: Dva pitanja, jedno bez ideje :( (SUMA) 03.05.2012. u 14:07 · pre 176 meseci #23

Citat:

Neka je $S$ skup resenja jednacine $x_1+x_2+\cdots+x_n=11$ u skupu $\bf{N}_0$ . Neka su $A$ , $B$ i $C$ redom skupovi onih resenja iz $S$ za koje vaze uslovi: (a) $x_1=0$ ; (b) jedan od brojeva $x_1,x_2,\dots,x_n$ jednak je 11; (c) jedan od brojeva $x_1,x_2,\dots,x_n$ jednak je 10. Tada je $\input amstex |S|=\binom {n+10} {11}, ~ |A|=\binom{n+9}{11},~|B|=n,~|C|=n(n-1),~|A\cap B|=n-1,~|B\cap C|=0, |C \cap A|=(n-1)(n-2)$ . Trazeni broj jednak je
$\input amstex |S \setminus (A \cup B \cup C)| = |S|-|A|-|B|-|C|+|A \cap B| +|B \cap C| + |C \cap A| - |A \cap B \cap C| = \binom{n+9}{10}-2n+1.$

Resenje je uzeto iz Kombinatorike (glava 4, zadatak 6) Pavla Mladenovica.

hvala.
Da li neko može da objasni ovo malo detaljnije?

Re: Dva pitanja, jedno bez ideje :( (SUMA) 03.05.2012. u 22:11 · pre 176 meseci #24

Postoji teorema koja kaze da broj nenegativnih resenja jednacine $x_1 + x_2 + \cdots + x_k =n$ (gde su $k \ge 1$ i $n\ge 1$ ) iznosi $\input amstex \binom {n+k-1}{n}$ . Dokaz ovog tvrdjenja mozete naci OVDE, strana 111. (ne mora bas preko ove teoreme, moze i preko posmatranja varijacija odredjenog tipa)

I mislim da je sad jasno zasto je $\input amstex |S|=\binom{11+n-1}{11}=\binom{n+10}{11}$ .

Dalje, mislim da je jasno zasto posmatramo jednacinu $x_1+x_2+\cdots+x_n=11$ . E sad, koja nama ovde resenja ne valjaju? Pa, ako je prva cifra nula, onda nam to resenje ne valja, jer onda to nije n-tocifreni broj, vec n-1-tocifren (il cak i manje, ako imas jos takvih nula). Da bi nasli koliko je takvih resenja, msm da je jasno da se to svodi na odredjivanje koliko jednacina $x_2+x_3+\cdots+x_n=11$ ima resenja. Takodje, nama su $x_i$ jednocifreni brojevi, tako da nam ne odgovaraju ni resenja u kojima je za neko $i \in \{1,\dots,n\}~~x_i=10$ , odnosno $x_i = 11$ . Dakle, od svih resenja, oduzecemo uniju ovakvih resenja (koja nam ne valjaju), i primeniti princip ukljucenja-iskljucenja. Ako je $x_i=11$ , onda su ostali clanovi jednaki nuli (dakle, jedinstveno su odredjeni), tako da nam ostaje samo da kazemo da imamo $n$ nacina kako cemo da dodelimo vrednost 11 nekom $x_i$ . Slicno za slucaj ako je $x_i=10$ (za neko $i$ ), onda je jos jedan broj jednak jedinici, a ostali su nuli. Dakle, imamo n mogucnosti za to kome cemo da dodelimo 10 (ili 1, svejedno je), a zatim za n-1 broj odredjujemo kome cemo da dodelimo 1, dakle, ukupno $n(n-1)$ . Za formulu ukljucenja-iskljucenja nam trebaju i neki preseci, al to mozes i sam da vidis zbog cega je njihova kardinalost tolika (koliko je napisano).

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 03.05.2012. u 23:07 · pre 176 meseci #25

Ha, sjajno, pogledao sam taj dokaz, odusevila me jednostavnost. Jos jedan dokaz da je ideja, tj. pristup, veoma vazan u matematici. Ja sam se neko vreme cesao po glavi, pokusavajuci da dobijem tu opstu formulu, dobro je da sam odustao :) U svakom slucaju, mislim da je ovo vazan deo zadatka (mozda jedini netrivijalan). Posto je tekst na engleskom, a i malo je sazet, ja cu prepricati (ako dozvoljavate :) taj dokaz ovde:

Neka su dati n i k; treba $x_1 + x_2 + \cdots + x_k =n$ pretvoriti u nesto kombinatorno iskazivo:

zamislimo n + k - 1 "kucica" i da treba da izaberemo k-1 od njih u koje postavimo znak "+", sto ostavlja n praznih kucica;

korespodencija sa datom jednacinom je sledeca: ako niz uzastopnih kucica zamenimo sa njihovim brojem (dakle 2 prazne uzastopne kucice su 2 itd), dobijamo jednu mogucu varijantu trazenog zbira; pritom, ako nema kucica izmedju dva znaka +, to zamenjujemo sa 0 (ako niz pocinje sa + ili zavrsava sa +, to je takodje 0); s' obzirom da praznih kucica ima n, ukupan zbir ovih brojeva jeste n.

Radi ilustracije, evo jednog primera za n=4, k=5: . . + + . + . + korespondira 2 + 0 + 1 + 1 + 0.

Ovakvih izbora ima, naravno, ${{n+k-1}\choose{k-1}} = {{n+k-1}\choose{n}}$

Re: Dva pitanja, jedno bez ideje :( (SUMA) 04.05.2012. u 17:01 · pre 176 meseci #26

puno hvala na objašnjejima. Nisam ni slutio da je rešenje do te mere komplikovano.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 04.05.2012. u 20:55 · pre 176 meseci #27

Pa, sad, pitanje je sta vam je dato na raspolaganje. Npr, da li u arsenalu imate tu teoremu koju je Sonec naveo, u vezi resenja jednacine sa k nepoznatih u N0... Mislim da svakako nije namera zadatka da se ona dokazuje. Navedeno resenje direktno se oslanja na tu teoremu, prilagodjavajuci rezultat zadatku; dakle ocigledno nije jednostavno primeniti direktnu logiku, tj. naci ta resenja u skupu cifara. Dalje, izgleda kao i da broj 11 nije slucajno izabran, jer je dovoljno izbaciti samo 10 i 11; zamisli da je tu neki pristojno veci broj, ko bi napravio sve te preseke i odredio im broj elemenata...

Dakle, ja bih zakljucio da je namera zaista koriscenje pomenute teoreme (osim ako postoji neki laksi direktan nacin, sto izgleda malo verovatno). Ostalo je manje-vise prosta logika, racunajuci i kombinatorni deo i deo oko formule za broj elemenata skupa S\{AuBuC}.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 21.05.2012. u 01:32 · pre 176 meseci #28

Da ne otvaram novu temu...
Kako da uporedim brojeve
$3^{3^{.^{.^{.^3}}}}$ (2012 trojki) i $4^{4^{.^{.^{.^4}}}}$ (2011 cetvorki) ?
Pokusao sam da logaritmujem oba broja, da bih "spustio" eksponente ispred, ali dobijam nesto tipa $3^{2011} log 3$ i slicno za 4, sto ne umem da uporedim...

Re: Dva pitanja, jedno bez ideje :( (SUMA) 21.05.2012. u 03:32 · pre 176 meseci #29

Za $v\geq 1$ i $u>2v+1$ važi $3^u>2\cdot 4^v+1$ . Obzirom da je $3^3>2\cdot 4+1$ , možeš indukcijom da kompletiraš rešenje.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 17.06.2012. u 22:27 · pre 175 meseci #30

Imam novi problem, a izgleda ovako
$\sum_{k=1}^{n}k{{n}\choose{k}}^2 , n\in N$
Treba izračunati ovu sumu.
Do sada sam od Nedeljka naučio da možda treba tražiti binom koji bi se uklopio u ovu sumu... Ne ide mi.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 17.06.2012. u 23:36 · pre 175 meseci #31

Evo sta kaze Pavle Mladenovic:
Izjednaciti koeficijente uz $x^{n-1}$ kod polinoma u sledecoj jednakosti $\input amstex n(1+x)^{2n-1} = \sum_{k=0}^{n} \binom{n}{k} x^k \sum_{j=1}^{n} j \binom{n}{j}x^{n-j}$ .
Inace, resenje je $\input amstex n \binom{2n-1}{n-1}$ .

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 18.06.2012. u 00:29 · pre 175 meseci #32

Pavle Mladenović verovatno ume da dođe do tog rešenja. Ja -ne

ali hvala za hint

Re: Dva pitanja, jedno bez ideje :( (SUMA) 18.06.2012. u 01:09 · pre 175 meseci #33

Pa nista, razvijes $(1+x)^{2n-1}$ i pogledas koeficijent uz $x^{n-1}$ , a zatim razvijas i desnu stranu, i gledas sve moguce koeficijente koje stoje uz $x^{n-1}$ . Odnosno, gledas kad je $x^k \cdot x^{n-j}$ stepena $n-1$ (za $k=...$ je $j=...$ i to uvrscavas u formulu) i kad to sve pogledas dobices sumu koja se trazi u zadatku.

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 17.11.2012. u 16:01 · pre 170 meseci #34

Da ne otvaram novu temu, pitaću ovde.

Kaže, izračunati sumu
$S_n=2^3 {n \choose 2}+3^3 {n \choose 3}+ \dots + n^3 {n \choose n} , n \in N$

Čini mi se da je ova suma jednaka
$\sum_{k=0}^{n} k^3 {n \choose k} - n$ jer moramo odbiti prve članove ali dalje ne umem. Ovaj pokušaj je bio usmeren na neko eventualno iskorišćavanje binomnog obrasca, ali... :( Ne umem da fiksiram ovaj eksponent, a da mi suma vrti osnovu. Kod binomnog je obratno

Takođe, zadatak kaže za $n \in N$ ali meni nije jasno npr za $n=1$ . Ispada da se javlja $1 \choose 2$ .
Ako može pomoć ;)

Re: Dva pitanja, jedno bez ideje :( (SUMA) 17.11.2012. u 19:18 · pre 170 meseci #35

$\input amstex (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k$ , uzmimo $\frac{d}{dx}$ na obe strane, dobijamo
$\input amstex n(1+x)^{n-1}=\sum_{k=1}^nk\binom{n}{k}x^{k-1}$ , pomnozimo sa $x$ , dobijamo
$\input amstex nx(1+x)^{n-1}=\sum_{k=1}^nk\binom{n}{k}x^{k}$ , uzmimo $\frac{d}{dx}$ na obe strane, dobijamo
$\input amstex n(1+x)^{n-2}(nx+1)=\sum_{k=1}^nk^2\binom{n}{k}x^{k-1}$ , pomnozimo sa $x$ , dobijamo
$\input amstex nx(1+x)^{n-2}(nx+1)=\sum_{k=1}^nk^2\binom{n}{k}x^{k}$ , uzmimo $\frac{d}{dx}$ na obe strane, dobijamo
$\input amstex n(1+x)^{n-3}(n^2x^2+(3n-1)x+1)=\sum_{k=1}^nk^3\binom{n}{k}x^{k-1}$ , pomnozimo sa $x$ , dobijamo
$\input amstex nx(1+x)^{n-3}(n^2x^2+(3n-1)x+1)=\sum_{k=1}^nk^3\binom{n}{k}x^{k}$

Stavimo da je $x=1$ , dobijamo $\input amstex \sum_{k=0}^n k^3\binom{n}{k} = 2^{n-3}n^2(n+3)$

Prema tome, konacno resenje je $2^{n-3}n^2(n+3) - n$

Za tvoje pitanje: http://mathworld.wolfram.com/BinomialCoefficient.html

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

1

Re: Dva pitanja, jedno bez ideje :( (SUMA) 17.11.2012. u 19:26 · pre 170 meseci #36

$(1+x)^n=\sum_{k=0}^n{n\choose k}x^k$ .

Diferenciranjem se dobija da je

$n(1+x)^{n-1}=\sum_{k=1}^n{n\choose k}kx^{k-1}$ .

Množenjem sa $x$ dobija se da je

$nx(1+x)^{n-1}=\sum_{k=1}^n{n\choose k}kx^k$ .

Diferenciranjem se dobija da je

$n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2}=\sum_{k=1}^n{n\choose k}k^2x^{k-1}$ .

Množenjem sa $x$ dobija se da je

$nx(1+x)^{n-1}+n(n-1)x^2(1+x)^{n-2}=\sum_{k=1}^n{n\choose k}k^2x^k$ .

Diferenciranjem se dobija da je

$n(1+x)^{n-1}+2n(n-1)x(1+x)^{n-2}+n(n-1)(n-2)x^2(1+x)^{n-3}=\sum_{k=1}^n{n\choose k}k^3x^{k-1}$ .

Zmenjujući $x$ sa 1 dobija se da je

$2^{n-1}n^2+n(n-1)(n-2)2^{n-3}=\sum_{k=1}^n{n\choose k}k^3$ ,

odnosno,

$\sum_{k=2}^n{n\choose k}k^3=2^{n-3}n(n-1)(n+2)-n$ .

Preteče me Sonec.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

1

Re: Dva pitanja, jedno bez ideje :( (SUMA) 17.11.2012. u 21:26 · pre 170 meseci #37

Zahvaljujem na detaljnom rešenju.
Da li možda znate u kojoj zbirci može da se nađe ovaj zadatak i još neki njemu slični ?

Re: Dva pitanja, jedno bez ideje :( (SUMA) 18.11.2012. u 07:35 · pre 170 meseci #38

Meni su se potkrale neke greške u računu, ali postupak je taj. Sonec je izračunao tačno.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Dva pitanja, jedno bez ideje :( (SUMA) 18.11.2012. u 12:13 · pre 170 meseci #39

Greška je nakon trećeg diferenciranja i sređivanja.U srednjem članu.

umjesto: $2x$ ispraviti na $(1+2x)$

Potpis

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Re: Dva pitanja, jedno bez ideje :( (SUMA) 02.12.2012. u 23:16 · pre 169 meseci #40

Citat:

nePonovljivA:
Zahvaljujem na detaljnom rešenju.
Da li možda znate u kojoj zbirci može da se nađe ovaj zadatak i još neki njemu slični ?

Mozes besplatno skinuti sledece dve knjige (dobro, to nisu knjige, vec linkovi ka tim knjigama (nisam hteo da postavljam direktne linkove do pdf-a)):
http://www.math.upenn.edu/~wilf/AeqB.html
http://www.math.upenn.edu/~wilf/DownldGF.html

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Forum kao aplikacija na telefonu

Srodne teme