WOLFRAM NOTEBOOK

This project looks to explore numerical multiway systems through visualization, and analyze relationships and patterns with more advanced functions. Afterwards, the project moves to focus on a relationship between the Catalan numbers and Dyck paths. Multiway systems were created, and custom rendering was done to generate the Dyck path based on edges. The goal of this project was to visualize Dyck graphs, and then add modifications, such as blocking a certain edge or moving the diagonal higher, and analyze any possible generalizations made from the modifications.

Introduction

Multiway systems are systems generated by a set of rules that are recursively applied to all of the outputs. Here’s a sample systematic output from a rule:
s {
f
1
[s],
f
2
[s]}
Symbolic multiway graph
In[]:=
ResourceFunction["NestGraphTagged"][n{Subscript[f,1][n],Subscript[f,2][n]},s,3,EdgeLabels->(DirectedEdge[_,_,i_]:>Placed[Text@({"
f
1
","
f
2
"}[[i]]),0.5]),AspectRatio->.4,"StateLabeling"->True,"FormattingFunction"->(Style[Text[#],9,Black]&),FormatTypeStandardForm,ImageSize->680]
Out[]=
Multiway systems can have a myriad of applications, including studying states in games and puzzles, such as Othello, or more theoretical aspects such as its use in the Wolfram Physics Project.

General Observations

Generally, with a linear or multiplicative multiway system, merging behavior can be predicted by the various constant values.
Consider a system of the form
n|->{an,n+b}
With this, we can predict the initial grid like pattern that arises, at least from the lower level branches.
Merger in symbolic multiway system
In[]:=
Graph[With[{g=ResourceFunction["NestGraphTagged"][x|->Expand[{5x,x+3}],{n},6,"StateLabeling"->True]},Subgraph[g,First/@First[FindCycle[UndirectedGraph[g],{8}]]]]]
Out[]=
The left hand side will always have
a+1
sides, and the right hand side has 2 sides, resulting in (
a+3
)-gons, as explained by Stephen Wolfram’s work “Multicomputation with Numbers: The Case of Simple Multiway Systems.” However, there are some exceptions to this behavior. For example, consider the rule set
n|->{2n,n+5}
The resulting graph ends up with one heptagon, with the remaining grids being pentagons. Every pentagon is also in the format of the generalized (
n+3
)-gon as explained above, which is trivial to see.
Plot of the new multiway system with the above rules
In[]:=
ResourceFunction["NestGraphTagged"][n{2n,n+5},{1},7,"StateLabeling"->True,PlotLegendsTraditionalForm/@{2n,n+5}]
Out[]=
Zooming in on the heptagon subset, we see the left hand side is entirely made up of powers of
a
(in this case 2).
Subgraph of the heptagon
In[]:=
Graph[With[{g=ResourceFunction["NestGraphTagged"][x|->Expand[{2x,x+5}],{1},6,"StateLabeling"->True]},Subgraph[g,First/@First[FindCycle[UndirectedGraph[g],{7}]]]]]
Out[]=
Conveniently,
x
+
Z
|
x
a
1(modb)
and this can easily be seen as true, as an integer
x
would exist through Fermat’s Little Theorem, since
a
and
b
are relatively prime. This suggests the only irregularities from an otherwise uniform lattice grid would be multiples of the order that make this equation true.
Experimenting with more functions here, we see interesting relationships.
Totient function and resulting graph with
n-Φ(n)
In[]:=
totient[n_Integer]:=Length[ResourceFunction["CoprimeIntegerList"][n]]ResourceFunction["NestGraphTagged"][n{totient[n],n-totient[n]},{1138},20,"StateLabeling"->True,PlotLegendsTraditionalForm/@{Totient[n],Common[n]}]
Out[]=

Dyck Paths

From any given point, a path can be generated by the map
or simply right and up “moves”. However, to make this path into a Dyck path, we will have to consider the restriction of the diagonal. To turn this into a multiway graph, we recursively build the graph by finding the next edge with the rule described above.
The Which above hard codes the empty set case and the ending case (i.e., all up), and checks the ending lattice point of the last edge to consider how many of the paths would be valid.
Generates all the next possible edges from the last move of the step
This function generates the Dyck path from the list of edges provided.
Generates the graph from a list of edges
Generates a random valid Dyck path on a n×n-grid
To test this, we will generate a 6×6 Dyck path using our newly defined function.
Generates and displays a Dyck path on a 6×6-grid
In preparation for creating our multiway system, the display function will be updated to clear up some clutter. The ImageSize option is updated to become smaller, and we get rid of the Frame (axes and numbers) of the plot.
Smaller display function to not clutter up the multiway graphs
Now, to actually create the multiway system, we utilize the function “MultiwaySystem” from the Wolfram Research Repository.
Function to create the multiway system for Dyck graphs
We can call it below to generate a sample Dyck path multiway system.
Generates a Dyck graph
Here’s an interactive you can play around with for the various levels
Visual of Dyck path recursive chain and steps for a 4×4 grid
Counting all valid Dyck paths for 1×1 to 6×6 grids.
Do the number of paths look familiar? To those well versed in number theory, you should recognize these as the Catalan numbers.
Catalan numbers
To get an interactive visualization, we need to create a few functions, as well as updating a few old ones, which will be explained later, in preparation for the next section.
Updated functions:
Updated functions to add restrictions (explained later)
New functions for the recurrence visualization:
Dynamic output of recursive formula of Catalan numbers
Alternatively, we can also prove an explicit formula for the Catalan numbers.
There is a proof for the Catalan numbers iteratively involving generating functions, which will be explained briefly here as well.
Proof. Let us define the generating functions for the Catalan numbers as
and solving, we get
Since
it follows that
Now, we expand the numerator using the binomial theorem
and we can quickly check this result by comparing the expansion of the coefficients with our general form.
Substituting this back in, we get
meaning
agreeing with our earlier result.

Modifications

Now, we seek to explore modified Dyck graphs and analyze the changes in behavior and number of paths. For example, what happens when our restriction isn’t just a diagonal? What happens if we want to prevent paths from passing a specific edge? What would happen if we didn’t have to strictly travel right or up?
Once again, here is the list of updated functions.
Updated functions to add customizable restrictions

Column Restrictions

A basic example would be moving up all the resCol values up by one.
Now what if the column restrictions weren’t uniform?
This is a significant difference from the 132 paths that would have resulted from a uniform change.

Edge Restrictions

Horizontal Restrictions

Adding (1, 0)--(2, 0) to badEdges
Adding (2, 0)--(3, 0) to badEdges
Simplifying, we get
To prove this, we can use complimentary counting with the help of a proof from a Codeforces editorial.
and generalized as
Adding (1, 1)--(2, 1) to badEdges
Closed form check
Adding (2, 1)--(3, 1) to badEdges
Adding (3, 1)--(4, 1) to badEdges

Vertical Edges

Adding (2, 0)--(2, 1) to badEdges
Adding (3, 0)--(3, 1) to badEdges
Closed form check

Multiple restrictions

Now, if we were to block out multiple edges, we get more interesting results.
Blocked out two edges that wouldn’t funnel all the paths into one path, namely (2, 2)--(3, 2) and (3, 0)--(3, 1)

Increment Modifications

What would happen if we changed the steps? Let’s see what happens when we change the right move from one unit to two units.
Closed form check
Adjusted step sizes for increments of 3 for x and 1 for y
Closed form check
What would happen if we would have a non-1 step? For example, what if we had an increment of 2 up and an increment of 3 right (using relatively prime numbers because otherwise it can be reduced into simpler increments)?
Adjusted step sizes for increments of 3 for x and 2 for y
Now, we’ll generate graphs with a 5 step and 2 step increment.
Adjusted step sizes for increments of 5 for x and 2 for y
Finally, we’ll look at graphs with a 5 step and 3 step increment.
Adjusted step sizes for increments of 5 for x and 3 for y
Now, what would happen if we added a third step?
Updated dyckNext function with a new edge {{x, y}, {x + 1, y + 1}

Conclusion

Being able to visualize Dyck graphs has led to many conclusions relating to the number of Dyck paths with Catalan numbers. Some of the results were the coefficients of a product of generating functions, suggesting a different approach to investigate further and the way to think about proving relations in the future. Catalan numbers are thoroughly engraved in Dyck paths, and visually representing them allowed for a better understanding of some of the recursive generations and proofs.

Future Directions

Extensions

  • Add analysis to Motzkin numbers and other similar numbers, or so proclaimed “royal paths” that are Dyck paths strictly beneath the diagonal (strong bound vs weak bound).
  • Working on more proofs and generalization as possible (i.e. do putting two blocked edges with known properties have multiplicative properties?), as well as further experimentation.
  • Playing around with more with non-uniform lines--these would probably not be able to be generalized, and would be a lot more difficult to pattern find anything, but could lead to interesting results.
  • Possibly adding more directions as well, such as what would happen when you introduce left and down moves? What if they can’t traverse the same lattice point?
  • The multiway function was also quite finicky, and required functions to be evaluated at a specific order for it to form a graph; otherwise the output of a code cell would simply become a Graph object.
  • References

  • Baracchini, G. (2016). Dyck paths and up-down walks. 1–11. https://math.mit.edu/~apost/courses/18.204-2016/18.204_Gabriella_Baracchini_final_paper.pdf
  • Barry, P. (2010). Generalized Catalan numbers, Hankel transforms and Somos-4 sequences. 2 Journal of Integer Sequences, 13(10.7.2), 1–16.
  • Bizley, M. (1954). Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (Km, kn) having just t contacts with the line my= nx and having no points above this line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line. JIA, 80, 55–62.
  • Games and puzzles as multicomputational systems. (2022, June 8). https://writings.stephenwolfram.com/2022/06/games-and-puzzles-as-multicomputational-systems/
  • jason. (2016, October 1). Showing directly that Dyck paths satisfy the Catalan recurrence [Forum post]. Mathematics Stack Exchange. https://math.stackexchange.com/q/1948805
  • Multicomputation with numbers: The case of simple multiway systems—Wolfram Physics bulletins. (2021, October 7). https://wolframphysics.org/bulletins/2021/10/multicomputation-with-numbers-the-case-of-simple-multiway-systems/
  • Scheuer, M. (2014, September 13). Answer to “Simplifying Catalan number recurrence relation” [Online post]. Mathematics Stack Exchange. https://math.stackexchange.com/a/930176
  • The on-line encyclopedia of integer sequences®(Oeis®). (n.d.). Retrieved July 10, 2024, from https://oeis.org/
  • [Tutorial] Catalan numbers and Catalan convolution. (n.d.). Codeforces. Retrieved July 10, 2024, from https://codeforces.com/blog/entry/87585
  • Weisstein, E. W. (n.d.-a). Catalan number [Text]. Retrieved July 10, 2024, from https://mathworld.wolfram.com/
  • Weisstein, E. W. (n.d.-b). Dyck path [Text]. Retrieved July 10, 2024, from https://mathworld.wolfram.com/
  • Weisstein, E. W. (n.d.-c). Motzkin number [Text]. Retrieved July 10, 2024, from https://mathworld.wolfram.com/
  • Acknowledgements

    Thanks to Henry, my mentor, and my mentor group for helping float ideas around and making project time productive and enjoyable; to the directors (Rory, Eryn, Megan) for making this program possible; and to my friends who looked over it and made me enjoy this program.
    Wolfram Cloud

    You are using a browser not supported by the Wolfram Cloud

    Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


    I understand and wish to continue anyway »

    You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.