Dostałem zadanie na ferie, które brzmi:
Dany jest alfabet o S literach. Ile różnych słów o długości L można utworzyć z liter danego alfabetu zakładając, że chcemy użyć N różnych liter?
Przykładowe rozwiązanie dla S = 10, L = 4, N = 2 wynosi 630, bo mamy takie kombinacje:
ABBB -> 10*9
BABB -> 10*9
BBAB -> 10*9
BBBA -> 10*9
AABB -> 10*9
ABBA -> 10*9
ABAB -> 10*9
Na kartce potrafię to rozpisać dla małych liczb (jak wyżej), jednak dla większych już się gubię.
Ile różnych słów?
-
zati61
- Użytkownik
- Posty: 656
- Rejestracja: 11 gru 2009, o 16:54
- Płeć: Mężczyzna
- Lokalizacja: aaa
- Pomógł: 119 razy
Ile różnych słów?
wystarczy ze jedno zrozumiemy(bedziemy wiedziec jak obliczyc i koniec)
twój przykład:
niestety troche pogubiłeś wyrazów:
na kazdej pozycji slowa mamy 2 mozliwosci:(A;B), wiec słów jest;
2*2*2*2=16, musismy odjac 2(AAAA:BBBB)- odejmujemy tyle ile jest roznych liter(wazne).
Wiec 16-2=14. Ogólnie na literkach: L*N-N, czyli N(L-1) różnych rodzajow(wzgledem literek)słów.
Teraz ostatnia rzecz nasz \(\displaystyle{ 10^9}\)
Z S literek wybieramy N. Wybieramy po kolei, czyli:
\(\displaystyle{ S*(S-1)*...(S-(N-1))}\), to sa wszystkie mozliwe slowa w 1 rodzaju
Ostatecznie wystarczy wymnozyc liczbe slow przez ich rodzaje, czyli:
\(\displaystyle{ N(L-1) \cdot S \cdot (S-1) \cdot ... \cdot (S-(N-1))=}\)
Jestesmy blisko, ale cos tu chyba zle mam(tak mi sie wydaje), późno jutro popołudniu/wieczorem pomyślimy
twój przykład:
niestety troche pogubiłeś wyrazów:
na kazdej pozycji slowa mamy 2 mozliwosci:(A;B), wiec słów jest;
2*2*2*2=16, musismy odjac 2(AAAA:BBBB)- odejmujemy tyle ile jest roznych liter(wazne).
Wiec 16-2=14. Ogólnie na literkach: L*N-N, czyli N(L-1) różnych rodzajow(wzgledem literek)słów.
Teraz ostatnia rzecz nasz \(\displaystyle{ 10^9}\)
Z S literek wybieramy N. Wybieramy po kolei, czyli:
\(\displaystyle{ S*(S-1)*...(S-(N-1))}\), to sa wszystkie mozliwe slowa w 1 rodzaju
Ostatecznie wystarczy wymnozyc liczbe slow przez ich rodzaje, czyli:
\(\displaystyle{ N(L-1) \cdot S \cdot (S-1) \cdot ... \cdot (S-(N-1))=}\)
Jestesmy blisko, ale cos tu chyba zle mam(tak mi sie wydaje), późno jutro popołudniu/wieczorem pomyślimy
Ile różnych słów?
W nocy siedziałem trochę nad tym i doszedłem do takiego wzoru:
\(\displaystyle{ \prod_{j=0}^{N-1} (S - j)}\)
Jednak przed iloczynem trzeba wstawić czynnik, który będzie wyznaczał ilość unikalnych wyrazów. I tutaj mam problem.
Dla przykładu dla \(\displaystyle{ N = 1}\) i \(\displaystyle{ L = 3}\) mamy tylko jeden unikalny wyraz, AAA.
Dla \(\displaystyle{ N = 2}\) i \(\displaystyle{ L = 3}\) mamy 3 unikalne wyrazy: AAB, ABA, BAA.
Liczbę unikalnych wyrazów mnożymy potem przez iloczyn wyżej zapisany. Jednak jak ją wyznaczyć? Na pewno zależy to od długości wyrazu \(\displaystyle{ L}\) oraz ilości różnych liter \(\displaystyle{ N}\).
\(\displaystyle{ \prod_{j=0}^{N-1} (S - j)}\)
Jednak przed iloczynem trzeba wstawić czynnik, który będzie wyznaczał ilość unikalnych wyrazów. I tutaj mam problem.
Dla przykładu dla \(\displaystyle{ N = 1}\) i \(\displaystyle{ L = 3}\) mamy tylko jeden unikalny wyraz, AAA.
Dla \(\displaystyle{ N = 2}\) i \(\displaystyle{ L = 3}\) mamy 3 unikalne wyrazy: AAB, ABA, BAA.
Liczbę unikalnych wyrazów mnożymy potem przez iloczyn wyżej zapisany. Jednak jak ją wyznaczyć? Na pewno zależy to od długości wyrazu \(\displaystyle{ L}\) oraz ilości różnych liter \(\displaystyle{ N}\).
-
zati61
- Użytkownik
- Posty: 656
- Rejestracja: 11 gru 2009, o 16:54
- Płeć: Mężczyzna
- Lokalizacja: aaa
- Pomógł: 119 razy
Ile różnych słów?
nevermoon, napisałem wszystko we wcześniejszym poście.
1. liczba słów jednego rodzaju
TU się zgadzamy nasze postacie są równoważne:
\(\displaystyle{ S \cdot (S-1) \cdot ... \cdot (S-(N-1))= \prod_{i=0}^{N-1} (S - i)}\)
2. liczba rodzajów(typów) słów,
Tak jak napisałem:
Nasze słowo: \(\displaystyle{ \underbrace{xx \ldots x}_{L}}\)
w miejsce każdej literki('x') możemy wstawić N możliwych liter, a więc mamy razem:
\(\displaystyle{ \underbrace{NN \ldots N}_{L}=NL}\) możliwości, w poprzednim poście napisałem, że trzeba odjąc słowa AAAA;BBBB; itp ale jednak nie trzeba, bo w zadaniu jest mowa o dowolnych slowach tworzonych z tych liter(a wiec moga byc tez slowa stworzone o dlugosci L z 1 litery- AAAA)
Podsumowując: rodzajów mamy: \(\displaystyle{ NL}\), a słów jegnego rodzaju(typu) mamy: \(\displaystyle{ \prod_{i=0}^{N-1} (S - i)}\)
Więc słów ogółem jest: \(\displaystyle{ NL \cdot \prod_{i=0}^{N-1} (S - i)}\)
1. liczba słów jednego rodzaju
TU się zgadzamy nasze postacie są równoważne:
\(\displaystyle{ S \cdot (S-1) \cdot ... \cdot (S-(N-1))= \prod_{i=0}^{N-1} (S - i)}\)
2. liczba rodzajów(typów) słów,
Tak jak napisałem:
Nasze słowo: \(\displaystyle{ \underbrace{xx \ldots x}_{L}}\)
w miejsce każdej literki('x') możemy wstawić N możliwych liter, a więc mamy razem:
\(\displaystyle{ \underbrace{NN \ldots N}_{L}=NL}\) możliwości, w poprzednim poście napisałem, że trzeba odjąc słowa AAAA;BBBB; itp ale jednak nie trzeba, bo w zadaniu jest mowa o dowolnych slowach tworzonych z tych liter(a wiec moga byc tez slowa stworzone o dlugosci L z 1 litery- AAAA)
Podsumowując: rodzajów mamy: \(\displaystyle{ NL}\), a słów jegnego rodzaju(typu) mamy: \(\displaystyle{ \prod_{i=0}^{N-1} (S - i)}\)
Więc słów ogółem jest: \(\displaystyle{ NL \cdot \prod_{i=0}^{N-1} (S - i)}\)