Ein Anfang wäre mal folgender Ansatz:

(1) Wie viele Wörter der Länge \(n-1\) gibt es, in denen das Zeichen c genau \(r-1\) mal vorkommt, das Zeichen a \(s\) mal und b \(t\) mal? (Da es an der letzten Stelle keine Auswahl gibt, habe ich das Wort um diese eine Stelle verkürzt.)

(2) Addiere alle diese Ausdrücke, so dass \(s \ge 0\) und \(t \ge 0\).

Die Lösung zu (1) ist

\[ \binom{n-1}{r-1} \binom{n-r}{s} \,,\]

wobei \(n\) und \(r\) fest stehen. Nur \(s\) kann variieren, und zwar im Bereich \(0 \le s \le n-r\).

Das ergibt dann

\[ S = \binom{n-1}{r-1} \sum_{s=0}^{n-r} \binom{n-r}{s} = \binom{n-1}{r-1} \, 2^{n-r} \,.\]

An der Lösung kann man erkennen, dass eine andere Überlegung noch direkter zum Ziel führt:

(1) Auf wie viele Weisen kann man die \(r\) Zeichen c in dem Wort verteilen? \( \implies \binom{n-1}{r-1} \)

(2) Auf die anderen Stellen kann man wahlweise a oder b setzen. \( \implies 2^{n-r} \)

PS: Hier zählen wir auch solche Wörter, die gar kein a oder gar kein b enthalten. Das wird aber in der Aufgabenstellung nicht gefordert.