User Portlet User Portlet

Brad Klee
Brad Klee
Wolfram Research
Collaboration Consulting Volunteering Meet ups Mentorships Networking

My introduction to the Wolfram community happened at Curry College, where I studied with Wolfram Summer School. Subsequently I extended my interest in primitive recursive functions to function programming and combinatory logic by working a few problems from Smullyan's "To Mock a Mockingbird". Here is a short program for listing all function compositions and computing the Catalan numbers:

RootedTrees[0] = {F[]};
RootedTrees[N_] := Union@Flatten[ Flatten[Outer[F, 
Sequence @@ (# /. n_Integer :> RootedTrees[n - 1]), 1]] & /@ 
Flatten[Permutations /@ IntegerPartitions[N], 1], 1]

Ouput, Count, and Test:

Flatten[RootedTrees /@ Range[0, 5]]
Out[]= {F[], F[F[]], F[F[F[]]], F[F[], F[]], F[F[F[F[]]]], F[F[F[], F[]]], 
F[F[], F[F[]]], F[F[F[]], F[]], F[F[], F[], F[]], F[F[F[F[F[]]]]], 
F[F[F[F[], F[]]]], F[F[F[], F[F[]]]], F[F[F[F[]], F[]]], 
F[F[F[], F[], F[]]], F[F[], F[F[F[]]]], F[F[], F[F[], F[]]], 
F[F[F[]], F[F[]]], F[F[F[F[]]], F[]], F[F[F[], F[]], F[]], 
F[F[], F[], F[F[]]], F[F[], F[F[]], F[]], F[F[F[]], F[], F[]], 
F[F[], F[], F[], F[]], F[F[F[F[F[F[]]]]]], F[F[F[F[F[], F[]]]]], 
F[F[F[F[], F[F[]]]]], F[F[F[F[F[]], F[]]]], F[F[F[F[], F[], F[]]]], 
F[F[F[], F[F[F[]]]]], F[F[F[], F[F[], F[]]]], F[F[F[F[]], F[F[]]]], 
F[F[F[F[F[]]], F[]]], F[F[F[F[], F[]], F[]]], F[F[F[], F[], F[F[]]]],
F[F[F[], F[F[]], F[]]], F[F[F[F[]], F[], F[]]], 
F[F[F[], F[], F[], F[]]], F[F[], F[F[F[F[]]]]], 
F[F[], F[F[F[], F[]]]], F[F[], F[F[], F[F[]]]], 
F[F[], F[F[F[]], F[]]], F[F[], F[F[], F[], F[]]], 
F[F[F[]], F[F[F[]]]], F[F[F[]], F[F[], F[]]], F[F[F[F[]]], F[F[]]], 
F[F[F[F[F[]]]], F[]], F[F[F[F[], F[]]], F[]], F[F[F[], F[]], F[F[]]],
F[F[F[], F[F[]]], F[]], F[F[F[F[]], F[]], F[]], 
F[F[F[], F[], F[]], F[]], F[F[], F[], F[F[F[]]]], 
F[F[], F[], F[F[], F[]]], F[F[], F[F[]], F[F[]]], 
F[F[], F[F[F[]]], F[]], F[F[], F[F[], F[]], F[]], 
F[F[F[]], F[], F[F[]]], F[F[F[]], F[F[]], F[]], 
F[F[F[F[]]], F[], F[]], F[F[F[], F[]], F[], F[]], 
F[F[], F[], F[], F[F[]]], F[F[], F[], F[F[]], F[]], 
F[F[], F[F[]], F[], F[]], F[F[F[]], F[], F[], F[]], 
F[F[], F[], F[], F[], F[]]}

{#, SameQ[#, CatalanNumber[#] & /@ Range[10]]
} &@(Length@RootedTrees[#] & /@ Range[10])

Out[]= {{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796}, True}