0
$\begingroup$

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities).

However, I'm not interested in sampling one object of some size out of a set of possible ones, I just want to enumerate (create) all of them.

For example, this answer illustrates a nice construction of binary trees.

I've tried playing with trees and thought up of some nice constraints for which new generating functions could be discovered.

Let's say I want to generate all possible arithmetic expressions with $n$ values using a predefined set of operators.

$$((((((((x_1+x_2)+x_3)+x_4)+x_5)-x_6)+x_7)-x_8)\cdot x_9)$$

Above is one of the expressions I want to generate where $n=9$ and $\{+,-,\cdot\}$ the operator set. If I'm wondering how many of these are there, it's obviously (if I generate all possible operator trees) equal to Catalan(n) - multiplied by number of ways to color tree nodes with different operators (leaves of the tree are fixed values).

If I were to use only $+$ as an operator I'd have no need for brackets and the number of possible trees would be $1$ regardless of the chosen $n$.

Let's say I want to remove unnecessary brackets and count the trees with $n$ numbers and operator set $S = \{+,-,\cdot, /, \text{^}\}$ where commutativity, associativity and precedence applies.

I've managed to discover generating functions for all subsets of operator set $S$ (have no clue how to prove the thing but am confident they are correct).

For the given $S$ the generating function is

$$F(x)=1+xF(x)+4xF(x)^2+x^2{F(x)}^3\;.$$

Is there a way where I could, using this generating function, generate all of these constrained (no unnecessary brackets) trees without having to first generate all trees and then remove the unnecessary brackets?

$\endgroup$
  • $\begingroup$ Do you mean you want to count all distinct numbers this generates, or distinct expressions (in which case it would be better to use indeterminates $X_1, X_2, \ldots$ instead of $1, 2, \ldots$)? $\endgroup$ – Robert Israel Jul 20 '16 at 17:55
  • $\begingroup$ Yeah, expressions, I'll edit it. $\endgroup$ – David Mitchell Jul 20 '16 at 18:57
  • $\begingroup$ Are you including identities such as $(x\text{^} y)\text{^} z = x\text{^}(y \cdot z)$, which is true over the positive reals but not for complex numbers? $\endgroup$ – Robert Israel Jul 20 '16 at 19:26
  • $\begingroup$ I am no expert on this but it would appear that Maple's combstruct package could be of use here. $\endgroup$ – Marko Riedel Jul 20 '16 at 20:09
  • $\begingroup$ @RobertIsrael I wasn't really thinking of numbers in particular, just on the simple properties of operators. lpaste.net/170857 So, nope, I wasn't really saying that (x/y)/z is equivalent to x/(y*z) or similar. $\endgroup$ – David Mitchell Jul 20 '16 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.