Wenn ich die Aufgabenstellung richtig interpretiere, zählt auch eine einzelne Zahl als strikt aufsteigende Zahlenreihe?
Du würdest dann erhalten
Aus {1,2}: 1, 2, 12 -->3 Möglichkeiten
Aus {1,2,3} : 1 , 2, 3, 12, 13, 23, 123 -->7 Möglichkeiten
Aus {1,2,3,4}: 1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134, 234, 1234 --> 15 Möglichkeiten.
Das ist jeweils 1 weniger als eine Zweierpotenz und lässt sich auch begründen:
1) Eine n-elementige Menge hat 2^n Teilmengen, die habe ich alle (mit Ausnahme der leeren Menge), angegeben.
2) Die Anzahlen lassen sich rekursiv herleiten.
Die aufsteigenden Folgen aus der Menge der Zahlen von 1 bis n+1 kann man aus den Folgen innerhalb der Zahlen 1 bis n erzeugen, indem man
- an alle bestehenden Folgen die Zahl n+1 anhängt
- in allen bestehenden Folgen das letzte Element durch n+1 ersetzt.
Mit deinen beiden Möglichkeiten verdoppelt sich schon mal die bisherige Anzahl, wenn man ein neues Element hinzunimmt. Außerdem kommt noch ein neues Element dazu: die Einzelzahl n+1.
Damit gilt für die Anzahlen: A(n+1)=1+2*A(n), wobei der Startwert A(1)=1 ist.
