na ile sposobów ?? miasta i kapelusze ...

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
vhailor
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 10 paź 2006, o 22:42
Płeć: Mężczyzna
Lokalizacja: Kolno

na ile sposobów ?? miasta i kapelusze ...

Post autor: vhailor »

1 Jest 3 dostawców kapeluszy. Na ile sposobów możesz zamówić 7 kapeluszy? Przeprowadź analizę i podaj algorytm obliczania dla n kapeluszy.
2 Jest 6 miast połączonych drogami każde z każdym. Na ile sposobów można przejechać z miasta A do miasta B? przeprowadź analizę i podaj algorytm obliczania dla n miast.
jovante
Użytkownik
Użytkownik
Posty: 204
Rejestracja: 23 cze 2007, o 14:32
Płeć: Mężczyzna
Lokalizacja: Siedlce
Pomógł: 56 razy

na ile sposobów ?? miasta i kapelusze ...

Post autor: jovante »

Przejdę od razu do przypadku ogólnego:

1. Ze wzoru na kombinacje z powtórzeniami mamy \(\displaystyle{ {n+k-1 \choose k-1}}\), gdzie n to liczba kapeluszy, zaś k to liczba dostawców.

2. Zadanie nie jest do końca jednoznaczne, więc czynię dwa założenia:
- żadne trzy miasta nie leżą na jednej prostej
- różne drogi występują z dokładnością do kolejności przejeżdżania przez kolejne miasta (przy czym wyruszamy z miasta A i kończymy na mieście B), przy czym przez żadne miasto nie przejeżdżamy dwukrotnie

\(\displaystyle{ \sum_{k=0}^{n-2}{n-2 \choose k}k!}\)
ODPOWIEDZ