Function Repository Resource:

IrreducibleBinaryCompositions

List all irreducible binary compositions for a set of chosen symbols and a chosen simplification rule

Contributed by: Bradley Klee

ResourceFunction["IrreducibleBinaryCompositions"][rules,n,sym]

returns a rules-irreducible subset of all possible binary compositions of symbols listed in sym whose proper leaf count (terminal nodes only) equals n.

ResourceFunction["IrreducibleBinaryCompositions"][rules,n]

assumes compositions of only two formal variables, a and b.

Details

The argument rules is assumed to be one or more simplification rules; i.e. rules that reduce the leaf count.

The subset excludes compositions which match the left hand side of the rules on a subexpression at any level, and includes all other non-matching compositions.

Examples

Basic Examples (1)

Generate binary compositions where a never appears as a left argument:

In[1]:=

$ResourceFunction[ "IrreducibleBinaryCompositions"][\[FormalA]\[SmallCircle]x_ :> x, #] & /@ Range[2, 3] // TableForm$

Out[1]=

Scope (3)

Use more than one rule to allow for quantitatively different reduction paths:

In[2]:=

$ResourceFunction[ "IrreducibleBinaryCompositions"][{(\[FormalA]\[SmallCircle]x_) :> x, (\[FormalB]\[SmallCircle]x_)\[SmallCircle]\[FormalA] :> x}, #] & /@ Range[1, 3] // TableForm$

Out[2]=

For some choices of rule binary compositions are totally reducible:

In[3]:=

$ResourceFunction[ "IrreducibleBinaryCompositions"][{\[FormalA]\[SmallCircle]x_ :> x, \[FormalB]\[SmallCircle]x_ :> x, \[FormalC]\[SmallCircle]x_ :> x}, #, {\[FormalA], \[FormalB], \[FormalC]}] & /@ Range[5]$

Out[3]=

The following count of irreducible compositions is related to the super-Catalan numbers (OEIS A001003):

In[4]:=

$Divide[Length[ ResourceFunction[ "IrreducibleBinaryCompositions"][\[FormalA]\[SmallCircle]x_ :> x, #]], 2] & /@ Range[7]$

Out[4]=

Neat Examples (2)

Plot irreducible expressions as trees for a choice of leaf count equals three:

In[5]:=

$ResourceFunction[ "IrreducibleBinaryCompositions"][\[FormalA]\[SmallCircle]x_ :> x, 3]$

Out[5]=

In[6]:=

$Row[Map[ExpressionTree[#, ImageSize -> 100] &, ResourceFunction[ "IrreducibleBinaryCompositions"][\[FormalA]\[SmallCircle]x_ :> x, 3] /. SmallCircle -> "\[SmallCircle]"]]$