What are efficient ways to compute the derivatives of iterated functions? The derivatives of iterated functions at a fixed point $z_0$ are useful in constructing a Taylors series of iterated analytic functions - in other words, the Taylors series of a dynamical system $f^t(z_0)$. 

A simpler version of the problem casts light on possible approaches. Instead of iterated functions, consider composite functions and Faà di Bruno's formula The combinatorial structure integer partitions serves as the index to the summations in Faà di Bruno's formula. So the first step of evaluation is to enumerate all integer partitions of a given order.  

While combinatorial structure integer partitions are associated with the derivatives of composite functions, the unlabeled version of the labeled combinatorial structure total partitions are associated with iterated functions. See Partition Diagrams for more information on the different relevant combinatorial structures. The following Mathematica code does what I need, but the cost of simplicity is that it first enumerates the labeled total partitions to compute the unlabeled total partitions. So for $n=10$, $D^{10}f^t(z_0)$, there are 282,137,824 labeled total partitions, while there are only 2,312 unlabeled partitions. 

Combinatorial Examples

a(4)=5 unlabeled total partitions: (oooo),(oo(oo)),(o(ooo)),(o(o(oo))),((oo)(oo)).

b(4)=26 labeled total partitions: ((1,4),2,3), (1,(2,4),3), (1,2,(3,4)), (((1,4),2),3), ((1,(2,4)),3), ((1,2),(3,4)), (((1,4),3),2), ((1,(3,4)),2), ((1,3),(2,4)), ((1,4),(2,3)), (1,((2,4),3)), (1,(2,(3,4))), (1,2,3,4), ((1,2,4),3), ((1,2),3,4), ((1,3,4),2), ((1,3),2,4), (1,(2,3,4)), (1,(2,3),4), ((1,2,3),4), (((1,2),4),3), (((1,2),3),4), (((1,3),4),2), (((1,3),2),4), (1,((2,3),4)), ((1,(2,3)),4)

b(4) = 12 (o(o(oo))) + 3 ((oo)(oo)) + 6 ((oo(oo)) + 4 (o(ooo)) + (oooo) = 26

I would like to have an efficient way to reproduce the preceding results.

Mathematica code

TotalPartitions[0] = {{}};
TotalPartitions[1] = {{1}};
TotalPartitions[2] = {{1, 2}};
Match[l_List, pattern_] := Extract[l, Position[l, pattern]];
TP1[l_List, next_Integer] := 
  Map[( l /. # -&gt; {#, next}) &amp;, Match[l, _Integer] ];
TP2[l_List, next_Integer] := 
  Map[( l /. # -&gt; Append[#, next]) &amp;, Match[l, _List] ];
TP3[l_List, next_Integer] := 
  Map[( l /. # -&gt; {#, next}) &amp;, Match[l, _List] ];
TotalPartitions[n_Integer] := 
  TotalPartitions[n] = 
   Flatten[ {Map[(TP1[#, n] ) &amp;, TotalPartitions[n - 1]], 
     Map[(TP2[#, n] ) &amp;, TotalPartitions[n - 1]], 
     Map[(TP3[#, n] ) &amp;, TotalPartitions[n - 1]]}, 2];

u = TotalPartitions[4] /. _Integer -&gt; 1
&gt; {{{{1, 1}, 1}, 1}, {{1, {1, 1}}, 1}, 
&gt;  {{1, 1}, {1, 1}}, {{1, 1}, {1, 1}}, 
&gt;  {1, {{1, 1}, 1}}, {1, {1, {1, 1}}}, 
&gt;  {{1, 1}, 1, 1}, {1, {1, 1}, 1}, 
&gt;  {1, 1, {1, 1}}, {{{1, 1}, 1}, 1}, 
&gt;  {{1, {1, 1}}, 1}, {{1, 1}, {1, 1}}, 
&gt;  {{1, 1, 1}, 1}, {{1, 1}, 1, 1}, 
&gt;  {1, {1, 1, 1}}, {1, {1, 1}, 1}, 
&gt;  {1, 1, 1, 1}, {{1, 1, 1}, 1}, 
&gt;  {{1, 1}, 1, 1}, {{{1, 1}, 1}, 1}, 
&gt;  {{{1, 1}, 1}, 1}, {1, {{1, 1}, 1}}, 
&gt;  {{1, {1, 1}}, 1}, {{1, 1, 1}, 1}, 
&gt;  {{{1, 1}, 1}, 1}, {{{1, 1}, 1}, 1}}

SetAttributes[Z, Orderless];
Tally[Apply[List, Apply[Z, u, Infinity], Infinity]]
&gt;  {{{1, {1, {1, 1}}}, 12}, {{{1, 1}, {1, 1}}, 3}, {{1, 1, {1, 1}}, 6}, 
&gt;   {{1, {1, 1, 1}}, 4}, {{1, 1, 1, 1}, 1}}


Note that the Tally function displays the number of occurrences of labeled total partitions for each unlabeled total partition, so that $12+3+6+4+1=26$ shows how the 5 unlabeled total partitions of order 4 map to the 26 labeled total partitions. I've tried pure analytic approaches, combinatorial approaches and a hybrid of the two in my Mathematica programs Schroeder Summations and Iterate. I believe this is a useful problem in dynamics and combinatorics and merits an efficient answer.
An unordered hierarchical partition of $n \geq 2$ is composed out of two ingredients:


A non-trivial partition $n_1,\ldots,n_k \vdash n$, where $n_1 \leq \cdots \leq n_k$ and $k &gt; 1$.
For each $n_i$, an unordered hierarchical partition of $n_i$. Furthermore, if $n_i = n_{i+1}$ then in some fixed order of hierarchical partitions of $n_i$, the one chosen for $n_i$ must precede or equal the one chosen for $n_{i+1}$.


In the base case $n = 1$ there is a single unordered hierarchical partition.

This gives the following algorithm for generating all unordered hierarchical partitions. We generate a list $P^{(n)}_1,\ldots,P^{(n)}_{q(i)}$ of all $q(n)$ unordered hierarchical partitions of $n$. For $n = 1$, the list consists of the single trivial partition. In order to generate the list for $n$:


Go over all non-trivial partitions $n_1,\ldots,n_k \vdash n$. We can write this partition more succinctly as $1^{m_1},\ldots,(n-1)^{m_{n-1}}$, where $m_i$ is the multiplicity of $i$.
For each $i \in \{1,\ldots,n-1\}$, make a list of all non-decreasing sequences of length $m_i$ consisting of numbers in $\{1,\ldots,q(i)\}$; there are $\binom{q(i)+m_i-1}{q(i)}$ of these.
Each choice of one sequence for each $i$ from the corresponding list corresponds to one unordered hierarchical partition of $n$.