szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Podział liczby
PostNapisane: 16 kwi 2015, o 00:49 
Użytkownik

Posty: 36
Lokalizacja: Kraków (UJ)
Mając liczbę n, chcę znaleźć wzór na liczbę wszystkich możliwych podziałów, które uwzględniają pozycje elementów w sumie (nie uwzględniają "różności" takich samych elementów).
Dla przykładu, n=4:

4 = 1+1+1+1 \newline
4 = 2+1+1 \newline
4 = 1+2+1\newline
4 = 1+1+2\newline
4 = 2+2\newline
4 = 1+3\newline
4 = 3+1\newline
4 = 4
Jak to uogólnić? Jak wyprowadzić wzór na liczbę takich podziałów?
Góra
Mężczyzna Offline
 Tytuł: Podział liczby
PostNapisane: 16 kwi 2015, o 08:14 
Użytkownik
Avatar użytkownika

Posty: 1229
Ustalmy n. pytamy się ile rozwiązań w liczbach całkowitychtarczy nieujemnych ma równanie

n = x_1+x_2+\ldots +x_n. Można to łatwo sprowadzić do przypadku, kiedy każdy x_i > 0. Wystarczy stronami dodać n. Otrzymamy wtedy:

2n = (x_1+1) + (x_2+1) + \ldots (x_n+1) \qquad (1)

Ile rozwiązań ma to równanie?

Wystarczy napisać sobie 2n kropek w rządku i między nie wstawić n-1 kreseczek. Liczba kółeczek między lewym brzegiem, a pierwszą kreską to x_1+1, liczba kółeczek między pierwszą a drugą kreską to x_2,... itp. Zatem wszystkich rozwiązań równania (1) jest

{2n \choose n-1}.

Pozdrawiam :)
Góra
Kobieta Offline
PostNapisane: 16 kwi 2015, o 09:15 
Użytkownik
Avatar użytkownika

Posty: 4419
Lokalizacja: Łódź
To nieprawda, np. n=2 można zapisać na dwa sposoby a nie na {4 \choose 1}=4
Raczej to będzie

{n-1 \choose 0}+{n-1 \choose 1}+{n-1 \choose 2}+...+ {n-1 \choose n-1}

bo maksymalnie pomiędzy n kropeczkami może być n-1 kreseczek a minimalnie żadnej kreseczki, oczywiście n \in N Nie sprawdzałam tego, więc zweryfikujcie.
Góra
Mężczyzna Offline
 Tytuł: Podział liczby
PostNapisane: 16 kwi 2015, o 15:32 
Użytkownik
Avatar użytkownika

Posty: 1229
Tak - moje rozwiązanie jest złe, bo za każdym razem zakładam, że składników jest tyle samo i dużo przypadków liczę po dużo razy.
Twoje rozwiązanie 2^{n-1} jest ok - mnie się poj...rąbało.
Góra
Mężczyzna Offline
 Tytuł: Podział liczby
PostNapisane: 16 kwi 2015, o 21:20 
Użytkownik

Posty: 36
Lokalizacja: Kraków (UJ)
@kropka+ : rzeczywiście, mi wyszło tak samo, chociaż rozumowałem nieco inaczej. Mając owe n kropek/kulek/czegośtam, mamy n-1 "przerw", w które możemy wsadzić kreskę. To bardzo intuicyjne, bo wtedy:
oo|o|o|ooo
oznaczałoby 2+1+1+3. Mając zatem n-1 przerw, w każdą z nich możemy wsadzic kreskę lub jej nie wsadzać, czyli 2^{n-1}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podział liczby  Maath  1
 Podział liczby - zadanie 3  cis123  2
 Podział liczby - zadanie 4  cis123  1
 Ilość sposobów ustawień w kolejce 4 osób i Liczby pięciocyfr  Gustlika  1
 Chlopcy i dziewczęta, podział  Natasha  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl