Kolokwium Saris: Jest ktoś w stanie posiedzieć ze mną nad zadaniami z matematyki dyskretnej? W środę o 8:00 mam I termin kolosa zaliczeniowego obejmującego: − grafy − szufladki dirichleta − funkcje tworzace − wzor jawny ciagu rek. − zasada wlaczen i wylaczen − ogolnie kombinatoryka Dzięki z góry . Teraz uczę się analizy, ale jutro od 15 siadam na dyskretną.

Saris: Dobra, żeby nie rzucać słów na wiatr. 1. Niech A będzie podzbiorem zbioru {1,2, ..., 149, 150} złożonym z 25 liczb. Wykaż, że istnieją dwie rozłączne pary elementów zbioru A, mające te same sumy. 2. Kowalscy, Nowakowie i Wiśniewscy mają po pięcioro dzieci. Cała piętnastka biwakuje w pięciu (rozróżnialnych) 3−osobowych namiotach. Ile jest rozmieszczeń takich, żeby każda rodzina miała co najmniej jeden namiot z przynajmniej dwójką swoich dzieci. 3. Znajdź ciąg, którego funkcja tworząca zadana jest wzorem:

	3x−1
f(x)=
	2x2−3x+1

4. Dany jest graf G o zbiorze wierzchołków V(G)={10, 11, 12, ..., 97, 98, 99}. Dwa wierzchołki grafu G połączone są krawędzią, jeśli mają tą samą liczbę jedności lub dziesiątek. Czy graf G jest eulerowski? planarny? Odpowiedź podaj wraz z uzasadnieniem. 5. Na ile sposobów można rozmieścić 4 identyczne pomarańcze i 6 różnych jabłek (każde innego gatunku) w pięciu różnych skrzynkach. 6. Znajdź ciąg spełniający równanie rekurencyjne: a_n=7a_n−1−10a_n−2+4n+3, a₀=4, a₁=2 7. Znajdź drzewo oznakowane o kodzie Prufera (1,1,4,2,2,4,3,3) Udowodnij, że gra dwudzielny o nieparzystej liczbie wierzchołków jest niehamiltonowski. 8. Pokaż, że w każdym grafie są conajmniej dwa wierzchołki tego samego stopnia. Zrobię teraz 3/6/7. Liczę na czyjąś pomoc albo wskazówki z resztą zadań . Bo na razie jestem noga z tego.

Saris: 3.

	−2		1
f(x)=U{3x−1}{(x−1)(2x−1)=		+		=−2∑xn+∑(2x)n ⇒ an=2n−2
	1−x		1−2x

Dobrze?

Saris: 7. 6−1−5 | 4−3−9 | | | 10 | 8−2−7 Jeszcze nie wiem jak udowodnić.

Saris: 6. a_n−7a_n−1+10a_n−2=4n+3 a₀=4 a₁=2 a_n=a_n^J+a_n^S (J−równanie jednorodne, S−równanie specjalne) a_n=rⁿ rⁿ−7ⁿ⁻¹+10rⁿ⁻²=0 r²−7r+10==0 r₁=5 r₂=2 a_n^J=C₁*5ⁿ+C₂*2ⁿ a_n^S=c*n+b Podstawiam do głównego równania: cn+b−7(c(n−1)+b)+10(c(n−2)+b)=4n+3 4cn+4b−13c=4n+3 4c=4 ⇒ c=1 4b−13=3 ⇒ b=6,5 a_n^S=n+6,5 a_n=a_n^J+a_n^S a_n=C₁*5ⁿ+C₂*2ⁿ+n+6,5 a₀=4=C₁*5⁰+C₂*2⁰+0+6,5 a₁=2=C₁*5¹+C₂*2¹+1+6,5 C₁=−1/6 C₂=−7/3 a_n=(−1/6)*5ⁿ+(−7/3)*2ⁿ+n+6,5 Ktoś sprawdzi?

Saris: 5. 6 różnych jabłek wybieramy na 5⁶ sposobów, a identyczne pomarańcze rozmieszczamy na

	4+5−1 5
		sposobów.

	4+5−1 4
Razem 56*

Saris: pomogl by ktos z innymi?

Saris: .