szukanie zaawansowane
 [ Posty: 15 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 14:34 
Użytkownik

Posty: 9
Lokalizacja: Wrocław
Witam,

Wiem że taki temat się powtórzył(został przeniesiony do kosza przez to że użytkownik nie zastosował LaTeX-a więc postanowiłem wziąć sprawy we własne ręce.) Zadania z którymi mam problem to:
11,12.

Będę się starał na bieżąco uzupełniać moje rozwiązania z poniższej listy, byłbym wdzięczny za sprawdzenie poprawności rozumowania i obliczeń oraz pomoc z rozwiązaniem zadań wypisanych wyżej.


1. Rozłożyć na rozłączne cykle oraz zbadać parzystość następujacej permutacji:

\left( \begin{tabular}{cccccccccccc}
1 & 2 & 3&4 & 5 & 6&7 & 8 & 9&10&11&12 \\
8 &4& 1& 3& 7& 11& 6& 2& 12& 5& 9& 10  \\
\end{tabular}\right)

2. Palindrom to słowo, które czytane od początku i od końca daje to samo (np. kajak). Ile jest
palindromów w alfabecie 26-literowym długości:
a) 10;
b) 11.

3. Wypisać wszystkie liczby Catalana mniejsze od 20.

4. Znajdź jawną postać ciągu an zadanego rekurencyjnie:

a _{n+2}  = 5a _{n+1}  - 6a _{n}
a _{0} = 2, a _{1}  = 5

5. Znajdź wyraz ogólny ciągu, którego funkcją tworzącą jest funkcja
f(x) =  \frac{x}{1-x ^{2} }

6. Na ile sposobów można podzielić 40 jednakowych cukierków pomiędzy 5 dziewcząt i 4 chłopców,
jeżeli:
a) każde z nich ma dostać co najmniej jednego cukierka;
b) dziewczęta mają dostać dokładnie po jednym cukierku?

7. Znaleźć liczbę dzielników liczby a) 6000; b) 6!

8. Wiadomo, że na uniwersytecie 60% profesorów gra w tenisa, 50% gra w brydża, 70% biega,
20% gra w tenisa i brydża, 30% gra w tenisa i biega, a 40% gra w brydża i biega. Jeśli ktoś
powie, że 20% profesorów biega, gra w tenisa i brydża, to powie prawdę?

9. Wykazać indukcyjnie, że F1 + F3 + F5 + ... + F _{2n−1}  = F _{2n}.

10. Ile jest wszystkich liczb pięciocyfrowych, w których:
a) kolejne cyfry rosną;
b) kolejne cyfry tworzą ciąg nierosnący?

11. Uzasadnić tożsamość:
{n \choose 1} +2 {n \choose 2} +3 {n \choose 3} +.....+n {n \choose n} =n2 ^{n-1}

12. Zbiór m elementowy można podzielić na cztery niepuste części na s(m, 4) sposobów, gdzie
liczby s(m, 4) spełniają zależność rekurencyjną s(m.4) = s(m − 1, 3) + 4s(m − 1, 4).
a) Oblicz s(5, 4) na podstawie tej zależności.
b) Sprawdzić wynik wypisując wszystkie podziały, o jakich mowa.

13. Poniższe liczby ustawić w kolejności od największej do najmniejszej:
{77 \choose 37} , {77 \choose 47} ,{77 \choose 57} ,{77 \choose 67} ,{99 \choose 37} ,{99 \choose 47}

14. Podać wartość współczynnika przy wyrazie a ^{11} b ^{6} c ^{2}d.
rozwinięciu \left( a+b+c+d\right) ^{20}. Znaleźć sumę wszystkich współczynników w rozwinięciu \left( a+b+c+d\right) ^{20}
.
15. Drzewo ma wyłącznie wierzchołki stopnia 1 oraz 3. Wierzchołków stopnia 3 ma 10. Ile ma
wierzchołków stopnia 1?

16. Podaj liczbę chromatyczną oraz indeks chromatyczny grafu K _{5}.

17. Znajdź drzewo o podanych kodzie Pruefera: 3423423

18. Spójny graf płaski (czyli planarny narysowany na płaszczyźnie bez przecięć) ma 24 wierzchołki,
wszystkie stopnia 3. Na ile obszarów dzieli on płaszczyznę?

19. Narysuj 3 grafy proste (nieizomorficzne) o 5 wierzchołkach i 6 krawędziach.

20. Trójkąt równoboczny dzielimy na 6 jednakowych trójkatów, prowadząc w nim trzy środkowe.
Na ile sposobów można pokolorować tych 6 trójkącików za pomocą dwóch kolorów, jeżeli dwa
pokolorowania uznajemy za równoważne, gdy jedno z nich można uzyskać z drugiego przez
obrót lub symetrię?

21. Ile drzew spinających ma graf (etykietowany)
Obrazek

____________________________________________________________________________________

1.
Cykle rozłączne:
\left( \begin{tabular}{ccccc}
1&8&2&4&3
\end{tabular}\right)
\left( \begin{tabular}{ccccccc}
5&7&6&11&9&12&10
\end{tabular}\right).
Parzystość:
Liczby inwersji:
8,4,1,3,7,11,6,2,12,5,9,10

Suma wszystkich możliwych inwersji - 24 - liczba parzysta więc permutacja jest także parzysta.

2.
a) 26 ^{ \frac{10}{2} }
b) 26 ^{ \frac{12}{2} } ===> Znalazłem taki wzór x ^{ \frac{n+1}{2} } -Dla nieparzystych n.

3.
Czy jest jakiś wzór na wyznaczenie wszystkich liczb Catalana mniejszych od danej wartości?
c_{n}= \frac{1}{n+1}  \cdot  {2n \choose n}.
C _{0} =1
C_{1} =1
C_{2}=2
C_{3}=5
c_{4}=14

4.
a _{n+2}  = 5a _{n+1}  − 6a _{n}
Zamieniam na postać
x ^{2} =5x-6
x ^{2}-5x+6=0 - Obliczam delte - 1
Czas na pierwiastki x _{1}=3 ,x _{2}=2
Podstawiam - a _{n}  = A \cdot 3 ^{n}+B \cdot 2 ^{n}
Przechodzę na układ równań:
\begin{cases} 2=3^{0}A+2^{0}B \\ 5=3^{1}A+2^{1}B \end{cases}

\begin{cases} 2=A+B \\ 5=3A+2B \end{cases}
Po obliczeniach:
A= 1 ,B=1
Podstawiam:
a _{n}  = 3 ^{n}+2 ^{n}

5.
f(x)= \frac{A}{1-x} + \frac{B}{1+x} = \frac{A+Ax+B-Bx}{1-x ^{2} }

\begin{cases} A+b=0 \\ A-B=1 \end{cases}

2A=1

\begin{cases} A= \frac{1}{2}  \\ B=- \frac{1}{2} \end{cases}

Podstawiam:
= \frac{ \frac{1}{2} }{1-x} + \frac{ \frac{-1}{2} }{1+x} = \sum_{n=0}^{ \infty }  \frac{x ^{n} }{2} - \sum_{n=0}^{ \infty }  \frac{(-1) ^{n} \cdot x _{n} }{2}= \sum_{n=0}^{ \infty }  \frac{x ^{n}-x ^{n} \cdot (-1) ^{n}   }{2}= \sum_{n=0}^{ \infty } x ^{n} \frac{(1 ^{n}-(-1) ^{n})  }{2}

Więc wyraz ogólny:
a _{n} = \frac{1 ^{n}-(-1) ^{n}  }{2}
6.
a)
Przed losowaniem cukierków dałem każdemu dziecku po 1 więc
40-9=31. Z dwumianu Newtona - {n+k-1 \choose n-1}
Więc odpowiedź to: {39 \choose 8}

b)
Dziewczęta dostają po 1 i nie biorą udziału w dalszym rozdawaniu. 40-5=35.
{38 \choose 3}
7.
a) 40
b) 30

8.
Ze wzoru włączeń i wyłączeń.
1=0,6+0,5+0,7-0,2-0,3-0,4+0,2
1 \neq 1,1

Z tego wynika iż ta osoba musi kłamać.

9.
F _{1}+F _{3}+F _{5} +......+F _{2n-1}=F _{2n}

1 ^{o} dlan=1
L: F _{1} =1 = P: F _{2} =1 L=P
2 ^{o} dla n
F _{1}+F _{3}+F _{5} +......+F _{2n-1}=F _{2n}
3^{o} dla n+1
F _{1}+F _{3}+F _{5} +......+F _{2n-1}+F _{2n+1} =F _{2n+2}
F _{1}+F _{3}+F _{5} +......+F _{2n-1} = F_{2n} - Własność Ciągu Fibonacciego
Więc:
L: F _{2n} +F _{2n+1} =F _{2n+2} = P - Co kończy dowód.
10.
a)
{9 \choose 5}
b)
Wszystkich możliwych wyborów 5-cyfrowej liczby jest 9 \cdot 10 ^{4}
Więc wszystkich liczb które tworzą ciąg nierosnący jest 9 \cdot 10 ^{4} - {9 \choose 5}
11.
~~~~~~~~~
12.
~~~~~~~~
13.
Trójkąt Pascala
{99 \choose 47} > {99 \choose 37} > {77 \choose 37} > {77 \choose 47} > {77 \choose 57} > {77 \choose 67}
14.
Wartość współczynnika - \frac{20!}{11! \cdot 6! \cdot 2! \cdot 1!}
Suma wszystkich współczynników - 4 ^{20}
15.
Narysowałem sobie takie drzewo i odczytałem że wierzchołków stopnia 1 ma 12.

16.
K _{5}
Liczba chromatyczna - 5
Indeks chromatyczny - 5 - ?

17.
Dość proste.

18.
Jeżeli wiemy że graf jest planarny to obowiązuje wzór W-K+S=2
Wiemy że W=24 i te wierzchołki są stopnia 3. Możemy obliczyć 2K=3 \cdot 24 w tym wypadku. Więc:
24-36+S=2
S=14

19.
Obrazek
20.
G={0,120,240,S _{1},S_{2},S_{3}}
Fix(0)=2 ^{6}
Fix(120)=Fix(240)=2^{2}

Fix(S_{1})=Fix(S_{2})=(S_{3})=2^{3}

G= \frac{2 ^{6}+2 \cdot 2 ^{2}+3 \cdot 2 ^{3}   }{6} =16
21.
4 \cdot 3=12
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:16 
Użytkownik

Posty: 15
Lokalizacja: localhost
Tak na szybko ;)

Zadanie 4:
masz podane wyrazy a_0 i a_1, wziąłeś złe potęgi (n=1,2, zamiast n=0,1) w układzie równań.

zadanie 9:
To są liczby Fibonacciego: F_{n+2} = F_{n+1} + F_{n}
Dalej bardzo prosta indukcja.

zadanie 11:
Dowód kombinatoryczny:
Lewa strona: Z n osób wybieramy delegację k osobową, a następnie przywódcę na k sposobów.
Prawa strona: Wybieramy jedną osobę jako lidera a następnie dobieramy do niego towarzyszy (ciągi 00011100.... idzie/nie idzie).

Warto też rzucić okiem na własności symbolu Newtona.

zadanie 12:
Podpowiedź, jak się przyjrzysz to zauważysz, że w ogólności ta rekurencja wyraża się wzorem:
s(m,k)=s(m-1, k-1) \cdot k \cdot s(m-1, k)

zadanie 14:
Potwierdzam 4^{20}, ponieważ gdy a=b=c=d=1 to ta suma będzie uzależniona tylko od współczynników.

zadanie 18:
Ilość krawędzi oblicz ze wzoru:
\sum deg(v) = 2K

zadanie 20:
http://www.matematyka.pl/390522.htm
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:27 
Użytkownik

Posty: 120
Jak dokładnie 13 zrobiłeś?

W 21) 4 \cdot 3=12, a nie 15 :D

W 3) wzór Catalana to:

c_{n}= \frac{1}{n+1}  \cdot   {2n \choose n}
i po prostu podstawiasz do niego 0,1,2,3... i któraś tam wyjdzie ci powyżej 20 (podpowiem, że będzie to c_{5}), ogólnie to będzie 1,1,2,5,14
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:30 
Użytkownik

Posty: 15
Lokalizacja: localhost
W zadaniu 13 korzystasz z następujących własności trójkąta Pascala:
Gdy n jest takie same to im k bliżej środka to tym liczba jest większa
Gdy n są różne, zaś k takie same to to większa liczba jest ta, która ma większą wartość n
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:40 
Użytkownik

Posty: 9
Lokalizacja: Wrocław
Quenshin napisał(a):

Zadanie 4:
masz podane wyrazy a_0 i a_1, wziąłeś złe potęgi (n=1,2, zamiast n=0,1) w układzie równań.

Mógłbyś rozpisać swoją myśl co do zadania 4? Nie mogę dostrzec gdzie te złe potęgi wziąłem.


0Mniac napisał(a):
W 21) 4*3=12, a nie 15 :D

W 3) wzór Catalana to:

c_{n}= \frac{1}{n+1} *  {2n \choose n}
i po prostu podstawiasz do niego 0,1,2,3... i któraś tam wyjdzie ci powyżej 20 (podpowiem, że będzie to c_{5}), ogólnie to będzie 1,1,2,5,14


No tak w 21 śmieszny błąd :D
Co do 3 to myślałem że jest jakiś szybszy sposób, dzięki wielkie!

13. Na ostatnim(dodatkowym wykładzie opowiadała, pozwolę sobie to troszkę skrócić)
wpierw należy podzielić 77 na dwie w miarę równe połowy aby zorientować się gdzie jest środek (największa wartość) w tym wierszu w trójkącie pascala. Wychodzą nam liczby 38,39. {77 \choose k} Wszystko co k ma mniejsze lub większe od 38,39 jest mniejsze od wartości w {77 \choose 38}. Więc po prostym segregowaniu wychodzi ze {77 \choose 37} > {77 \choose 47} > {77 \choose 57} > {77 \choose 67}.
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:41 
Użytkownik

Posty: 120
Wysłałem Ci fotki z rozwiązaniami większości przykładów. Teraz tylko do rozwiązania zostało mi 12), którego tematu w ogóle nie ogarniam :D
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:48 
Użytkownik

Posty: 15
Lokalizacja: localhost
roskuwaczus napisał(a):
Quenshin napisał(a):
Zadanie 4:
masz podane wyrazy a_0 i a_1, wziąłeś złe potęgi (n=1,2, zamiast n=0,1) w układzie równań.

Mógłbyś rozpisać swoją myśl co do zadania 4? Nie mogę dostrzec gdzie te złe potęgi wziąłem.


Otrzymałeś wzór:
a _{n}  = A \cdot 3 ^{n}+B \cdot 2 ^{n}

Masz podane wyrazy a_0, a_1, więc:
\begin{cases} 2=3^{0}A+2^{0}B \\ 5=3^{1}A+2^{1}B \end{cases}
Otrzymujesz następujący układ do rozwiązania.
\begin{cases} 2=A+B \\ 5=3A+2B \end{cases}
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 16:50 
Użytkownik

Posty: 9
Lokalizacja: Wrocław
Dzięki wielkie!
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 17:29 
Użytkownik

Posty: 120
Jeszcze co do 1 zadania. Trochę jestem zielony w tych inwersjach i nie wiem jak do końca je wyznaczyć. Staram się to zrobić w tym wątku 390603.htm może pomożecie?:D
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 21:10 
Użytkownik

Posty: 2
Lokalizacja: Wrocław
Czy zadanie 6 jest na pewno dobrze zrobione ?

Według mojego rozumowania to:

a) Jeśli każde dziecko ma mieć po 1 cukierku, to od 40 cukierków odejmujemy 9 rozdanych. Zostaje nam 31 cukierków.

Teraz ilość sposobów rozdania 31 nierozróżnialnych przedmiotów 9 rozróżnialnym osobom - {39 \choose 8} Bo mamy ciąg 01 o długości 39 i 1 jest 8.

b) Jeśli dziewczyny mają mieć dokładnie po 1 cukierku, to od 40 cukierków odejmujemy 5. Zostaje 35 cukierków do rozdania 4 chłopakom. Znowu ciąg 01 o długości 38 i ilość 1 - 3. Czyli {38 \choose 3}


Czy mam rację ?
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 21:25 
Użytkownik

Posty: 9
Lokalizacja: Wrocław
Jest to bardzo prawdopodobne, korzystasz z dwumianu newtona o wzorze {n+k-1 \choose n-1} gdzie k jest w tym przypadku ilością cukierków do rozdania a n- liczbą dzieci którym się należą cukierki.
Z tego toku rozumowania wychodzi:
a) {39 \choose 8}
b) {38 \choose 3}
Może ktoś jeszcze to potwierdzić :D?
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 22:06 
Użytkownik

Posty: 120
10) b) na pewno tak? na tych rozwiązaniach znajomego było, że {10+5-1 \choose 5-1}
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 22:14 
Użytkownik

Posty: 15
Lokalizacja: localhost
0Mniac napisał(a):
10) b) na pewno tak? na tych rozwiązaniach znajomego było, że {10+5-1 \choose 5-1}


Od wszystkich możliwych liczb 5-cyfrowych odejmujemy te, w których cyfry rosną.
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 22:21 
Użytkownik

Posty: 2
Lokalizacja: Wrocław
Nie rozumiem tylko zadania 21, może ktoś jaśniej wytłumaczyć ?
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 23:00 
Użytkownik

Posty: 9
Lokalizacja: Wrocław
w 21 ten graf podzieliłem na 2 grafy rozłączne i dla każdego z osobna (kwadratu,trójkąta) szukałem drzew spinających. Dla kwadratu wyszło {4 \choose 1} a dla trójkąta {3 \choose 1}. Następnie {4 \choose 1} \cdot {3 \choose 1}=12.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 15 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 matematyka dyskretna  pyrak  2
 [Matematyka dyskretna] Układy kongruencji  Anonymous  3
 3 zadania...  Ciapanek  2
 egzamin matematyka dyskretna  dibo  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl