Broj smislenih proizvoda matrica

PostPoslato: Ponedeljak, 21. Oktobar 2019, 21:31
od DraganKese
Pozdrav,
Potrebno je odrediti broj svih smislenih proizvoda [inlmath]n[/inlmath] matrica za sledece matrice:
[dispmath]A^{1\times3},B^{3\times3},C^{3\times1}[/dispmath] Pokusao sam da odredim ovo induktivnim metodom i uvideo sam da se proizvodi krecu kao Fibonacijev niz, ali ne umem to da dokazem.

Re: Broj smislenih proizvoda matrica

PostPoslato: Sreda, 23. Oktobar 2019, 08:22
od primus
Šta znači termin "smisleni proizvod matrica"? Kao što znamo, da bismo mogli da množimo dve matrice broj kolona prve matrice mora biti jednak broju vrsta druge matrice.

Re: Broj smislenih proizvoda matrica

PostPoslato: Petak, 25. Oktobar 2019, 20:54
od DraganKese
Upravo to i jeste smisleni proizvod matrica, to jest, potrebno je naci ukupan broj mogucih proizvoda matrica.
PS. Ispisivanjem svih kombinacija proizvoda, ukljucujuci i one gde se dve matrice mnoze same sa sobom, dobijam da postoji [inlmath]5[/inlmath] mogucih kombinacija, za tri matrice [inlmath]8[/inlmath] kombinacija, za cetiri [inlmath]13[/inlmath] kombinacija i tu primecujem da broj mogucih proizvoda sa porastom broja matrica predstavlja Fibonacijev niz, samo ne znam kako to i da dokazem.

Re: Broj smislenih proizvoda matrica

PostPoslato: Subota, 26. Oktobar 2019, 01:59
od Daniel
Moram reći da je ovo jedan od najinteresantnijih zadataka koje sam video u skorije vreme. Svideo mi se. :thumbup:

Možemo uočiti to, da u nekom „smislenom“ proizvodu, za sve matrice koje nisu na prvoj poziciji važi:
  • [inlmath]A[/inlmath] može doći jedino nakon [inlmath]C[/inlmath];
  • [inlmath]B[/inlmath] može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath];
  • [inlmath]C[/inlmath] takođe može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath].
Npr. za [inlmath]n=2[/inlmath], mogući smisleni proizvodi bi bili [inlmath]CA[/inlmath], [inlmath]AB[/inlmath], [inlmath]BB[/inlmath], [inlmath]AC[/inlmath] ili [inlmath]BC[/inlmath] (slučaj [inlmath]n=1[/inlmath] je trivijalan, za njega su mogućnosti, naravno – [inlmath]A[/inlmath], [inlmath]B[/inlmath] ili [inlmath]C[/inlmath]).

Označimo sa [inlmath]P_{A_k}[/inlmath] broj smislenih proizvoda za [inlmath]n=k[/inlmath] kod kojih je [inlmath]A[/inlmath] na poslednjem mestu.
Analogno, označimo sa [inlmath]P_{B_k}[/inlmath] broj smislenih proizvoda za [inlmath]n=k[/inlmath] kod kojih je [inlmath]B[/inlmath] na poslednjem mestu, a sa [inlmath]P_{C_k}[/inlmath] broj smislenih proizvoda za [inlmath]n=k[/inlmath] kod kojih je [inlmath]C[/inlmath] na poslednjem mestu.
I, neka je [inlmath]P_k=P_{A_k}+P_{B_k}+P_{C_k}[/inlmath] ukupan broj mogućih proizvoda za [inlmath]n=k[/inlmath] (npr. [inlmath]P_1=3[/inlmath], [inlmath]P_2=5[/inlmath], [inlmath]P_3=8[/inlmath] itd.)

Posmatrajmo sada slučaj dodavanja jedne matrice u proizvod, tj. povećanje [inlmath]n[/inlmath] sa [inlmath]k[/inlmath] na [inlmath]k+1[/inlmath]:
  • Pošto [inlmath]A[/inlmath] može doći jedino nakon [inlmath]C[/inlmath], sledi da je [inlmath]P_{A_{k+1}}=P_{C_k}[/inlmath];
  • Pošto [inlmath]B[/inlmath] može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath], sledi da je [inlmath]P_{B_{k+1}}=P_{A_k}+P_{B_k}[/inlmath];
  • Pošto [inlmath]C[/inlmath] može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath], sledi da je [inlmath]P_{C_{k+1}}=P_{A_k}+P_{B_k}[/inlmath].
Isto tako je i:
  • [inlmath]P_{A_{k+2}}=P_{C_{k+1}}[/inlmath];
  • [inlmath]P_{B_{k+2}}=P_{A_{k+1}}+P_{B_{k+1}}[/inlmath];
  • [inlmath]P_{C_{k+2}}=P_{A_{k+1}}+P_{B_{k+1}}[/inlmath].
Odatle sledi:
[dispmath]\begin{align}
P_{k+2}&=P_{A_{k+2}}+P_{B_{k+2}}+P_{C_{k+2}}\\
&=\underbrace{P_{C_{k+1}}+P_{A_{k+1}}+P_{B_{k+1}}}_{P_{k+1}}+P_{A_{k+1}}+P_{B_{k+1}}\\
&=P_{k+1}+\underbrace{P_{C_k}+P_{A_k}+P_{B_k}}_{P_k}\\
&=P_{k+1}+P_k
\end{align}[/dispmath] čime je pokazano da ovo jeste Fibonačijev niz.

Re: Broj smislenih proizvoda matrica

PostPoslato: Subota, 26. Oktobar 2019, 17:04
od DraganKese
Hvala puno na tako detaljnom odgovoru, drago mi je da vam se svideo zadatak.