Knoten im Domino-Baum

Question

Angenommen, Sie haben ein Doppel-N-Domino. Nimm ein Stück und wähle eine seiner Seiten. Zeichnen Sie mit dieser Seite als Wurzel den Baum mit allen möglichen Kombinationen von Teilen, die diese Seite teilen. Die Stücke mit dem gleichen Wert auf jeder Seite zählen als nur ein Teilbaum. Sehen Sie dieses Tree für ein Beispiel des Baums mit einem doppelten 2 Domino, mit [0,1] als Wurzel und 0 als die gewählte Seite.

Dieser Baum enthält 14 Knoten. Jetzt wiederhole jedes Stück als Wurzel und jede Seite als gewählte Seite.

Die Frage ist, was ist die maximale Anzahl der Knoten in diesen Bäumen? Ich habe ein Programm erstellt und ich habe einige Informationen.

Double N   Maximum Nodes in some tree 
     0       1 
     1       3 
     2       21 
     3       487 
     4       147753 
     5       133720011 

Ich weiß nicht, ob es Formel ist, Algorithmus, Pseudo-Code, Dynamische Programmierung dieses Problem zu lösen, aber jede Hilfe ist willkommen.

EDIT: Es ist nicht schwer zu sehen, dass alle Stücke mit dem gleichen Wert auf beiden Seiten einen Baum mit der gleichen Anzahl von Knoten induziert, und das gleiche gilt für alle Stücke mit unterschiedlichen Wert, Permutationen. Sie müssen also nur die Anzahl der Knoten im Baum mit dem [0 0] Stück als root überprüfen.

Answer 1

Ihre Frage bezieht sich auf das Zählen von Pfaden in einem vollständigen Diagramm, die nicht zweimal dieselbe Kante verwenden. Sie können einen vollständigen Graphen auf den Vertices 0 bis N betrachten, und jeder Domino kann als eine Kante zwischen den Zahlen betrachtet werden. Beachten Sie, dass Sie auch eine Kante von jedem Stützpunkt zu sich selbst einschließen.

Ein verwandtes und wahrscheinlich einfacheres Problem ist das Zählen von Eulerschen Pfaden, d.h. Verwenden jedes einzelnen Dominos. Es scheint keine vollständig geschlossene Form zu geben, selbst dafür gibt es hier ein Papier, das es analysiert und einige Berechnungen anstellt: http://users.cecs.anu.edu.au/~bdm/papers/euler.pdf.