Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BinaryCompositions

Source Notebook

List all possible binary compositions for a set of chosen symbols

Contributed by: Bradley Klee

ResourceFunction["BinaryCompositions"][leafn,sym]

returns all possible binary compositions of symbols listed in sym whose proper leaf count (terminal nodes only) equals leafn.

Examples

Basic Examples (3) 

Axiom-level binary compositions for cases n=1,…,4:

In[1]:=
Column[ResourceFunction["BinaryCompositions"][2, Alphabet[][[1 ;; #]] ] & /@ Range[4]]
Out[1]=

Double level composition acts like Tuples:

In[2]:=
Column[StringJoin /@ Tuples[Alphabet[][[1 ;; #]], {2}] & /@ Range[4]]
Out[2]=

Binary compositions are composable:

In[3]:=
ResourceFunction["BinaryCompositions"][3, {a, b}]
Out[3]=

The recursive count of compositions relates to OEIS A025225, i.e. to the generators of 2-colored planar binary trees:

In[4]:=
Grid[{ Length@ResourceFunction[ "BinaryCompositions"][#, {\[FormalA], \[FormalB]}] & /@ Range[1, 6], 2^# CatalanNumber[# - 1] & /@ Range[1, 6]}, Spacings -> 4]
Out[4]=

The terminal node leaf count is two more than the composition depth:

In[5]:=
Column[ Function[{len}, Union /@ Map[LeafCount[TreeForm[#]]/2 &, ResourceFunction["BinaryCompositions"][#, Alphabet[][[1 ;; len]] ] & /@ Range[1, 5], {2}]] /@ Range[4]]
Out[5]=

Publisher

Brad Klee

Version History

  • 1.0.0 – 10 January 2022

Related Resources

License Information