podział na klasy w kartografii

bregalad · Post autor: **bregalad** » 31 sie 2010, o 14:17

Witam forumowiczów. Jest to mój pierwszy post więc proszę o wybaczenie pewnych błędów jakie mogę popełnić.

Mam następujące zadanie do rozwiązania.
Na ile sposobów można podzielić pola podstawowe w metodzie kartogramu przy danej ilości klas.

Polami podstawowymi mogą być np. województwa w Polsce (18). Postanawiamy zobrazować zagęszczenie ludności w tychże województwach na mapie i użyć metody kartogramu. Zbieramy województwa w szereg od najmniejszej wartości zagęszczenia do największej i zakładamy, że dzielimy województwa na 5 klas. Województwo o najmniejszej wartości znajdzie się w klasie pierwszej a o największej w piątej. Resztę województw przypisujemy kolejno wg wartości do klas od 1 do 5. Ile jest możliwych podziałów?

Konikov · Post autor: **Konikov** » 1 wrz 2010, o 20:15

Witamy na forum ;]

Twoje zadanie odpowiada takiemu oto zagadnieniu:

Mamy zbiór {1, 2, ..., 18} (n = 18) i chcemy go rozdzielić na 5 niepustych podzbiorów, w których elementy są kolejnymi liczbami. Bardziej obrazowo: chcemy w ten zbiór wstawić 4 przedziałki, które będą go dzieliły na zbiory. Liczymy na ile sposobów można to zrobić.

Mamy 17 (n - 1 = m) miejsc w które możemy wstawić podział. Teraz można na to spojrzeć na co najmniej 2 sposoby:

1. Chcemy wziąć 4-el. podzbiór 17-el. zbioru (zaniedbujemy kolejność, gdyż to jest podzbiór, a nie ciąg).
\(\displaystyle{ {17 \choose 4}}\)

2. Numerujemy przedziałki po kolejności występowania. Pierwszy przedziałek możemy wstawić za liczbami 1 aż do 14 (muszą zostać 3 miejsca na kolejne). Gdy wybierzemy miejsce pierwszego, mamy od następnego aż do 15 miejsca na drugi przedziałek. Idąc tą drogą:
\(\displaystyle{ \sum_{i_1=1}^{m-3} \sum_{i_2> i_1}^{m-2} \sum_{i_3> i_2}^{m-1} \sum_{i_4> i_3}^{m} 1}\)
Co w zasadzie sprowadza się do tego samego co punkt 1.

bregalad · Post autor: **bregalad** » 1 wrz 2010, o 22:34

dzięki za odpowiedź: 1 sposób rzeczywiście banalnie prosty
nie rozumiem natomiast sposobu drugiego. Czy mógłbym prosić o rozpisanie na przykładzie n=7 i 4 podzbiorach?

Konikov · Post autor: **Konikov** » 1 wrz 2010, o 23:10

Drugi sposób można zrozumieć rysując sobie kropeczki ;] Narysuj 6 rzędów kropeczek po 4 w każdym (będzie to Twój przykład dla n = 7, ponieważ m = n - 1). Teraz każda kolumna to odpowiednik kolejnej sumy. Ponumeruj rzędy, będą one oznaczały liczby, za którymi można postawić przedział. Naszym zadaniem jest policzenie ile jest dróg z prawo na lewo, zachowując własności tej dużej sumy, którą napisałem powyżej.

Za pierwszym razem możesz wybrać kropeczki od 1 do 3. Każda kolejna kolumna musi mieć wybraną kropkę o numerze większym od poprzedniej.

Wynik to wszystkie możliwe drogi.

Jeśli rozumiesz, skąd sam wzór się wziął, to masz dowód na to, że owa suma jest innym wyrażeniem kombinacji bez powtórzeń ;]

Tutaj znajduje się podobne zadanie, tylko z kombinacją z powtórzeniami: 205936.htm

bregalad · Post autor: **bregalad** » 1 wrz 2010, o 23:38

Konikov pisze:... po 4 w każdym ...

chyba chodziło o 3

dzięki jeszcze raz

ostatnia prośba: czy mógłbyś napisać wzór ogólny dla drugiego sposobu dla dowolnej ilości pól podstawowych i klas?

Konikov · Post autor: **Konikov** » 2 wrz 2010, o 00:03

bregalad pisze:chyba chodziło o 3

Yup ;]

Proszę bardzo:

\(\displaystyle{ \sum_{i_{1} = 1}^{m - k + 1} \sum_{i_{2} = i_1 + 1}^{m - k + 2} ... \sum_{i_{k - 2} = i_{k - 3} + 1}^{m - 2} \sum_{i_{k - 1} = i_{k - 2} + 1}^{m - 1} \sum_{i_{k} = i_{k-1} + 1}^{m} 1}\)

Ilość niepustych podzbiorów: k + 1
Ilość elementów do podziału: m + 1