grafy i kombinatoryka

[liceusik]

Prosiłbym o pomoc w rozwiązaniu 4 zadanek. Niedługo maturka, a tutaj takie coś dostajemy... 1-2 są proste, ale chciałem się też upewnić. Oto one:


ZAD. 1
a) Z grupy 2n osobowej, złożonej z n mężczyzn i n kobiet, chcemy wybrać podzbiór przy jednym tylko zastrzeżeniu, że liczba wybranych mężczyzn jest równa liczbie wybranych kobiet. Stosując wynik zadania 7, pokaż, że taki podzbiór może być wybrany na \(\displaystyle{ {2n\choose k}}\) sposoby.
b) Tym razem chcemy wybrać podzbiór tak jak w a), a następnie wskazać przywódcę spośród mężczyzn i przywódczynię spośród kobiet tego podzbioru. Obliczyć liczbę sposobów wybrania najpierw konkretnego podzbioru, a następnie odpowiednich przywódców, a także obliczyć liczbę sposobów wybrania najpierw przywódców, a następnie pozostałych należących do podzbioru. Wywnioskować, że:

\(\displaystyle{ 1^{2}}\) \(\displaystyle{ {n\choose 1}^2}\) + \(\displaystyle{ 2^{2}}\) \(\displaystyle{ {n\choose 2}^2}\) + \(\displaystyle{ 3^{2}}\) \(\displaystyle{ {n\choose 3}^2}\) +...+ \(\displaystyle{ n^{2}}\) \(\displaystyle{ {n\choose n}^2}\) = \(\displaystyle{ n^{2}}\) \(\displaystyle{ {2n \ - \ 2\choose n \ - \ 1}}\)
c) Stosując różna metody, pokazać, że: \(\displaystyle{ {n\choose 1}}\) + 2 \(\displaystyle{ {n\choose 2}}\) + 3 \(\displaystyle{ {n\choose 3}}\) +...+ n \(\displaystyle{ {n\choose n}}\) = \(\displaystyle{ n2^{n-1}}\)

Zad. 2
Gra, zwana po angielsku "sprouts" jest grą między dwoma osobami. Na płaszczyźnie jest oznaczona dowolna liczba wierzchołków. Każdy z graczy, na przemian, dodaje nowy wierzchołek i łączy go krawędziami z dwoma istniejącymi wierzchołkami. Jedynymi warunkami są te, że otrzymywany rysunek musi być planarną reprezentacją jakiegoś grafu i że żaden wierzchołek nie ma stopni większego od 3. Przegrywa ten gracz, który pierwszy nie może wykonać swojego ruchu. Pokazać że niezależnie od liczby początkowych wierzchołków, gra zawsze musi mieć swój koniec.

[ Dodano: 16 Stycznia 2008, 02:53 ]
Już z góry dziękuje za wniesioną pomoc!

Zad. 3
Na ile wierzchołków można pomalować
(1) wierzchołki
(2) krawędzie
zamieszczonego poniżej grafu trzema kolorami, tak aby każdy kolor został użyty dwa razy?
._._._.

[kinwotar]

z1. a) liczba tych podzbiorów równa jest \(\displaystyle{ \sum_{k=0}^{n} }\) jezeli uwzglenimy pozdbiór pusty czyli ilosc facetów i kobiet jest 0 a jak nie uwzglednimy to wystarczy odjąc jeden.

nie wiem co wychodzi w zadaniu 7 z którego trzeba to rozwiązać ale jest taki wzór który można udowodnić kombinatorycznie: \(\displaystyle{ \sum_{k=0}^{l} {m \choose l-k}= {{n+m} \choose l}}\) jak teraz podstawisz n=m=l no to ci wyjdzie to co trzeba.

b) co do podpunktu b to popraw bo tam minus napisales zamiast = i brakuje minusow w nawiasach no ale ogolnie to ci przepisze rozwiazanie z ksiazki z.palki bo sam bym tego lepiej nie wykminil:
prawą strone możemy tak zapisać bowiem możemy najpierw wybrać przywódców a dopiero później uzupełnic nasz wybór o dowolną, ale równą liczbę kobiet i mężczyzn. po zastanowieniu się zdanie to okazuje się prawdziwe

poza tym, jak na "niedługo maturka" to te zadania są mega trudne, spokojnie można je dać studentom na politechnice.

c) no to normalnie rozpisujesz dwumian na silnie potem dzielisz przez n prawą i lewą strone, zwijasz silnie spowrotem do dwumianów z tym że teraz będzie wszystko (n-1) no i ci wyjdzie suma dwumianów od \(\displaystyle{ {{n-1} \choose 0}}\) do konca. czyli tyle co po prawej zostalo.

[liceusik]

Dzięki! Takie błędy się robi jak się szybko przepisuje:)
No tak, to pierwsze i ostatnie są "trochę" trudne w porównaniu dla tych dwóch środkowych...

[ Dodano: 17 Stycznia 2008, 23:46 ]
A czy ktoś wie jak zrobić zadanie nr 4? To też mnie bardzo nurtuje