Wie viele Lösungsmöglichkeiten gibt es für einen Zerlegungsbaum mit der gleichen Startzahl?

Question

Aufgabe:

Wie viele Lösungsmöglichkeiten gibt es für einen Zerlegungsbaum mit der gleichen Startzahl?

Problem/Ansatz:

Ich analysiere die fachwissenschaftlichen Hintergründe von Zerlegungsbäumen wie diesen: https://pikas.dzlm.de/pikasfiles/uploads/upload/Material/Haus_2_-_Kontinuitaet_von_Klasse_1_bis_6/UM/Zerlegungsbaeume/Kurzinfo_Zerlegungsbaeume.pdf
Jetzt stellt sich mir die Frage, wie ich eine allgemeine Formel finden kann um die Anzahl der verschiedenen Zerlegungsbäume einer Startzahl zu berechnen.

Der Zerlegungsbaum von 6 hat zum Beispiel zwei unterschiedliche Zerlegungsbäume, der von 12 zum Beispiel 6.

Vielleicht kann mir da jemand weiterhelfen, würde mich freuen :) danke schon mal!

Comments

Der Zerlegungsbaum von 6 hat zum Beispiel zwei unterschiedliche Zerlegungsbäume

Welche 2 Bäume sind das? 2*3 und 3*2

Ist das dank des Kommutativgesetzes nicht ein Baum?

der von 12 zum Beispiel 6.

Welche 6 Bäume wären das genau?

---

12 = 2 * 6 = 2 * (2 * 3)

12 = 3 * 4 = 3 * (2 * 2)

Ich würde das als 2 Zerlegungsbäume werten.

---

Ok. Ich habe nachgelesen und unnötigerweise steht in dem pdf drin, dass über das Kommutativgesetz mehrere Bäume entstehen, die ein anderes Aussehen haben.

Es interessiert wohl nicht, dass diese Bäume nur spiegelverkehrt sind und daher nicht wirklich anders aussehen.

---

Ich habe ein rekursives Programm geschrieben welches ein Produkt soweit es keine Primzahl ist in zwei Faktoren aufteilt und dann rekursiv schaut wie viele Zerlegungen es dann jeweis gibt.

Für 12 ergibt sich

12 = 2 * 6 = 2 * (2 * 3)
12 = 2 * 6 = 2 * (3 * 2)
12 = 3 * 4 = 3 * (2 * 2)
12 = 4 * 3 = (2 * 2) * 3
12 = 6 * 2 = (2 * 3) * 2
12 = 6 * 2 = (3 * 2) * 2

6 Zerlegungsbäume

Ich habe aber keinen Plan, ob es dafür eine Formel gibt. Bereits die Teileranzahlfunktion ist ja nicht so trivial. Real zerlegt man dazu die Zahl erstmal in Potenzen von Primfaktoren.

Das erscheint mir Formeltechnisch nur mit extrem großen Aufwand nachzubauen.

Meine Rekursion hat aber auch extrem große Schwächen. Da in der Rekursion z.B. immer wieder die Teiler einer Zahl berechnet werden. Es wäre vermutlich günstiger einmal eine Primfaktorzerlegung zu machen. Aber mit der Rekursivität ist das Programm im Umfang recht klein.

---

Ich würde zu allen natürlichen Zahlen unterhalb einer Grenze jeweils die Anzahl der Zerlegungsbäume mit der Mächtigkeit der Teilermenge vergleichen und nach einem Muster in diesem Vergleich suchen.