Since there are four proofs in the wikipedia article you referenced, it seems you aren’t looking for a mathematical explanation for the correspondence between the Catalan numbers and the permutations of a binary tree.
So instead, here are two ways to try and intuitively visualise how the Catalan sequence (1, 2, 5, 14, 42, …) arises in combinatorial systems.
Dicing polygons into triangles
For a polygon of side N, how many ways can you draw cuts between the vertices that chop the polygon up entirely into triangles?
- Triangle (N=3): 1 (It’s already a triangle)
- Square (N=4): 2 (Can slice at either diagonal)
- Pentagon (N=5): 5 (Two slicing lines emanating from a vertex. Five vertices to choose from)
- Hexagon (N=6): 14 (Try drawing it)
- …and so on.
Drawing a path through a grid without crossing the diagonal
In this case, the number of unique paths is the Catalan number.
2×2 grid => 2 paths
_| |
_| __|
3×3 grid => 5 paths
_| | _| | |
_| _ _| | _| |
_| _| _ _| _ _| _ _ _|
4×4 grid => 14 paths
5×5 grid => 42 paths
and so on.
If you try drawing the possible binary trees for a given N, you will see that the way the tree permutes is just the same.
Your desire not to just blindly accept the correspondence between the tree and the sequence is admirable. Unfortunately, it’s difficult to go much further with this discussion (and explain why the Catalan formula ‘happens to be’ the way it is) without invoking binomial mathematics. The Wikipedia discussion of binomial coefficients is a good starting point if you want to understand combinatorics (which includes permutation counting) itself in more depth.