Zadatak iz kombinatorike

Zadatak iz kombinatorike 28.02.2011. u 09:51 · pre 191 mesec #1

Zad:
Odrediti max broj

Re: Zadatak iz kombinatorike 28.02.2011. u 18:05 · pre 191 mesec #2

Prebroj koliko imaš kvadratnih matrica 1x1, 2x2, ... , mxm:

1x1 imaš $(m-0)\cdot (n-0)$ ;
2x2 imaš $(m-1)\cdot (n-1)$ ;
...
mxm imaš $(m-m+1)\cdot (n-m+1)$ .

Maksimalan broj kvadratnih matrica u matrici reda mxn (m<n) je $(m-0)\cdot (n-0)+(m-1)\cdot (n-1)+...+1\cdot (n-m+1)$ .

Re: Zadatak iz kombinatorike 28.02.2011. u 23:34 · pre 191 mesec #3

Hvala, Sini. I ja sam dosao do ove formule al sam slabo postavio pitanje..

Re: Zadatak iz kombinatorike 28.02.2011. u 23:45 · pre 191 mesec #4

Mozda je ovako nisam siguran.

$\sum _{k=0}^{m+1} ((m-k)(n-k))=-\frac{1}{6} (2+m)\left(m^2-2 m+3 n-3 m n-3\right)$

Potpis

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Re: Zadatak iz kombinatorike 01.03.2011. u 09:01 · pre 191 mesec #5

Hvala. Ima li ko ideju moze li preko faktorijela, lici mi da moze al sam se zapetljao

Re: Zadatak iz kombinatorike 01.03.2011. u 09:35 · pre 191 mesec #6

Pa ako je zadatak da napises program onda ti je ova formula sasvim dovoljna za iterativnu proceduru. Ako ga pakujes na faktorijel moze da se uradi i preko rekurzije, ali rekurzija je uvek sporija jer funkcija poziva sama sebe vise puta. Je l' mnogo bitno da bude u obliku faktorijela?

Potpis

If you can't explain it simply, you don't understand it well enough. A. Einstein

Re: Zadatak iz kombinatorike 01.03.2011. u 09:50 · pre 191 mesec #7

Zbog -1/6 se moze dobiti negativan broj a broj kv. matrica bi valjda trebao da je cio pozitivan broj, i valjda k ide od 0 do m-1).

Re: Zadatak iz kombinatorike 01.03.2011. u 16:31 · pre 191 mesec #8

Ja sam napisao sumu prema Sini82-evoj "formuli" i tamo ide do m+1.
Probao sam za kvadratne m=n i trebalo bi da suma ide do m.
Za m<n suma daje tacne rezultate.

A sumira se ovako

$\sum _{k=0}^{m+1} ((m-k) (n-k))=\sum _{k=0}^{m+1} k^2-m\sum _{k=0}^{m+1} k -n\sum _{k=0}^{m+1} k +m n\sum _{k=0}^{m+1} 1$

Potpis

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Re: Zadatak iz kombinatorike 01.03.2011. u 18:56 · pre 191 mesec #9

$\sum _{k=0}^{m-1} ((m-k) (n-k))=\sum _{k=0}^{m-1} k^2-m\sum _{k=0}^{m-1} k -n\sum _{k=0}^{m-1} k +m n\sum _{k=0}^{m-1} 1$

Re: Zadatak iz kombinatorike 01.03.2011. u 20:29 · pre 191 mesec #10

To je to sad sam skontao da je islo do m-1

Sad je ukupan broj $\frac{m}{6} \left(1+3 n+3 m n-m^2\right)$

Potpis

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Re: Zadatak iz kombinatorike 01.03.2011. u 23:33 · pre 191 mesec #11

Hvala momci. Srdjane, da li si ovaj rezultat dobio iz formule koju je sini iznad napisao $\sum _{k=0}^{m-1} ((m-k) (n-k))=\sum _{k=0}^{m-1} k^2-m\sum _{k=0}^{m-1} k -n\sum _{k=0}^{m-1} k +m n\sum _{k=0}^{m-1} 1$ ? Da li koristis da je $\sum _{k=0}^{m-1} k^2=m(m-1)(2m-1)/6$ i da je $\sum _{k=0}^{m-1} k=m(m-1)/2$ ?

Re: Zadatak iz kombinatorike 02.03.2011. u 01:01 · pre 191 mesec #12

Da ono je formula za Sinijevu sumu do m-1.
Ja sam to izracunao u Mathematici nisam rucno.

A mozes (moras) da koristis te sume za sumu kvadrata i sumu prirodnih brojeva.
Kad primenis te formule, jel dobijes ovako nesto

$\sum _{k=0}^{m-1} k^2-m\sum _{k=0}^{m-1} k -n\sum _{k=0}^{m-1} k +m n\sum _{k=0}^{m-1} 1=\frac{1}{6} m (m-1) (2 m-1)-m \frac{1}{2} (m-1) m-n \frac{1}{2} (m-1) m+m n m$

Kad sve izmnozis i izvuces m (ili prvo izvuces m) dobices kao ja.

$\frac{m}{6}-\frac{m^3}{6}+\frac{m n}{2}+\frac{m^2 n}{2}=\frac{m}{6}\left(1-m^2+3n+3m n\right)$

Mozda te je bunilo ovo $\sum _{k=0}^{m-1} 1=m$

Potpis

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Re: Zadatak iz kombinatorike 02.03.2011. u 01:13 · pre 191 mesec #13

Da, upravo to. Ja sam uzimao da je $\sum _{k=0}^{m-1} 1=1$ .

Re: Zadatak iz kombinatorike 02.03.2011. u 01:28 · pre 191 mesec #14

Konkretno za m=10.
Koliko je $\sum _{k=0}^{9} 1$ ?

1+1+1+1+1+1+1+1+1+1 = 10.
Odnosno m u opštem slučaju.

Zadatak ti je urađen ispravno ako je glasio: "Odrediti max broj kvadratnih matrica u matrici reda mxn (m-kolone, n-redovi i n>m)."
Bez onog čudnog dela dela: "gdje se kvadratnom matricom smatra i jedinični član uz krajnju ivicu".
Računati su i svi elementi (1X1) koji i nisu uz krajnu ivicu, što je i normalno i tako je Sini82 i uradio.

Re: Zadatak iz kombinatorike 02.03.2011. u 01:37 · pre 191 mesec #15

Hvala, Srdjane. Miko takodje. Sad sam se malo zamislio i vidio da je $\sum _{k=m}^{n} 1=n-m+1$ .

Re: Zadatak iz kombinatorike 02.03.2011. u 02:08 · pre 191 mesec #16

Kada bi se od ovih tvojih kvadratnih podmatrica tipa 1X1, 2X2, 3X3... izračunale determinante one se zovu Minori.
Ali ovu su samo minori nastali ukrštanjem susednih vrsta i susednih kolona.

Definicija:
Minor reda k matrice AmXn je vrednost determinante kvadratne podmatrice tipa kXk, nastale iz matrice A ukrštanjem bilo kojih njenih k vrsta i k kolona.
k=1,2,3...min(m,n).

Dakle minori tipa 2 nisu samo od kvadratnih podmatrica nastalih ukrštanjem 2 susedne vrse i 2 susedne kolone, već bilo koje 2 vrste i 2 kolone.
Recimo može (1 i 3) vrsta ukrštene sa (2 i 5) kolonom i broj minora je daleko veći od ovog što su tebi izračunali.
Ti si dobio broj minora u "komadu".

Jedino se ne menja kod minora tipa 1X1.

Zadatak se generalizuju na: "Koliko ima minora tipa 2, tipa 3.... do tipa min(m,n)".
Možemo uzeti da je min(m,n) = m.

Znao bih da napišem program da ih sve izgeneriše, ali mi prebrojavanje zapinje.

Re: Zadatak iz kombinatorike 02.03.2011. u 03:42 · pre 191 mesec #17

@Miki069
Jesi na ovo mislio?

Citat:

Let A be an m × n matrix and k an integer with 0 < k ≤ m, and k ≤ n. A k × k minor of A is the determinant
of a k × k matrix obtained from A by deleting m − k rows and n − k columns.

Since there are:

${m \choose k}$
ways to choose k rows from m rows, and there are

${n \choose k}$

ways to choose k columns from n columns, there are a total of

${m \choose k} \cdot {n \choose k}$

minors of size k × k.

Izvor
http://en.wikipedia.org/wiki/Minor_%28linear_algebra%29

Potpis

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Re: Zadatak iz kombinatorike 02.03.2011. u 09:37 · pre 191 mesec #18

To je to.

Toliko je jasno iz dela definicije "...ukrštanjem bilo kojih njenih k vrsta i k kolona.." da mi sad nije jasno šta sam ja muljao i komplikovao.
U programu i koristim generator kombinacija, a u prebrojavanju nisam ukapirao da su kombinacije.

Hvala Srdjane.

Forum kao aplikacija na telefonu

Srodne teme