Wir wissen, dass es Nk Wörter der Länge k gibt. Alles, was wir tun müssen, ist, die Beiträge aller k zwischen 0 und n zusammenzusummieren, ∑ k=0nNk. Summen dieses Typs lassen sich mit einem Trick berechnen, der so aussieht:

∑n ∑n n∑- 1 N k = N N k- 1 = N N k k=0 k(=0 k= - 1) 1 ∑n k n ∑n k n+1 = N --+ N - N = 1 + N N - N N k=0 k=0

Diese Gleichung kann man jetzt nach der Summe auflösen und kommt auf

∑n 1 - N n+1 = ----------. k=0 1 - N

Mithin hat die Sternmenge einer N-elementigen Menge (1 -Nn+1)∕(1 -N) Elemente, die kürzer als n sind.

Prüft diese Formel mit eurem Ergebnis von oben. Beachtet, dass dies eine stark wachsende Funktion ist. In der Aufgabe oben (N= 3) wärt ihr, selbst wenn ihr ein Wort pro Sekunde schreiben könntet, über 24 Stunden beschäftigt gewesen, hättet ihr die Wörter bis zur Länge 11 schreiben wollen (das sind nämlich 88573 Stück), wolltet ihr bis Länge 16 kommen, wärt ihr fast ein Jahr beschäftigt gewesen, bis ihr die 21523360 Wörter hingeschrieben hättet.

Hat man ein Alphabet von 26 Zeichen, wird das alles noch viel schlimmer – hier gibts schon bei 321272407 Wörter bis zur Länge 7, für die ihr dann wohl gegen zehn Jahre brauchen würdet.

In diesen rapide wachsenden Zahlen liegt dann auch der Grund, warum Passwörter, die einfach aus Zeichen zusammengewürfelt werden, relativ sicher sind.