Für die reine Berechnung der Anzahl:
Man kann das Ganze auch als ein kombinatorisches Problem auffassen: Für k Zweier-Schritte, gibt es genau (n - 2*k + k) über k Möglichkeiten, diese anzuordnen. Dies summiert man dann für 0..n / 2 auf und man hat die Anzahl der Möglichkeiten:
(In Haskell: )
Code:
fac 0 = 1
fac n = product [1..n]
n `binom` k = fac n `quot` (fac k * fac (n-k))
treppe :: Integer -> Integer
treppe n = sum [(n - 2*k + k) `binom` k | k <- [0..n `quot` 2]]
Dabei sieht man auch, dass es, wie oben erwähnt, sich um die Folge der Fibonacci-Zahlen handelt, daher als Einzeiler/Zweizeiler(mit Absicht unverständlich):
Code:
import Control.Monad.Fix
treppe n = fix ((1:) . scanl (+) 1) !! n