Alfabet i liczba słów
-
- Użytkownik
- Posty: 281
- Rejestracja: 2 wrz 2009, o 21:10
- Płeć: Mężczyzna
- Podziękował: 9 razy
- Pomógł: 2 razy
Alfabet i liczba słów
Niech \(\displaystyle{ \sum =\{a_1,..., a_n\}}\) będzie n-literowym alfabetem i niech \(\displaystyle{ n \ge 1}\). Ile jest wszystkich słów \(\displaystyle{ S_m =l_1, l_2,..., l_m}\) o długości \(\displaystyle{ m \le n}\) o literach z \(\displaystyle{ \sum}\)?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Alfabet i liczba słów
Jest ich \(\displaystyle{ \sum_{m=0}^nn^m=\frac{n^{n+1}-1}{n-1}}\), bo słów długości \(\displaystyle{ m}\) jest \(\displaystyle{ n^m}\). Oczywiście wliczyłem też słowo puste (zeroliterowe).
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Alfabet i liczba słów
To jest suma ciągu geometrycznego, więc można skorzystać ze wzoru. Ja tego wzoru nie pamiętam, więc mnożę i dzielę przez \(\displaystyle{ n-1}\) i tak to właśnie wychodzi.