Rozmieszczanie zer i jedynek na n numerowanych miejscach

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Seido
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 9 kwie 2015, o 19:18
Płeć: Mężczyzna
Lokalizacja: Polska

Rozmieszczanie zer i jedynek na n numerowanych miejscach

Post autor: Seido »

Witam wszystkich. Nie ukrywam, że bardzo potrzebna jest mi wasza pomoc i porada dotycząca pewnego zadania z którym przyszło mi się spotkać.

Zadanie brzmi następująco : "Na ile sposobów można rozmieścić na n numerowanych miejscach \(\displaystyle{ k}\) zer i \(\displaystyle{ n-k}\) jedynek? Wykonać obliczenia dla \(\displaystyle{ n = 10}\) i \(\displaystyle{ k = 3}\)."

Z początku zadanie wydawało mi się banalne, lecz teraz w mojej głowie zapanował chaos. Wydaje mi się, że dla podanych już \(\displaystyle{ n}\) i \(\displaystyle{ k}\) zadanie powinno wyglądać w ten sposób:

Miejsc jest \(\displaystyle{ n}\), czyli \(\displaystyle{ 10}\). Załóżmy, że może to być nawet liczba dziesięciocyfrowa, tak tylko dla rozpatrywania tego przykładu w ten sposób. Ma się składać z \(\displaystyle{ k}\) zer, czyli z trzech, oraz \(\displaystyle{ n-k}\) jedynek, czyli z siedmiu.

W mojej głowie wygląda to tak:
\(\displaystyle{ 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 3 \cdot 2 \cdot 1=30240}\) - używając najpierw jedynek, a potem zer. Dało by to \(\displaystyle{ 30240}\) sposobów na rozmieszczenie zer i jedynek. Czy mój tok rozumowania jest prawidłowy, czy też trzeba tu wykorzystać jakiś wzór?

Martwi mnie głównie pierwsza część tego zadania, czyli pokazanie na ile sposobów można rozmieścić te zera i jedynki przy różnych \(\displaystyle{ n}\) i \(\displaystyle{ k}\). Idąc moim tokiem myślenia trzeba za każdym razem rozpisywać to w ten sposób, a jako, że jest to zadanie na pierwszym roku studiów mam przeczucie, że jednak, jak już pisałem wcześniej, niezbędny jest tu jakiś wzór i tak zrobione zadanie może przejść co najwyżej w liceum, ale nie na uczelni.

Z góry dziękuję za pomoc, pozdrawiam.
Ostatnio zmieniony 9 kwie 2015, o 19:53 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
cz0rnyfj
Użytkownik
Użytkownik
Posty: 187
Rejestracja: 25 cze 2013, o 18:52
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 26 razy

Rozmieszczanie zer i jedynek na n numerowanych miejscach

Post autor: cz0rnyfj »

Wygląda na to że coś przekombinowałeś.

Dla \(\displaystyle{ n = 10}\) nie możliwe jest żeby powstało tyle kombinacji z 2 cyfr \(\displaystyle{ (0, 1)}\) (rozwiązujesz to tak jakbyś miał do dyspozycji 10 cyfr)
po drugie w swoim rozwiązaniu nie uwzględniasz sytuacji kiedy na pierwszym miejscu masz \(\displaystyle{ 0}\)
np. \(\displaystyle{ 0111111100}\) <- taka liczba nie może powstać ,

Ja to widzę tak:
zapis dla \(\displaystyle{ n = 10}\)

\(\displaystyle{ 1 \cdot \frac{9!}{3! \cdot 6!} = 84}\)

1 - wybieram na pierwsze miejsce jedynke.
9! - to co mi pozostało przestawiam jak chce
mianownik - bo 11111 jest nie rozróżnialne, tak samo 000

oraz ogólny zapis

\(\displaystyle{ 1 \cdot \frac{(n-1)!}{k! \cdot (n-k-1)!}}\)
Seido
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 9 kwie 2015, o 19:18
Płeć: Mężczyzna
Lokalizacja: Polska

Rozmieszczanie zer i jedynek na n numerowanych miejscach

Post autor: Seido »

Generalnie to nie jest liczba, tylko ustawienie jedynek i zer na miejscach. Niepotrzebnie zamotałem z tą liczbą.
Fakt, liczyłem to jakbym miał \(\displaystyle{ 10}\) cyfr do dyspozycji - dopiero kilkanaście minut temu uświadomił mi to kumpel który podesłał mi notatki z wykładów. Według tego co z nim sobie uzgodniliśmy powinno to wyglądać tak:
\(\displaystyle{ \frac{10!}{3! \cdot 7!}=120}\)
Jak to się teraz prezentuje?
szachimat
Użytkownik
Użytkownik
Posty: 1674
Rejestracja: 23 sty 2015, o 21:47
Płeć: Mężczyzna
Lokalizacja: lubelskie
Podziękował: 6 razy
Pomógł: 354 razy

Rozmieszczanie zer i jedynek na n numerowanych miejscach

Post autor: szachimat »

Seido, napisane masz: "Na ile sposobów można rozmieścić na n numerowanych miejscach k zer i n-k jedynek?" - a zatem układy te nie dotyczą liczb.
Natomiast Twoje rozumowanie nie jest poprawne, gdyż nie jest powiedziane, że najpierw stoją jedynki.
Zacznę od najprostszych układów:
1) na ile sposobów można umieścić na trzech miejscach dwie litery "O" i jedną "K"?
- są to permutacje 3-elementowe z liter wyrazu "OKO":
- OKO, OOK, KOO - jest ich 3, a ze wzoru mamy: \(\displaystyle{ P _{3} ^{2,1}= \frac{3!}{2! \cdot 1!}}\)
2) ile jest permutacji z liter wyrazu "MAMA"?
- MAMA, MAAM, MMAA, AMAM, AMMA, AAMM - jest ich 6, a ze wzoru mamy: \(\displaystyle{ P _{4} ^{2,2}= \frac{4!}{2! \cdot 2!}}\)

A w twoim przykładzie będzie \(\displaystyle{ P _{n} ^{k,n-k}= \frac{n!}{k! \cdot (n-k)!}}\)
ODPOWIEDZ