Strona 1 z 1

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

: 9 paź 2007, o 22:52
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.

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

: 10 paź 2007, o 17:25
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!}\)