Alfabet i liczba słów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
choko
Użytkownik
Użytkownik
Posty: 279
Rejestracja: 2 wrz 2009, o 21:10
Płeć: Mężczyzna

Alfabet i liczba słów

Post autor: choko » 13 mar 2011, o 17:13

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}\)?

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E

Alfabet i liczba słów

Post autor: norwimaj » 13 mar 2011, o 18:12

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).

choko
Użytkownik
Użytkownik
Posty: 279
Rejestracja: 2 wrz 2009, o 21:10
Płeć: Mężczyzna

Alfabet i liczba słów

Post autor: choko » 13 mar 2011, o 19:26

Jest ich \(\displaystyle{ \sum_{m=0}^nn^m=\frac{n^{n+1}-1}{n-1}}\)
Ok tylko jak obliczyłeś tą sumkę?

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E

Alfabet i liczba słów

Post autor: norwimaj » 13 mar 2011, o 20:40

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.

ODPOWIEDZ