1
$\begingroup$

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 /. # -> {#, next}) &, Match[l, _Integer] ];
TP2[l_List, next_Integer] := 
  Map[( l /. # -> Append[#, next]) &, Match[l, _List] ];
TP3[l_List, next_Integer] := 
  Map[( l /. # -> {#, next}) &, Match[l, _List] ];
TotalPartitions[n_Integer] := 
  TotalPartitions[n] = 
   Flatten[ {Map[(TP1[#, n] ) &, TotalPartitions[n - 1]], 
     Map[(TP2[#, n] ) &, TotalPartitions[n - 1]], 
     Map[(TP3[#, n] ) &, TotalPartitions[n - 1]]}, 2];

u = TotalPartitions[4] /. _Integer -> 1
> {{{{1, 1}, 1}, 1}, {{1, {1, 1}}, 1}, 
>  {{1, 1}, {1, 1}}, {{1, 1}, {1, 1}}, 
>  {1, {{1, 1}, 1}}, {1, {1, {1, 1}}}, 
>  {{1, 1}, 1, 1}, {1, {1, 1}, 1}, 
>  {1, 1, {1, 1}}, {{{1, 1}, 1}, 1}, 
>  {{1, {1, 1}}, 1}, {{1, 1}, {1, 1}}, 
>  {{1, 1, 1}, 1}, {{1, 1}, 1, 1}, 
>  {1, {1, 1, 1}}, {1, {1, 1}, 1}, 
>  {1, 1, 1, 1}, {{1, 1, 1}, 1}, 
>  {{1, 1}, 1, 1}, {{{1, 1}, 1}, 1}, 
>  {{{1, 1}, 1}, 1}, {1, {{1, 1}, 1}}, 
>  {{1, {1, 1}}, 1}, {{1, 1, 1}, 1}, 
>  {{{1, 1}, 1}, 1}, {{{1, 1}, 1}, 1}}

SetAttributes[Z, Orderless];
Tally[Apply[List, Apply[Z, u, Infinity], Infinity]]
>  {{{1, {1, {1, 1}}}, 12}, {{{1, 1}, {1, 1}}, 3}, {{1, 1, {1, 1}}, 6}, 
>   {{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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I suggest you add a clear and succinct description of the object you're trying to enumerate to the body of the question. $\endgroup$
    – Yuval Filmus
    Commented Mar 26, 2014 at 14:30
  • $\begingroup$ This sounds like a question for Computational Science. $\endgroup$
    – David Richerby
    Commented Mar 26, 2014 at 17:04
  • $\begingroup$ @DavidRicherby Disagree. This is combinatorial enumeration. $\endgroup$
    – Yuval Filmus
    Commented Mar 26, 2014 at 19:41
  • $\begingroup$ @Daniel I still cannot quite understand what a hierarchical partition is. Can you give a definition? $\endgroup$
    – Yuval Filmus
    Commented Mar 26, 2014 at 19:42
  • $\begingroup$ @YuvalFilmus A "hierarchical" partition or total partition as per Stanley's Enumerative Combinatorics, Vol 2, pg 13, is the number of ways n objects can be parenthesized. It is a recursive application of set partitioning. $\endgroup$
    – Daniel Geisler
    Commented Mar 26, 2014 at 19:55

2 Answers 2

Reset to default
1
$\begingroup$

An unordered hierarchical partition of $n \geq 2$ is composed out of two ingredients:

  1. A non-trivial partition $n_1,\ldots,n_k \vdash n$, where $n_1 \leq \cdots \leq n_k$ and $k > 1$.

  2. 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$:

  1. 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$.
  2. 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.
  3. Each choice of one sequence for each $i$ from the corresponding list corresponds to one unordered hierarchical partition of $n$.
Improve this answer
$\endgroup$
6
  • $\begingroup$ This is great, I have walked through it several times and see no problems. I'm going to attempt to implement this in Mathematica to verify that this works as intended. $\endgroup$
    – Daniel Geisler
    Commented Mar 27, 2014 at 0:32
  • $\begingroup$ The reference to a hierarchical partition of $n_i$ in the first point 2. should be an unordered hierarchical partition, shouldn't it? Unordered hierarchical partitions are enumerated by decomposing them into smaller unordered hierarchical partitions. Correct? $\endgroup$
    – Daniel Geisler
    Commented Mar 27, 2014 at 0:42
  • $\begingroup$ While I requested an efficient method of computing the derivatives of iterated functions, I also indicated that an effective algorithm for enumerating unordered hierarchical partitions, OEIS A000669, would be considered a solution. $\endgroup$
    – Daniel Geisler
    Commented Mar 27, 2014 at 21:39
  • 1
    $\begingroup$ This is "selection with replacement". Perhaps the easiest way to approach this is via the standard bijection showing that the number of ways to choose $k$ out of $n$ with replacement is $\binom{n+k-1}{k}$. See the Wikipedia article: en.wikipedia.org/wiki/…. $\endgroup$
    – Yuval Filmus
    Commented Mar 31, 2014 at 1:59
  • 1
    $\begingroup$ Another approach would be to run a recursive procedure that accepts a "minimum" (originally 1), a "total" ($n$) and a "number" (originally $k$). If you pick $x$, you update the "minimum" to $x$, and in any case you decrease "number" by 1. $\endgroup$
    – Yuval Filmus
    Commented Mar 31, 2014 at 3:39
0
$\begingroup$

@YuvalFilmus has provided an algorithm that I believe answers the question of how to enumerate the ordered hierarchical partitions in terms of unordered hierarchical partitions. Ideally this would be a comment to his answer, but it is too lengthy. I am trying to write Yuval's algorithm in Mathematica as a precursor to coding an efficient way to compute the derivatives of iterated functions. The following Mathematica code comes close to correctly enumerating the unordered hierarchical partitions.

<< Combinatorica`
o[1] = {1};
o[n_ /; n > 1] :=
 Apply[Sequence,
  Map[Tuples, Rest[Partitions[n]] /. m_Integer -> o[m]], 1];
Table[Length[o[i]], {i, 6}]
> {1, 1, 2, 5, 12, 34}

The value o[6] should be 33, not 34. This is because the Tuple command is used and produces both {{{1,1},1},{1,1,1}} and {{1,1,1},{{1,1},1}} which are the same when unordered.

o[3]={{1, 1, 1}, {{1, 1}, 1}}

This is where step 2. of Yuval's algorithm comes into play. The following are legitimate values for non-decreasing sequences

{o[3][[1]],o[3][[1]]}
> {{{1,1},1},{{1,1},1}}
{o[3][[1]],o[3][[2]]}
> {{{1,1},1},{1,1,1}}
{o[3][[2]],o[3][[2]]}
> {{1,1,1},{1,1,1}}

while the following with indices 2, 1 is an invalid decreasing sequence

{o[3][[2]],o[3][[1]]}
> {{1,1,1},{{1,1},1}}

The Tuple command therefore needs to be replaced with a version where no tuple is in non-descending order.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.