Some structures of the catalan numbers I

The Catalan numbers are ubiquitous in counting problems which is one of the primary reasons for its popularity. From various sources like books and Wikipedia we see that in combinatorial mathematics. The Catalan numbers form is a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects such as polygon triangulation, balanced parentheses, mountain ranges, diagonal avoiding paths and binary tree. Belgian mathematician Eugene Charles Catalan discovered Catalan numbers in 1838, while studying well-formed sequences of parentheses. They are named after the Belgian mathematician Eugene Charles Catalan. Although they are named after Catalan, they were not first discovered by him. These numbers appear in a variety of disguises, we are so used to having them around, it is perhaps hard to imagine a time when they were either unknown, or known but obscure and underappreciated. The organization of this paper is as follows. The first we encountered a number of occurrences of the CBC and Catalan numbers. Then, we study to understand the connections between these numbers and well-known structures of Catalan numbers like dyck paths, binary trees, permutations, partitions and etc. We also discuss some algebraic interpretations and additional aspects of Catalan numbers.

For positive integers $n\geq k$, the \textit{Binomial coefficient} ${n\choose k}=\frac{n!}{k!(n-k)!}$ appears in Khayyam Triangle which is one of the most important object to solving and proposing combinatorics problems. Using properties of binomial coefficients, we can write\begin{eqnarray*}{2n\choose n}&=&{2n-1\choose n-1}+{2n-1\choose n}\\&=&{2n-1\choose n}+{2n-1\choose n}\\&=&2{2n-1\choose n},\end{eqnarray*}where show these numbers are even. The \textit{CBC}s $\binom{2n}{n}$ are centrally located in even numbered rows in Pascal’s triangle, as Figure 1 shows. It was conjectured by \textit{Paul Erd\H{o}s} that the CBC numbers are squarefree for all $n>4$. This conjecturewas proved for every sufficiently large $n$ [4,16]. These numbers appears in several importance sequences like \textit{Catalan, Narayana, Motzikin and etc.} This is one of the reasons for researchers to having special attention to these numbers. The $n$-Catalan numbers defined as $C_n=\frac{1}{n+1}{2n\choose n}$, with initial value $C_0=1$. To date, nearly 400 articles and problems have appeared on Catalan numbers. \textit{Richard P. Stanley} of Massachusetts Institute of Technology has listed over $270$ occurrences of Catalan numbers in his EnumerativeCombinatorics, vol. 2, and another seventy on his Web site Catalan Addendum [17,18]. The CBC numbers are given as sequence $A000108 $ in the On-Line Encyclopedia of Integer Sequences [20]. Using generating functions, It can be employed to derive the following explicit formula . To this end, consider the generating function $C(x)=\sum_{n=0}^{\infty} C_nx^n=C_0+C_1x+C_2x^2+\cdots$. Using some initial values of Catalan numbers, we can write\begin{align*}\label{GF}xC^2(x)&=(1+x+2x^2+5x^3+14x^4+42x^5+\cdots)^2\\&=1+2x+5x^2+14x^3+\cdots =C(x)-1.\end{align*}Then\begin{eqnarray}4x^2C^2(x)=4xC(x)-4x+1-1\end{eqnarray}Solving for $C(x)=\frac{1-\sqrt{1-4x}}{2x}$. In this paper, we introduce and prove some structures of Catalan numbers. The set family like $\{\S_i\}_{n=1}^{\infty}$ is called structures of Catalan numbers if it can define the bijection $F: \S_n\longrightarrow C_n$ between these family and Catalan numbers. In the Section 1, we shall only study Dyck paths, and provide several bijective proofs like polygon triangulation, balanced parentheses, mountain ranges, that they are counted by Catalan numbers. We first introduce Dyck and binary paths, and then state our main theorem in Section 2.In Section 3, we states structures of Catalan numbers and Nonintersecting Chords. Let we have $2n$ persons with labaled $v_1; v_2;\ldots;v_{2n}$ such that located at the boundary of a circle with equal distancebetween every two adjacent persons. Let $R_n$ be the set of different ways to pair the $2n$persons with edges (as straight lines) that do no intersect. Then, $|R_n| = |C_n|$. In Section 4, we find structures of Catalan numbers and triangulated polygons. Section 5 devoted to structures of Catalan numbers and words. A \textit{plane tree} is a rooted tree with an ordering specified for the children of eachvertex. In the Section 6, we proved $C_n$ counts the number of plane trees with $n+1$ vertices and also, states several new structures of Catalan numbers and trees. Sections 7 and 8 devoted to structures of Catalan numbers between permutations and partitions., respectability.

There are many equivalent ways to define Catalan numbers. The main results of this paper,focus on combinatorial interpretations of Catalannumbers. Some of these structures of Catalan numbers which is discuss in this paper are1) Dyck paths of length $n$ with two steps $(0,1)$ and $(1,0)$.2) binary parenthesizations of a string of $n+1$ letters.3) The set of binary trees with n nodes.4) Plane trees with n internal nodes, all of degree 2.5) Paths from $(0,0)$ to $(2n,0)$ with steps $(1,−1)$ and $(1, 1)$, never falling below the $x$-axis.6) Noncrossing pairs of sequences of $n+1$ steps $(1, 0)$ and $(0, 1)$, which only intersect at start and end.7) In Stanley, this is described as non-intersecting arcs joining $n$ pairs of points in the plane. Our preferred version of this representation is to think of it as partitions of $2n$ into blocks of size 2.8) $n$ nonintersecting chords joining $2n$ points on a circle.9) Ways of drawing $n +1$ points on a line with arcs connecting them such that the arcs do not pass below the line, the arcs are noncrossing, all the arcs at a given node exit in the same direction (left or right), and the graph thus formed is a tree.10) Partitions of an $(n + 2)$-gon into triangles.11) Noncrossing partitions of $[n]$.12) Noncrossing Murasaki diagrams with $n$ vertical bars.13) Nonnesting partitions of $[n]$.14) Permutations of the multiset $\{1^2, 2^2,\ldots,n^2\}$ such that the first occurrences of each number appear in increasing order, and there is no subsequenceof the form $abab$.15) $321$-avoiding permutations of $[n]$.16) Permutations w of $[2n]$ with $n$ cycles of length two such that the product $(1, 2,\ldots,2n)w$ has $n$ cycles.17) Permutations of $[n]$ that can be stack sorted.18) Binary parenthesizations of a string of $n + 1$ letters.19) The numbers of the sequences $(a_1,\ldots,a_n)$ such that $1\leq a_1\leq \cdots \leq a_n$ and $a_i\leq i$.20) Standard Young Tableux of shape $(n, n)$.

We have studied some nice structures of the Catalan numbers in this paper. We make frequent references to Stanley’s list of Catalan representations [19]. These can be found in exercise 6.19, where each of the representations discussed is given as a part of the exercise. So, the first, we encountered a number of occurrences of the CBC $\binom{2n}{n}$ and Catalan numbers. Then, we study to understand the connections between these numbers and well-known structures of Catalan numbers like dyck paths, binary trees, permutations, partitions and etc. We also discuss some algebraic interpretations and additional aspects of Catalan numbers. It would be interesting for readers to considering results on divisibility of CBC and Catalan numbers. It would be interesting to explore similar techniques for Structures of Motzkin numbers, Delannoy numbers, Narayana Numbers and etc.