Partition Diagrams

The similarity between adding partitions to set partitions and adding items to partitions of set partitions leads to the idea of recursively or hierarchically partitioning a set. Schroeder diagrams will be used to represent the process of recursive partitioning. The combinatoric structure associated with the problem of recursive partitioning is the combinatoric structure known as Schroeder's Fourth Problem or hierarchies.
A new rule needs to be added for recursive partitioning, stating that internal nodes must have two or more child nodes. The absence of this rule would allow an internal node with one child node to be recursively partitioned indefinitely, creating an infinite number of trees. A new type of diagram is introduced, the Schroeder diagram. The hexagon Bell number diagram in Figure 2 has two partitions of three items each, but a group of three items may be further partitioned in four ways. A tree structure of Bell number diagrams allows recursive partitioning to be displayed in a less visually confusing manner that displaying it with a standard tree graph.
A Schroeder diagram represents the process of recursive partitioning in the form of a tree with Bell number diagrams for nodes. Bell number diagrams containing only one partition are forbidden, as in Figure 1. The absence of this rule would allow an internal node with one child node to be recursively partitioned indefinitely, creating an infinite number of trees. Later it will be shown that these diagrams are forbidden because they are left hand values. Figure 1 represent the third, fourth, and fifth derivatives of a recursive function.

Figure 1 - Examples of Bell Number Diagrams Forbidden in Schroeder Diagrams

Partitions with 1 or 2 items are not displayed as their own separate Bell number diagram since no additional information would be forthcoming; a single item can't be sub-partitioned, and two items can only be recursively partitioned in one way due to the prohibition against placing all items in a single partition. All Bell number diagram partitions of 3 or more items have a second representation as child node Bell number diagram containing the same number of items as the original partition. Child nodes are sorted from left to right in chronological order; a child node containing the first label would be to the left of the other child nodes. Items and partitions are commingled in Schroeder diagrams rather that have partitions with only one item. A "naked" single item replaces partitions containing a single item.

Figure 2 - The Schroeder diagram and tree graph of {{{1, 5}, 3}, {{2, 4}, 6}}

Items	1	2	3	4	5	6	7	8	9	10
Partition Function	1	2	3	5	7	11	15	22	30	42
Set Partitions	1	2	5	15	52	203	877	4140	21147	115975
Unlabeled Hierarchies	1	1	2	5	12	33	90	261	766	2312
Hierarchies	1	1	4	26	236	2752	39208	660032	12818912	282137824

Table 1 - Several Combinatoric Structures from the On-Line Encyclopedia of Integer Sequences

Diagrams of unlabeled combinatoric structures are placed in a circle to indicate that they serve as a grouping of their labeled versions. The unlabeled structures then can be used to index the labeled structures. Fa`a di Bruno's Formula uses the enumeration of the integer partitions to form the index for the summation that gives the different derivatives of composite functions. The Ferrers diagrams below visually enumerate the integer partitions of the number four.

Figure 3 - The Ferrers diagrams of the number four

Figure 4 - Unlabeled Bell Number Diagrams

Enumerates integer partitions; a radial Ferrers diagram. This serves as a building block for the next type of diagram.

Figure 5 - Unlabeled Schroeder Diagrams

Enumerates unlabeled hierarchies and serves as an index for labeled hierarchies.

Bell Number Diagrams

Unlabeled Bell Number Diagrams

Enumerates integer partitions, a radial Ferrers diagram.

Unlabeled Schroeder Diagrams

Enumerates unlabeled hierarchies

Schroeder Diagrams

The entries after hier(2) are grouped together with other structures identical except for their labeling and preceded by the unlabeled diagram serving to index the entire group.