Aby edytować ten dokument, zmień w adresie URL słowo `preview' na edit ;)

Grupa O (rozwiązujta :D)

1. Połączmy graf C7 o wierchołkach 1,2,...,7 z grafem K6 o wierzchłkach 8,9,..13 dodając krawędź 1-8. Ile drzew spinających ma taki graf?

c7->7 drzew

k6 -> n^(n-2) -> 6^4 drzew kazda stad ma 7 koncowek z grafu c7, wiec iloraz jest wynikiem

drzew

2. Podaj liczbę chromatyczną i indeks chromatyczny szkieletu ośmiościanu?

l.chrom = 3

i.chrom = 5 (graf pełny, parzysty)

3. Znajdź liczbę wszystkich grafów zwykłych (symetrycznych, bez krawędzi wielokrotnych i bez pętli) o 10 wierzchołkach.

2^(10 po 2) //gdzies juz byl wzor na to, ale nie pamietam gdzie // tn ? 2e^( n po 2 ) ?

4. Znajdź f. tworzącą dla ciągu an = 7^n dla n >= 2, an = 0 w pozostałych przypadkach.

f(x)=49x^2/(1 - 7x)

5. Na ile sposobów można rozdać 52 kart pomiędzy 4 graczy, przy założeniu, że każdy z nich otrzymuje jednego asa?

(4 po 1)*(48 po 12)*(36 po 12)*(24 po 12) //najpierw rozdajemy po asie, potem po rowno kazdemu karty (choc to nie bylo napisane, ze ma byc po rowno, wiec nie wiem czy takie rozwiazanie jest dobre) <-źle chyba powinno byc (4po1)*(48+3 po 3) ale nie jestem pewien tego 4po1 //ok, podswietlone jest lepsze niz moje :) // raczej nie... // wydaje mi się, że wynik będzie po prostu (48+3 po 3) - każdy gracz ma po prostu dostać jednego asa, więc nieważne jaki kolor, można je odjąć; potem nie jest określone po ile kart ma dostać każdy z graczy, więc stosujemy wzór (n+k-1 po k-1) // no tak, to zalezy czy Asy traktujemy jako rozróżnialne, czy nie//

// oczywiście, że rozróżnialne, jak gracie w karty to nie bierzecie pod uwagę koloru asa? :F tak, że podświetlony wzór będzie git//

6. Znajdź liczbę rozwiązań równania x1+ x2...+x7 = 40 w l.c nieujemnych przy czym x7 >= 3, a pozostałe dowolne

x7=y7+3, reszta bez zmian (0 to najmniejsza nieujemna liczba), czyli

y1+y2+...+y7=37

oo|oooo|ooooooooo|ooooo|ooooooo|oooooo|oooo

37+6 po 6

7. Na ile sposobów można podzielić 15-kąt wypukły na 13 trójkątów (liczba Catalana 13)

wzór na l.catalana: http://upload.wikimedia.org/wikipedia/pl/math/7/e/5/7e5d4600bac66254a4c6fc015f79d253.png

k13= 26!/(14!*13!)=208012 //moze ktos potwierdzic czy to takie rozwiazanie mialo byc?

8. W drzewie 7-wierzchołkowym wierzchołek 1 sąsiaduje z 2, 3, 4, 5, a wierzchołek 5 z wierzchołkami 6, 7. Znajdź kod Pruefera tego drzewa.

11155

9. Na ile istotnie różnych sposobów można pokolorować kwadrat podzielony przez przekątne i symetralne boków na 8 jednakowych trójkątów za pomocą 3 kolorów? Pokolorowania uznajemy za jednakowe, gdy jedno z nich da się uzyskać z drugiego przez obrót.

Fix0=3^8

// zleeeee!!!!///

Fix90=3^6=Fix180 // mi wyszło 3^2 i Fix90* = Fix270*

Fix270=3^7 //Fix180=3^4

chyba zapomniano o symetriach :P ma być 8 trójkątów w tym kwadracie, a teraz sprawdzamy możliwości pokolorowania tych trójkątów 3-ma kolorami: sprawdzamy tylko dla obrotów, bo w poleceniu nie ma, że mamy to zrobić dla symetrii... zachwilę napiszę dlaczego tak jest // no to rozumiem, ale skoro jset 8 trójkątów, to czemu obracamy o 90 stopni? // bo figura, którą mamy otrzymać musi być izomorficzna do poprzedniej … teraz rozumiem! Thx a lot! Jesteś geniuszem!
BTW jak w poleceniu jest, że możemy otrzymać drugą figurę przez obrót (tylko obrót) to nie sprawdzamy symterii, jeśli jest dla obrótu i symetrii lub tylko symetrii, to sprawdzamy możliwości dla obortów i symetrii, ponieważ same obroty tworzą grupę obrotów, podobnie obroty i symetrie razem. Same symetrie nie tworzą grupy obortów.

(2*3^6+3^7+3^8)/4 // więc (3^8+2*3^2+3^4)/4 //

10. Znajdź funkcję tworzącą dla ciągu zadanego rekurwencją an+1 = 3an + 2, a0 = 1.

S(x)=1/(1-x) //sposo na liczenie takich rzeczy jest ponizej bardzo ladnie opisany

/*To zadanie zrobiłbym tak:

..

a0=1, a1=5, a2=17, a3=53. Niech f(x)= a0+a1*x+a2*x^2+...+an*x^n+... będzie funkcja tworzącą tego ciągu.

a(n+1)-3an=2

3x*f(x)=3*a0*x+3*a1*x^2+3*a2*x^3+...+3*a(n-1)*x^n

f(x)-3*xf(x)=a0+x*(a1-3*a0)+x^2(a2-3*a1)+x^n(an-3*a(n-1))=>1+2x+2x^2+2x^3+...=1+2x/(1-2x)=1/(1-2x)

stąd f(x)=1/(1-2x)(1-3x)

*/ Nie polecam z tej strony tego robić, wynik chyba nie jest poprawny; lepiej zrobić analogicznie, tak jak poniżej. Mi wyraz ogólny ciągu wyszedł 3^n - 1.

11. Sformułuj odpowiednią nierówność pomiędzy liczbą krawędzi a liczbą wierzchołków grafu planarnego bez trójkątów i wywnioskuj stąd, że graf kostki 5-wymiarowej nie jest planarny.

UZUPEŁNIONE O NASZĄ GRUPĘ J i M

grupa M:

1. Na ile sposobów można zbiór 6-el. podzielić na 4 niepuste części?

Liczby Stirlinga II rodzaju - wtedy wynik 65

S(6,4)= 4*S(5,4)+S(5,3) = 4*(5 po 2)+3*(4 po 2)+2³-1 =40+18+7=65
//skąd ta “-1”? // S(n,2)=2^n-1-1
S(5,3) = 3*S(4,3)+S(4,2) = 3*(4 po 2)+2³-1=18+7 << czemu tu jest 5 i 3 jak dzielimy 6 el zbior na 4 niepuste czesci, na chuj ktos mota -.- // Bo to jest rozwinięcie wzoru na S(5,3) potrzebnego do rozwiązania zadania, na chuj się czepiasz?

// materiały do nauki liczb II rodzaju Stirlinga - na dole, gdzie jest klamra { }, również są liczby Bella

2. Znajdź wzór ogólny o funkcji tworzącej f(x)= x^2 / 2-x. Nie zapomnij o początkowych wyrazach. // Jak to cholerstwo zrobic?

jeśli dobrze pamiętam, a_0 = 0, a_1 = 0, a_n = (½)^n, nie jestem pewien

poprawcie mi humor i powiedzcie, że dobrze


\

//nie spiesz sie :D

3. Graf płaski dzieli płaszczyznę na 25 obszarów, ma 35 wierzchołków. Ile ma krawędzi?

W - K + S = 2

35 - K + 25 = 2

K = 58

4. Droga w kracie 5x9 (najkrótsza)

5+9 po 5, lub 5+9 po 9, musimy wykonać 5+9 kroków, z czego 5 musi być równoległe do krótszego boku, a 9 do dłuższego

5. Podaj liczbę chromatyczną (wierzchołki) i indeks chromatyczny (krawędzie) grafu powstałego z C10 przez dodanie krawędzi 1-3.

indeks = 3, bo w wierzchołkach 1 i 3 zbiegają się 3 krawędzie

liczba = 3, bo C_10 wymaga dwóch kolorów, a połączenie 1-3 wymusza na nas dodanie jeszcze jednego koloru

C_10 => a-b-a-b-a-b-a-b-a-b

+----------------------+

+---+

C_10 z połączeniem => a-b-c-b-a-b-a-b-a-b

+----------------------+

6. Na ile sposobów można podzielić 30 jednakowych cukierków na 2 dziewczyny i 3 chłopców? Dziewczyny muszą dostać (dokładnie) po 2 cukierki, chłopcy mogą nie dostać żadnego.

Dziewczynki dostają dokładnie po dwa cukierki, więc są one dla rozważań nieistotne.

Można na 3 sposoby pokrzywdzić dwóch chłopców, na 3*25 jednego chłopca, 25 po 2 podziałów gdzie każdy dostaje cukierka

??? ktoś może potwierdzić ???

Jak dla mnie to 30-4 = 26 cukierkow do rozdania na chlopcow (bo dziewczyny maja 4).
Robimy to jak z monetami:

ch1 ch2 ch3

ooooo|ooooooooooooooo|oooooo
2 kreski, 26 kropek czyli
26+2 po 2 (rownowazne 26+2po2).

Potwierdzam. 28 po 2

7. W drzewie 7 wierzchołkowym, wierzchołek 7 sąsiaduje z 2, 3, 4, 5, 6, a wierzchołek 2 z 1 Znajdź kod Pruefera.

2 7 7 7 7

8. Dwa grafy K5 o wierzchołkach 1, 2,...,5 i K8 6, 7,...,13 połączono krawędzią łączącą 1 oraz 13. Ile drzew spinających ma taki graf?

drzew rozpinających, gdzie k to liczba dorysowanych krawędzi.

Graf Kn ma n^(n-2) drzew spinajacych.

K5 + K8 = 5^3 * 8^6. * http://www.matematyka.pl/201199.htm

9. malowanie 8-kąta foremny na 4 kolory. // W poleceniu było napisane tylko przez obrót!

G={0st., 45 st., 90st., 135st., 180st., 225st., 270st., 315st.}

|G| = 8

Fix 0st = 4^8

Fix 45st = Fix 315st = 4^1 // skąd tam 4^8 a tu 4^1 itd?//tak na chłopski rozum, to przy obrocie o zero stopni musisz malować każdy trójkąt w środku na nowy kolor, więc masz 8 możliwości.

Przy obrocie o 45 stopni, jeśli pomalujesz jeden trójkącik na kolor A, to kolejny też ma kolor A (bo ten pierwszy przechodzi od razu na drugi), kolejny równiez ma kolor A itp.

Fix 90st = Fix 270st = 4^2 //Tutaj malujesz sobie trójkącik na kolor A, po czym przechodzi on 2 trójkąty dalej (obrót 90 stopni), następnie znów 2 trójkąty dalej aż wróci do tego pierwszego A. Wtedy nie masz zamalowanych wszystkich, więc malujesz kolejny niezamalowany na B i powtarzasz czynność. Wychodzi, że możesz pomalować całośc na dwa kolory. Generalnie warto sobie narysować i go obracać w pamięci i zobaczyć co przechodzi na co :) więc 4 to liczba kolorów możliwych ogólnie, a potęga to liczba kolorów na jakie malujemy przy aktualnym obrocie. // dzięki wielkie ;)

Fix 135st = Fix 225st = 4^1

Fix 180st = 4^4

10. Znajdź f tworzącą i przedstaw w postaci f-kcji wymiernej

a_n+1 = 4a_n+2,

a₀ = 1.
Sprawdzać a nie kibicować, to relacja live z moich poczynań :D Można wyjaśnić krok 3?;p (dlaczego n-1?) // bo masz a_n, a wzór jest na a_n+1=4*a_n+2, to a_n=4a_(n-1)+2//oke :)

ktoś może to przejście rozjaśnić, bo mi mózg paruje...?

jak to A i B zostało wyliczone? // właśnie tak

Potwierdzenie, nie sypłem się :D https://www.wolframalpha.com/input/?i=a%28n%2B1%29%3D4a%28n%29%2B2%2C+a%280%29%3D1#

11. Znajdz liczbe drzew spinających grafu K10 mających wierzchołek st.8

na 10 po 1 wybieramy wierzchołek, który będzie miał stopień 8

na 9 po 8 wybieramy 8 wierzchołków, które podpinamy do wybranego poprzednio

na 8 po 1 wybieramy do którego z wybranych poprzednio podpinamy brakujący wierzchołek

??? ktoś potwierdzi ???

IMO jak juz w 2 punkcie wybrales 8 wierzcholkow z 9, to zostaje jeden jedyny nie wybrany, ktory podczepiamy nie do W(st.8), wiec jak dla mnie to ostatnie 8po1 juz odpada.

10po1 * 9po8

grupa J //5-10 oraz część rozwiązań dodano 18.05.2012

1. Znajdź funkcję tworzącą dla ciągu a_n = 5 ^ n, dla n >= 3, oraz a_n = 0 dla pozostałych.

// ogarnal by ktos to zadanie?

a_n=5^n i n>=3 wiec

Suma od 0 do inf=(5x)^n+3 = 125x^3*Suma od 0 do inf(5x)^n=125x^3/1-5x all :D

2. Na ile obszarów dzieli płaszczyznę graf płaski mający 35 wierzchołków i 45 krawędzi.

W - K + S = 2

35 - 45 + S = 2

S = 12

3. Ile trójkątów wyznacza 15 punktów, z których 5 leży na jednej prostej, 10 na drugiej, a te dwie proste są równoległe.

(5 po 1)*(10 po 2) trójkąty z podstawą na prostej `10'

(5 po 2)*(10 po 1) trójkąty z podstawą na prostej `5'

wynikiem jest suma

4. Znajdź liczbę rozwiązań równania x_1 + x_2 + ... + x_5 = 30, w liczbach całkowitych, takich że wszystkie x_1 >= 3

x_1+x_2+...+x_5=27 [bo odejmujemy 3 zeby bylo z warunku ze x_1 >= 3]

i potem mozna dalej robic jak z monetami

oooo|oooooo|oooooo|oooooooo|oooo

co nam daje 27+4 po 4

A nie 3? przeciez moze byc rowne 3, no chyba ze ta metoda pozwala na nie wybranie ani jednego dla ktorejkolwiek przegrodki, o czym ja nie mam pojecia :) w takim wypadku osoba na czerwono ma racje i bedzie inny wynik

Powinniśmy odjąć 3 ponieważ x1 nie może być 0,1,2 więc odpadają 3 możliwośći //popr.

30-7=23 , potem bierzemy 4 przegrodki ... ostatecznie ( 23 +4 po 4 ) ?

dlaczego -

? nigdzie nie jest napisane ze nie mozna miec rozwiazania zerowego// 7 bo , za x1 =y1 +3 , x2=y2+1+ ..+ x5=y5+1 .= 30 po lewej stronie bedziesz miec y1+y2...+7=30
// całkowite to też liczba “0”, a warunek dotyczy tylko pierwszego wyrazu x₁ więc tylko x₁=y₁+3, a pozostałe to x_i=y_i , podane rozwiazanie jest dobre (27+4 po 4) i skończcie z tą oczodajną tęczą, istnieją kolory mniej jaskrawe...

5. Podaj rozwiązanie ogólne rekurencji r_(n+2) + 4 * r_(n+1) = -4 * r_(n)

r_n = k*(-2)^n + l*(-2)^n *n // --8 imho bo delta =16 sqrt x0=-16/2=-8 potwierdzi ktos?

x^2+4x+4=0 delta = b^2-4ac tu = 0 // odpowiedz dobra // k bo x0=-4/2=-2 sory za wprowadzenie w blad :)

6. Podaj liczbę chromatyczną (wierzchołki) i indeks chromatyczny (krawędzie) szkieletu piramidy (ostrosłup o podstawie kwadratowej)

indeks = 4 // ktos moze to wytlumaczyc ? tutaj krawedzie to jak bedzie ?

liczba = 3 // -||- bo n to sa wierzcholki ? a wiec nieparzyste wierzholki ..jest ich 5 .. czyli n-1 ?5-1 ?/ bo naryswoalismy to sobie i na mniej sie nie da:)//

tutaj chodzi tylko o krawedzie podstawy ? na co trzeba patrzec ? xD zeby wiedziec jaka jest liczba chromatyczna i indeks chromatyczny ? // w odp jest blad btw, powinno byc na odwrot//ktos powie jak to zrobic ?// z indeksem - malujesz sobie czubek jakims kolorem A, zostaje Ci podstawa, ktorej przeciwlegle wierzcholki malujesz na B i B i na C i C+ ogolnie wierycholki, ktore sa ze soba styczne nie moga byc pokolorowane na ten sam kolor

indeks powinien wynosić 5 // wygląda, że tak // krawedz e malujemy na czerwono, a stara krawedz a przy podstawie malujemy na fioletowo = 4??//przecież wtedy E:=A, a nie może...// bullshit xd zobacz na rysunek teraz indeks =3 liczba=4 i tak ma być!!!!!!!!!!! // Przeciez z rysunku dokładnie wynika, ze liczba = 3, a indeks = 4, liczba to wierzchołki, indeks to krawędzie -_-

7. W drzewie 7-wierzchołkowym wierzchołek 1 sąsiaduje z 2, 3, 4, 5 i 6, a wierzchołek 6 z wierzchołkiem 7. Znajdź kod Pruefera tego drzewa.

Kod Prufera to 11116

8. W grafie C_(12) z naturalną numeracją wierzchołków, dodajemy krawędź 1-5. Ile drzew spinających ma taki graf?

aaa jest prostsze rozwiazanie :P Normalnie graf C_n ma n drzew spinajacych (bo nie mozna polaczyc ostatniej krawedzi z przedostania). Jesli dodamy ta 1-5 to nie mozemy polaczyc 2krawedzi wiec jest 11drzew spinajacych “naokolo” + 9 kombinacji z lewego grafu i 5 prawego. 9*5+11=56

//taka dziwna teoria ale wyszlo :P

// no ładne rzeczy i od razu skapowałem ^^

//moim zdaniem jak usuniemy krawedz 1-5 to mamy 12 drzew spinajacych, jesli ja zostawic to mozemy usunac 1 z 4 krawedzi po lewej i 1 z 8 po prawej wiec mysle ze to bedzie 12 + 4*8

Zgodzę się, że będzie 12+4*8, ja bym jeszcze dodał 12+4*8+4+8, bo: 4*8 - 1 z 4 krawedzi po lewej i 1 z 8 po prawej, +4 - bo możemy usunąc tylko jedną krawędź po lewej i +8 bo usuwamy tylko po prawej, zgodzi się ktoś ?

//a moze tak: graf Cn ma n drzew spinajacych. z tego polaczenia mamy 2 drzewa Cn z 1 wspolna krawedzia. C5 i C9 => 5+9 lub 5*9 lub cos w tym kierunku?//no to tak jak wyzej zrobilem ^^ chyba http://www.matematyka.pl/201199.htm nie moge otworzyc linku :<
// nie wygląda, moment.

http://di.com.pl/news/45338,0,Leap_3D_jest_100_razy_precyzyjniejszy_niz_Kinect_wideo.html

Czyli nie wiadomo wkońcu jak jest naprawdę?

http://i.pinger.pl/pgr209/b8c101d50025af5e4f9586a4

Z cwiczeń z Zakrzem wynika, że wersja 12+4*8+4+8 jest prawidłowa, tak samo jak jej tłumaczenie (choć nie jestem przekonany do tych +4+8, czy akurat te wartości)

9. Na ile istotnie różnych sposobów można pokolorować sześciokąt podzielony na 6 trójkątów równobocznych za pomocą 3 kolorów? Pokolorowania uznajemy za jednakowe, gdy jedno da się uzyskać z innego przez obrót.

Fix0 = 3^6

Fix60=Fix300=3

Fix120=3^3

Fix180=Fix240=3^2

Odpowiedź: (Fix0 + Fix60 + Fix120 + Fix180 + Fix240 + Fix300) / 6=(3^6 + 2*3 +3^3+2*3^2) / 6

10. Znajdź funkcję tworzącą dla ciągu zadanego rekurencją a_(n+1) = 4 * a_n + 2, dla a_0 = 1

11. Sformułuj odpowiednią nierówność pomiędzy liczbą krawędzi a liczbą wierzchołków grafu planarnego i wywnioskuj stąd że graf kostki 6-wymiarowej nie jest planarny.

WTF?

Dla grafu zwykłego planarnego nie zawirającego trójkątów: k <= 2w - 4 może z tego trzeba skorzystać?

Oczywiście, że z tego. Kostka ma 2^6 = 64 wierzchołków i 6 * 2^(6-1) = 192 krawędzie

Ostatecznie 192 <= 2*64-4=124, sprzeczność.

grupa C

grupa E

grupa G

1. Znajdź liczbę rozwiązań x₁ + x₂ + … + x₇ = 40 takich, że x₁ >= 3

3ze x_i >0 lub x_i >= 0,

gdzie i = 2, 3, … 7 | Zakrzewski podobno coś na tablicy dopisywał)

•dla x_i > 0:

x₁ = y₁ + 3

x₂ = y₂ + 1, x₃ = y₃ + 1, …, x₇ = y₇ + 1, y_j >= 0 (j = 1, 2, …, 7)

y₁ + 3 + y₂ + 1 + y₃ + 1 + … + y₇ + 1 = 40 //tylko x₁ >= 3 !! imho w treści jest po prostu bład przepisywanie. Z kontekstu wynika, że dla “wszystkich” x, czyli x z indeksem “i” // być może

y₁ + y₂ + … + y₇ = 31 Pozdrowienia z Wrocławia

// Mozna prosciej :) bierzesz ilość przegródek czyli 6 i wtedy wystarczy 31+6 czyli (37 po 6) :)//i o to chodziło thx //np :D

•dla x_i >= 0

x₁ = y₁ + 3

x₂ = y₂, x₃ = y₃, …, x₇ = y₇, y_j >= 0 (j = 1, 2, …, 7)

analogicznie jak wyżej:

(37 + 7 - 1 po 7 - 1)

2. Znajdź funkcje tworzącą dla ciągu a_n = 2ⁿ, gdy n>= 4 oraz a_n = 0 w pozostałych przypadkach.

Funkcja tworzaca dla 2ⁿ, to 1/(1-2x) // ( btw. dla 3ⁿ,1/(1-3x) ), ciekawostka
Opisuje ona sumę 1+2x+(2x)²+(2x)³+...+(2x)ⁿ +...

(bo
)

I sposób

gdy odejmiemy od całej sumy sumę pierwszych czterech (n<4) czyli

n=0,1,2,3

1+2x+(2x)²+(2x)³

mamy:

- (1+2x+(2x)²+(2x)³)

po skroceniu:

//sprawdzałem w Wolframie, jest dobrze:D

//Można to bardziej pogrupować niż wykonywać tyle mnożenia

0/3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333/nom ofc ale tak kazdy widzi :P
II sposób

, teraz zmieniamy “granicę”, żeby ta suma dla n=<0,3> przyjmowała 0.

// E(n) - suma od n do inf
// E(0) (2x)⁽ⁿ⁺⁴⁾ = (2x)⁴ * E(4) (2x)ⁿ

3 . Zapisz w formie permutacji symetrię osiową sześciokąta foremnego o wierzchołkach 1,2, …, 6 względem osi 2, 5 (wierzchołki 2 oraz 5)

Rozłóż ją na cykle.

(13)(2)(46)(5)

4. Narysuj drzewo o kodzie P3rufera 32555

6

|

1 - 3 - 2 - 5 - 4

|
7

//wytłumaczenie

//punkt 39

https://docs.google.com/document/d/1AxLa5iTjVwd02cJBmpMGQsgQS21vztyEanWudk_R8Nw/edit

5. Dla jakich n graf K_n,2 jest eulerowski? Dla jakich hamiltonowski?

Eulerowski dla n parzystych, hamiltonowski dla n=2

<- skąd to wiadomo? eluerowski, bo wierzcholki parzysty stopien.

polecam cwiczenie 2 i 4:

http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/%C4%86wiczenia_13:_Grafy_II

6. Podaj liczbę chromatyczną (dotyczy kolorowania wierzchołków) grafu powstałego z K₁₀ przez usunięcie jednej krawędzi. Odpowiedź uzasadnij.

n-1, ponieważ wierzchołki, z której usunięto krawędź mogą mieć ten sam kolor

// Zakrzu ma u siebie twierdzenie

7. Oczywistości: Liczba chromatyczna (wierzchołkowa) grafu Kn jest równa n -1, więc w odpowidzi powinno być chyba n - 2

Zakrzu się walnął. n-1 to dobra odpowiedź

`no dobra, niech bedzie. WIerze na słowo :P

7. Znajdź liczbę wszystkich funkcji f: [1,2, …, 9] -> {1, 2, 3} będących funkcjami “na”

3^9-3*2^9-3^1

Tutaj ktoś to mądrze wytłumaczył :

http://www.matematyka.pl/204108.htm

(3 po 0)3^9 - (3 po 1)* 2^9 + (3 po 2) *1^9 - (3 po 3)*0^9o0

8. r_{n + 2} + 9r_n = - 6r_{n + 1}

- Podaj rozwiązanie rekurencji o równaniu charakterystycznym.

xⁿ⁺² + 6xⁿ⁺¹ + 9xⁿ = 0 / xⁿ

x² + 6x + 9 = 0

(x + 3)² = 0

x_1,2 = -3, stąd a_n = (-3)ⁿ, b_n = (-3)ⁿn (a_n i b_n to para niezależnych rozwiązań)

f_n = K*(-3)ⁿ + L*(-3)ⁿn, dla K,L dowolnych

// x₁ == x₂ (pierwiastek podwójny):

a_n = (x₁)ⁿ b_n = (x₂)ⁿ * n

// gdyby pierwiastek nie był podwójny:

a_n = (x₁)ⁿ b_n = (x₂)ⁿ

// dalej podstawiamy f_n = K * a_n + L * b_n

9. Na ile istotnie różnych sposobów można pokolorować prostokąt 5x2 za pomocą 4 kolorów. Pokolorowania uznajemy za jednakowe, gdy jedno z nich da sie uzyskać z drugiego przez obrót lub symetrię.

//wiem, że się czepiam, ale czy prostokąt 5x2 nie powinien być rysowany tak jak macierz?

G = { I (O o 0st), O o 180st, S |, S -- }

//kk, rozumiem czacze juz :P Sposoby to te bez zmiany rowniez ...

Fix I = 4^10r

Fix O o 180st = 4^5

Fix S | = 4^6

Fix S -- = 4^5

//skąd to sie bierze?

Dla S |:

1	2	5	2	1
3	4	6	4	3

(4^10 + 4^5 + 4^6 + 4^5) * ¼ = ...

10. Znajdź liczbę ścian, krawędzi, wierzchołków w grafie płaskim, w którym wszystkie ściany są trójkątami, a stopień każdego wierzchołka wynosi 5.

ściany sa trójkatami stad

2K = 3S -> K = 3/2 S
//skąd to się wzięło? :) // wszystkie ściany składają się z trójkątów czyli z 3 krawędzi, ale to jest podwójna liczba krawędzi, bo każda krawędź jest krawędzią dwóch ścian

można zauwazyc ze kazde dwie krawędzie stykaja sie z 3 ścianami

gdy z wierzchołka styka się 5 trójkątów

5W=3S-> W=3/5 S // tu nie powinno byc 5W=3K?;> Narysuj sobie 5 wierzchołków i połącz je wszystkie tylko 3 ma krawędziami xD // u Zakrza w rozwiazaniach tak est napisane // czyli dobry ten wynik w koncu?? // wydaje mi się że dobrze, bo w końcu Wąsu tak na wykładzie rozwiązał takie zadanko, ale skąd to się wszystko wzięło to za cholerę rozkminić nie mogę

W-K+S=2 //Gwoli ścisłości - ten skrót tłumaczy się tak: Wąsu Kosi Studentów i wstawia 2// MOZG ROZJEBANY :D//

3/5S - 3/2S + S = 2 // poprawione, dalsza część mimo tego była i jest dobrze
1/10S=2
S= 20

K=30

W=12

11. Korzystając z zasady indukcji matematycznej wykaż, że dla n >= 2

(2 po 2) + (3 po 2) + … + (n po 2) = (n + 1 po 3)

Krok początkowy:

n=2

(2 po 2) = 1 = (2+1 po 3)

Przejście indukcyjne:

Załóżmy, że dla ustalonego n zachodzi wzór (ten, który trzeba udowodnić). Pokażemy, że zachodzi też dla n+1

(2 po 2) + (3 po 2) + … + (n po 2) + (n+1 po 2) = (ind.) (n+1 po 3) + (n+1 po 2) = ((n+1)+1) po 3)

Fioletowa suma to (n+1 po 3) z założenia indukcyjnego. // wyszla komus ta indukcja? // ostatni krok to jest własność

i z tego wychodzi

//Można po prostu zastosować tożsamość Pascala (I wykład): (n po k) + (n po k+1) = (n+1 po k+1) i wsio :-)

grupa E

1. Znajdź funkcje tworzącą dla ciągu an = 2^n, gdy n >= 3 oraz an = 0 w pozostałych przypadkach. (podobne do zadania 2. grupa C)

2. Oblicz dowolną metodą liczbę Bella B3

B0 = 1, B1 = 1, B2 = B0 + B1 = 2, B3 = B0 + 2B1 + B2 = 5

Wzór = Suma(od i = 0 do n)((n po i)*Bi))

3. Znajdź liczbę rozwiązań równania x1 + x2 + … + x7 = 30 takich, że x1 >= 2 (podobne do zadania 1 grupa C)

4. Znajdź liczbę wszystkich funkcji f: [1,2, …, 8] -> {1, 2, ?} będących funkcjami “na” (podobne do zadania 7 grupa C)

5. Narysuj drzewo o kodzie Prufera 12555

6

|

3-1-2-5-4

|

7

// czy to nie powinno być inaczej? jeśli chcemy to teraz zapisać w kodzie, wychodzi 55521 kodujemy zapisując od prawej do leewej // nie nie nie zapisujemy usuniete na koniec ciagu wiec jak usuwamy 3 to koncem jest poczatek i mamy 1 z kolei jak usuniemy jeden to koniec jest po 1 czyli 12555

6. Dla jakich n graf K_2,n jest eulerowski ale nieplanarny. Dlaczego?

Dla żadnych... Ponieważ zawsze można wziąć ustawić w jednej linii n wierzchołków, jeden z tych dwóch zdeterminowanych nad nie, drugi pod nie, zawsze jest planarny.

Zbadamy kiedy jest planarny. Z pierszego lematu o planarności grafów 2K <= 3N - 6

Podstawiamy : 2n <= 3(n+2) - 6 wychodzi n >= 0

Wtedy jest planarny, więc nieplanarny jest nigdy.

! tu trzeba skorzystac z nierównosci K<=2W-4

7. Podaj liczbę chromatyczną i indeks chromatyczny grafu powstałego z K₄ przez usunięcie jednej krawędzi. Uzasadnij.

Liczba chromatyczna - 3 , jak usuniesz jedna krawedz , to wierzcholki z usunietych krawedzi moga miec ten sam kolor.

Indeks chromatyczny - 3, bo generalnie wierzchołki K4 sa stopnia 3, a wywalenie jednej krawedzi i tak nic nie zmieni bo dalej beda 2 wierzcholki stopnia 3 co w rezultacie wymaga 3 kolorow by pomalowac te krawedzie.

grupa G (tylko unikalne zadania)

2. Znajdź liczbę dzielników 8!

8! = 8*7*6*5*4*3*2 = 2^3 * 7 * 2 * 3 * 5 * 2^2 * 3 * 2 = 2^7 * 3^2 * 7 * 5

8*3*2*2 = 24*4 = 96 // iloczyn (potęg + 1)

9. Na ile istotnie różnych sposobów można pokolorować sześciokąt foremny podzielony na 6 trójkątów równobocznych za pomocą 3 kolorów. Pokolorowania uznajemy za jednakowe, gdy jedno z nich da się otrzymać przez obrót drugiego.

Fix0o=3^6

Fix60o=3 // a nie 3^3? nie daje glowy ^^ // Nie jak obracasz o 60st to masz tylko 1 znaczek

Fix120o=3^2

Fix180o=3^3 // nie 3? j.w

Fix240o=3^2 //3^4? j.w.

Fix300o=3 // 3^5? j.w.

(X/G)= (3^6+2*3+2*3^2+3^3)/6

//sprawdzcie plx /\ //zniszczyles system ;) wedlug mnie jest ok ;d // dobrze jest

Kto nie wierzy niech wydrukuje, wytnie i poobraca sobie :P. //Fajne :D

11. Korzystając z zasady indukcji matematycznej wykaż, że

1 + 3 + 5 + … + (2n - 1) = n^2

dla n=1 oczywiste

blablabl formułka, sprawduzamy dla n+1

1+3+5+...+(2n-1)+(2n+1)=(n+1)^2

n^2+2n+1=n^2+2n+1

0=0

[•]

/// dodaje drugi raz grupe G (calosciowo) // rozwiązania powyżej!!!!!

1. Znajdź liczbę ścian, krawędzi i wierzchołków w grafie płaskim, w którym ściany są trójkątami a stopień każdego wierzchołka wynosi 5.

2. Korzystając z zasady indukcji matematycznej wykaż, że dla n należących do N+ 1+3+5+…(2n-1)=n2 Zastosowanie indukcji obowiązkowe!

3. Podaj liczbę chromatyczną (dotyczy kolor. wierzchołków) i indeks chromatyczny (dot. Krawędzi grafu powstałego z K4 przez usunięcie jednej krawędzi. Odp uzasadnij!

4. Znajdź liczbę dzielników liczby 8! (widziałem też liczbę 604)

5. Znajdź liczbę funkcję tworzącą dla ciągu an = 2n dla n >=3, an = 0 w pozostałych przypadkach.

6. Oblicz dowolną metodą liczbę Bella B3.

7. Znajdź liczbę rozwiązań równania x1+x2+…+x7=30 takich, że wszystkie x1>=2.

8. Znajdź liczbę wszystkich funkcji f:{1,2,…,8} -> {1,2,3} będących funkcjami na.

9. Narysuj drzewo o kodzie Pruefera 12555.

10. Dla jakich n graf K2,n jest eulerowski, ale nieplenarny? Dlaczego?

11. Na ile istotnie różnych sposobów można pokolorować sześciokąt foremny podzielony n 6 trójkątów równobocznych za pomocą 3 kolorów? (druga wersja była kwadrat, 4 trójkąty i 2 kolory) Pokolorowania uznajemy za jednakowe, gdy jedno z nich da się uzyskać z obrotu drugiego przez obrót.

GRUPA G godzina 14

--> [Author:(null)]

jaroslaw.szumega:

Doszla cala grupa G, pozdrawiam :P

---