Thema #Kombinatorik. Frage: Auf wie viele unterschiedliche Weisen lässt sich n als #Summe von nat. #ahlen <n darstellen, wenn bloße #Kommutationen nicht als unterschiedliche Darstellungen gelten?

Also z. B. 3 ist ja 1+1+1 oder 1+2 oder 2+1 oder 3, aber zwei davon sind kommutativ. So geht jede Zahl 2^(n-1) mal, aber wenn man 1+2 und 2+1 als nur eine Lösung rechnet? Die Anzahl Möglichkeiten steigt auch konstant, aber ich habe noch keine Gesetzmäßigkeit gefunden. Jemand ne Idee?

#Mathe

@schreibmax Klingt auf den ersten Blick wie eine Anwendung für In- und Exklusion:

  • Ich zähle alle Darstellungen.
  • Dann rechne ich aus, was ich doppelt gezählt habe und ziehe das von meiner ersten Summe ab. Auch hier zähle ich "zu viel", ziehe entsprechend zu viel ab.
  • Nun rechne ich auch, was ich in 2. zu viel abgezogen habe, addiere es wieder dazu...
  • Und so weiter. Letztendlich ein endlich langes f0(n) - f1(n) + f2(n) - f3(n) ...

    @wakame So ungefähr. Würde vermuten, dass jemand sich schon mal damit befasst hat, aber das Netz hilft bisher nicht wirklich weiter.

    @schreibmax
    Beschäftigt definitiv. Das Problem ist NP-schwer (und damit vermutlich nicht in polynomieller Zeit berechenbar):

    https://de.wikipedia.org/wiki/Partitionierungsproblem

    Partitionierungsproblem – Wikipedia

    @wakame @schreibmax NP-schwer, but can nevertheless be calculated very rapidly inside a sufficiently large array: stackoverflow.com/questions/14…
    Integer Partition (algorithm and recursion)

    Finding how many combinations of a sum number (the variable n in code). For ex.: 3 = 1+1+1 = 2+1 = 3 => ANS is 3 5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 => ANS is 7 In the

    Stack Overflow

    @wakame Ha! Es gibt also immerhin einen Namen dafür und auch einiges an mathematischer Geschichte. Hätte mich auch gewundert. Vielen lieben Dank für den Hinweis!

    Ist doch immer erfrischend, auf was für Gedanken man an einem harmlosen Vormittag kommt.