Give five symbolic and mathematical definitions related to time complexity.

Some Definitions for Time Complexity.


## Symbols and definitions

1. **Big O notation ($O$)**: If $\exists{c, n_{0}} \in \mathbb{R}^{+}$, such that $\forall{n} > n_0$, $f(n) \leq cg(n)$, then $f(n) = O(g(n))$.
2. **Small o symbol ($o$)**: If $\forall{c} > 0$, $\exists{n_0}$, such that $\forall{n} > n_0$, $f(n) < cg (n)$, then $f(n) = o(g(n))$.
3. **Big Omega symbol ($Ω$)**: If $\exists{c, n_{0}} \in \mathbb{R}^{+}$, such that $\forall{n} > n_0$, $ f(n) \geq cg(n)$, then $f(n) = \Omega(g(n))$.
4. **Small omega symbol ($ω$)**: If $\forall{c} > 0$, $\exists{n_0}$, such that $\forall{n} > n_0$, $f(n) > cg (n)$, then $f(n) = \omega(g(n))$.
5. **Theta symbol ($θ$)**: If $\exists{c_1, c_2, n_0} \in \mathbb{R}^{+}$, such that $\forall{n} > n_0$, $c_1g( n) \leq f(n) \leq c_2g(n)$, then $f(n) = \Theta(g(n))$. It can be understood that when the complexity of the upper bound and the lower bound both increase by the same amount, then this complexity is also called a compact bound.

These notations describe the asymptotic behavior of algorithms' time complexity, aiding in understanding their performance characteristics.

| Notation | Meaning           | Intuition                |
| -------- | ----------------- | ------------------------ |
| $\Theta$ | Tight Bound       | Equivalent to "="        |
| $O$      | Upper Bound       | Less than or equal to    |
| $o$      | Loose Upper Bound | Less than                |
| $\Omega$ | Lower Bound       | Greater than or equal to |
| $\omega$ | Loose Lower Bound | Greater than             |

## Average, Best, Worst Cases

Time complexity is generally used to compare different algorithms, such as bubble sort, insertion sort, and heap sort. However, for the same algorithm, depending on the input, we can also consider average, best, and worst case time complexities. For example, the time complexity of a binary search tree varies between a singly linked list and a balanced tree.

**Average Time Complexity**: A measure of the weighted average of an algorithm's running time over all possible input cases. Let $T(n)$ be the running time of the algorithm for an input size of $n$. The average time complexity $\bar{T}(n)$ is defined as

$$
\bar{T}(n) = \sum_{i=1}^{k} p_i \cdot T_i(n)
$$

where $T_i(n)$ is the running time for the $i$th input case, $p_i$ is the probability of the $i$th case, and $k$ is the total number of possible input cases.

**Best Case Time Complexity**: The minimum running time required by an algorithm in the most ideal scenario.

**Worst Case Time Complexity**: The maximum running time required by an algorithm in the least ideal scenario.



This article will introduce some commonly used classical ciphers, which have been applied in history, reflecting the wisdom of ancient people. In ancient times, with low productivity and backward computing devices, classical ciphers had a certain protective effect. However, with the improvement of computer computing power nowadays, these classical ciphers have become very vulnerable and no longer practical.

Nowadays, there are many methods for breaking these classical ciphers. When I have the opportunity later on, I will summarize some of the decryption techniques for classical ciphers.

## Caesar Cipher

When it comes to classical ciphers, one classic example is the Caesar Cipher. The Caesar Cipher is a simple substitution encryption method based on letter shifting.

Core Idea: The core idea of the Caesar Cipher is to obtain the ciphertext by shifting each letter in the plaintext by a fixed number. This number of shifts is called the offset or key.

Algorithm Steps:

1. Determine the offset, i.e., the number of shifts.
2. For encryption, shift each letter in the plaintext backward by the offset to obtain the ciphertext.
3. For decryption, shift each letter in the ciphertext forward by the offset to obtain the plaintext.

TypeScript Implementation:

```typescript
function caesarCipherEncrypt(plainText: string, shift: number): string {
  let result = "";
  for (let i = 0; i < plainText.length; i++) {
    let char = plainText[i];
    if (char.match(/[a-z]/i)) {
      let code = plainText.charCodeAt(i);
      if (code >= 65 && code <= 90) {
        char = String.fromCharCode(((code - 65 + shift) % 26) + 65);
      } else if (code >= 97 && code <= 122) {
        char = String.fromCharCode(((code - 97 + shift) % 26) + 97);
      }
    }
    result += char;
  }
  return result;
}

function caesarCipherDecrypt(cipherText: string, shift: number): string {
  return caesarCipherEncrypt(cipherText, 26 - shift);
}
```

This TypeScript implementation provides encryption and decryption functions for the Caesar Cipher. The encryption function accepts plaintext and the offset as parameters and returns ciphertext, while the decryption function accepts ciphertext and the offset as parameters and returns plaintext.

## Rail Fence Cipher

The Rail Fence Cipher is a classical substitution encryption method based on rearranging the letters in the plaintext. The core idea of the Rail Fence Cipher is to rearrange the letters in the plaintext to form a matrix with a specific number of rows, and then read the letters in the matrix in a certain order to obtain the ciphertext.

Algorithm Steps:

1. Determine the height of the rail fence, i.e., the number of rows in the matrix.
2. Write the plaintext into a matrix according to the height of the rail fence.
3. Read the letters in the matrix in a specific order to obtain the ciphertext.
4. For decryption, knowing the height of the rail fence is necessary to correctly rearrange the letters in the ciphertext to obtain the plaintext.

Idea:
The Rail Fence Cipher is a substitution encryption method based on rearranging letters. Encryption and decryption are achieved by reading the letters in the matrix in a specific order.

TypeScript Implementation:

```typescript
function railFenceCipherEncrypt(plainText: string, height: number): string {
  let rail: string[][] = new Array(height).fill(null).map(() => []);
  let directionDown = false;
  let row = 0;
  for (let char of plainText) {
    rail[row].push(char);
    if (row === 0 || row === height - 1) {
      directionDown = !directionDown;
    }
    directionDown ? row++ : row--;
  }
  let result = "";
  for (let i = 0; i < height; i++) {
    result += rail[i].join("");
  }
  return result;
}

function railFenceCipherDecrypt(cipherText: string, height: number): string {
  let rail: string[][] = new Array(height).fill(null).map(() => []);
  let directionDown = false;
  let row = 0;
  for (let char of cipherText) {
    rail[row].push("x"); // Placeholder, will be replaced later
    if (row === 0 || row === height - 1) {
      directionDown = !directionDown;
    }
    directionDown ? row++ : row--;
  }
  let index = 0;
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < rail[i].length; j++) {
      if (rail[i][j] === "x") {
        rail[i][j] = cipherText[index++];
      }
    }
  }
  directionDown = false;
  row = 0;
  let result = "";
  for (let i = 0; i < cipherText.length; i++) {
    result += rail[row].shift();
    if (row === 0 || row === height - 1) {
      directionDown = !directionDown;
    }
    directionDown ? row++ : row--;
  }
  return result;
}
```

This TypeScript implementation provides encryption and decryption functions for the Rail Fence Cipher. The encryption function accepts plaintext and the height of the rail fence as parameters and returns ciphertext, while the decryption function accepts ciphertext and the height of the rail fence as parameters and returns plaintext.

## Route Cipher

The Route Cipher, also known as the Path Transposition Cipher, is a substitution encryption method based on matrix rearrangement. Its core idea is to read the characters in the matrix according to a predetermined path order to encrypt or decrypt messages. The essence of the Route Cipher is to arrange the plaintext into a matrix along a specific path and then read the characters in the matrix according to the predetermined path order to obtain the ciphertext.

Algorithm Steps:

1. Arrange the plaintext into a matrix along a specific path.
2. Read the characters in the matrix according to the predetermined path order to obtain the ciphertext.
3. For decryption, read the characters in the ciphertext according to the same path order to reconstruct the plaintext.

TypeScript Implementation:

```typescript
function routeCipherEncrypt(plainText: string, rows: number, cols: number, path: number[][]): string {
  let matrix: string[][] = new Array(rows).fill(null).map(() => new Array(cols).fill(""));
  let index = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (index < plainText.length) {
        matrix[r][c] = plainText[index++];
      }
    }
  }
  let result = "";
  for (let step of path) {
    let [r, c] = step;
    result += matrix[r][c];
  }
  return result;
}

function routeCipherDecrypt(cipherText: string, rows: number, cols: number, path: number[][]): string {
  let matrix: string[][] = new Array(rows).fill(null).map(() => new Array(cols).fill(""));
  let index = 0;
  for (let step of path) {
    let [r, c] = step;
    matrix[r][c] = cipherText[index++];
  }
  let result = "";
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      result += matrix[r][c];
    }
  }
  return result;
}
```

This TypeScript implementation provides encryption and decryption functions for the Route Cipher. The encryption function accepts plaintext, the number of rows and columns in the matrix, and the path as parameters, and returns ciphertext. The decryption function accepts ciphertext, the number of rows and columns in the matrix, and the path as parameters, and returns plaintext.

It is worth noting that:

- The Route Cipher is based on path transposition.
- It uses a matrix (usually a square matrix) to represent the plaintext, and then selects characters for encryption by following a predetermined path in the matrix.
- Encryption paths can be straight lines, curves, or any other shape, with each path representing a key.
- During decryption, knowledge of the same path is required to reverse the operation.

## Vigenère Cipher

The Vigenère Cipher is a polyalphabetic substitution cipher and is one of the most famous ciphers in classical cryptography. It encrypts plaintext using a keyword, employing the concept of multiple Caesar ciphers to achieve a more complex substitution encryption.

Core Idea:
The core idea of the Vigenère Cipher is to encrypt plaintext using a keyword (key). Each letter in the keyword corresponds to a shift number in the alphabet, forming a set of Caesar ciphers. Then, for each letter in the plaintext, a shift is performed using the corresponding shift number from the keyword to obtain the ciphertext.

Algorithm Steps:

1. Choose a keyword as the key.
2. Repeat the keyword until it matches the length of the plaintext.
3. For encryption, shift each letter in the plaintext by the corresponding letter of the keyword at the same position to obtain the ciphertext.
4. For decryption, use the same keyword to shift each letter in the ciphertext by the corresponding letter of the keyword at the same position in reverse to obtain the plaintext.

The Vigenère Cipher is a polyalphabetic substitution cipher that achieves encryption and decryption by using a keyword and the concept of multiple Caesar ciphers. Compared to a single Caesar cipher, the Vigenère Cipher provides a more complex encryption method, making decryption more difficult.

TypeScript Implementation:

```typescript
function vigenereCipherEncrypt(plainText: string, key: string): string {
  const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let encryptedText = "";
  key = key.toUpperCase();
  for (let i = 0, j = 0; i < plainText.length; i++) {
    const char = plainText[i].toUpperCase();
    if (alphabet.includes(char)) {
      const shift = alphabet.indexOf(key[j % key.length]);
      const charIndex = alphabet.indexOf(char);
      const encryptedIndex = (charIndex + shift) % alphabet.length;
      encryptedText += alphabet[encryptedIndex];
      j++;
    } else {
      encryptedText += char;
    }
  }
  return encryptedText;
}

function vigenereCipherDecrypt(cipherText: string, key: string): string {
  const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let decryptedText = "";
  key = key.toUpperCase();
  for (let i = 0, j = 0; i < cipherText.length; i++) {
    const char = cipherText[i].toUpperCase();
    if (alphabet.includes(char)) {
      const shift = alphabet.indexOf(key[j % key.length]);
      const charIndex = alphabet.indexOf(char);
      const decryptedIndex = (charIndex - shift + alphabet.length) % alphabet.length;
      decryptedText += alphabet[decryptedIndex];
      j++;
    } else {
      decryptedText += char;
    }
  }
  return decryptedText;
}

// Example usage
const plainText = "HELLO";
const key = "KEY";
const encryptedText = vigenereCipherEncrypt(plainText, key);
console.log("Encrypted Text: ", encryptedText); // Output encrypted text
const decryptedText = vigenereCipherDecrypt(encryptedText, key);
console.log("Decrypted Text: ", decryptedText); // Output decrypted text
```

In this example, the `vigenereCipherEncrypt` function encrypts plaintext, and the `vigenereCipherDecrypt` function decrypts ciphertext. These functions use a keyword to encrypt plaintext and decrypt ciphertext, employing the concept of the Vigenère Cipher.

The Vigenère Cipher has been widely used historically and still holds value in modern cryptography. While it can be cracked using modern cryptographic analysis techniques, it still provides a certain level of protection under certain conditions.

## Baconian Cipher

The Baconian cipher is an ancient cryptographic technique named after the 16th-century English philosopher, Francis Bacon. This cipher utilizes the form of letters to encrypt textual information into a series of different symbols.

In the Baconian cipher, typically two different symbols, often represented as "A" and "B" (or "a" and "b"), are used to represent different letters in the plaintext. For example, "A" might represent the letter "A" in the plaintext, while "B" might represent other letters. Through this method, textual information can be transformed into a sequence of "A" and "B" characters, thus achieving encryption.

Below are the algorithm steps for the Baconian cipher:

1. Firstly, create a Baconian cipher alphabet, which includes the mapping relationship between plaintext letters and their corresponding Baconian cipher symbols. Typically, two symbols, A and B, are used to represent letters.

2. Convert the plaintext to uppercase and remove any characters other than letters.

3. Iterate over each letter in the plaintext:
   - For each letter, find its corresponding Baconian cipher symbol in the alphabet.
   - Concatenate the found Baconian cipher symbols to form the ciphertext.

Here's a TypeScript implementation:

```typescript
class BaconCipher {
  private static baconianAlphabet: { [key: string]: string } = {
    A: "AAAAA",
    B: "AAAAB",
    C: "AAABA",
    D: "AAABB",
    E: "AABAA",
    F: "AABAB",
    G: "AABBA",
    H: "AABBB",
    I: "ABAAA",
    J: "ABAAB",
    K: "ABABA",
    L: "ABABB",
    M: "ABBAA",
    N: "ABBAB",
    O: "ABBBA",
    P: "ABBBB",
    Q: "BAAAA",
    R: "BAAAB",
    S: "BAABA",
    T: "BAABB",
    U: "BABAA",
    V: "BABAB",
    W: "BABBA",
    X: "BABBB",
    Y: "BBAAA",
    Z: "BBAAB",
  };

  public static encrypt(plaintext: string): string {
    // Convert plaintext to uppercase and remove non-alphabetic characters
    plaintext = plaintext.toUpperCase().replace(/[^A-Z]/g, "");

    let ciphertext = "";
    for (let i = 0; i < plaintext.length; i++) {
      const letter = plaintext[i];
      const baconianLetter = this.baconianAlphabet[letter];
      if (baconianLetter) {
        ciphertext += baconianLetter;
      }
    }
    return ciphertext;
  }

  public static decrypt(ciphertext: string): string {
    let plaintext = "";
    for (let i = 0; i < ciphertext.length; i += 5) {
      const chunk = ciphertext.substr(i, 5);
      const letter = this.getBaconianLetter(chunk);
      if (letter !== null) {
        plaintext += letter;
      }
    }
    return plaintext;
  }

  private static getBaconianLetter(baconianCode: string): string | null {
    for (const [key, value] of Object.entries(this.baconianAlphabet)) {
      if (value === baconianCode) {
        return key;
      }
    }
    return null; // If no matching letter found
  }
}

// Example usage:
const plaintext = "HELLO";
const ciphertext = BaconCipher.encrypt(plaintext);
console.log("Plaintext:", plaintext);
console.log("Ciphertext:", ciphertext);

const decryptedText = BaconCipher.decrypt(ciphertext);
console.log("Decrypted Text:", decryptedText);
```

This TypeScript code implements the encryption and decryption functionality of the Baconian cipher. You can pass the plaintext to the `BaconCipher.encrypt()` method for encryption or pass the ciphertext to the `BaconCipher.decrypt()` method for decryption.

## Affine Cipher

The Affine cipher is an ancient substitution cipher that combines the concepts of the Caesar cipher and linear algebra. It encrypts each letter in the plaintext by using two values called the encryption key (a) and the offset key (b).

The encryption formula for the Affine cipher is $E(x) = (ax + b) \mod m$, where:

- $x$ is the numerical representation of the plaintext letter in the alphabet (usually starting from 0, where 'a' is 0, 'b' is 1, and so on).
- $a$ and $b$ are the encryption keys.
- $m$ is the size of the alphabet (usually 26 for English).

To decrypt, the modular multiplicative inverse of the encryption key is used. The encryption key $a$ must be coprime with the alphabet size $m$ to ensure that each letter can be correctly encrypted and decrypted.

Below are the algorithm steps for the Affine cipher:

1. Choose appropriate encryption key $a$ and offset key $b$.
2. Convert each letter in the plaintext to its numerical representation $x$ in the alphabet.
3. Apply the Affine encryption formula to each numerical value $x$ to obtain the corresponding ciphertext value.
4. Convert the ciphertext numerical values back to letter representations in the alphabet.

Here's a TypeScript implementation:

```typescript
class AffineCipher {
  private static readonly alphabetSize: number = 26; // Size of the English alphabet

  public static encrypt(plaintext: string, a: number, b: number): string {
    let ciphertext = "";
    plaintext = plaintext.toUpperCase().replace(/[^A-Z]/g, ""); // Convert to uppercase and remove non-alphabetic characters
    for (let i = 0; i < plaintext.length; i++) {
      const char = plaintext[i];
      const charCode = char.charCodeAt(0) - "A".charCodeAt(0); // Convert letter to numerical value from 0 to 25
      const encryptedCharCode = (a * charCode + b) % this.alphabetSize; // Affine encryption formula
      const encryptedChar = String.fromCharCode(encryptedCharCode + "A".charCodeAt(0)); // Convert numerical value back to letter
      ciphertext += encryptedChar;
    }
    return ciphertext;
  }

  public static decrypt(ciphertext: string, a: number, b: number): string {
    let plaintext = "";
    const aInverse = this.modInverse(a, this.alphabetSize); // Calculate the modular inverse of encryption key a
    for (let i = 0; i < ciphertext.length; i++) {
      const char = ciphertext[i];
      const charCode = char.charCodeAt(0) - "A".charCodeAt(0); // Convert letter to numerical value from 0 to 25
      const decryptedCharCode = (aInverse * (charCode - b + this.alphabetSize)) % this.alphabetSize; // Affine decryption formula
      const decryptedChar = String.fromCharCode(decryptedCharCode + "A".charCodeAt(0)); // Convert numerical value back to letter
      plaintext += decryptedChar;
    }
    return plaintext;
  }

  private static modInverse(a: number, m: number): number {
    for (let i = 1; i < m; i++) {
      if ((a * i) % m === 1) {
        return i;
      }
    }
    return -1; // If no modular inverse exists, return -1
  }
}

// Example usage:
const plaintext = "HELLO";
const a = 5; // Encryption key
const b = 8; // Offset key
const ciphertext = AffineCipher.encrypt(plaintext, a, b);
console.log("Plaintext:", plaintext);
console.log("Ciphertext:", ciphertext);

const decryptedText = AffineCipher.decrypt(ciphertext, a, b);
console.log("Decrypted Text:", decryptedText);
```

This TypeScript code implements the encryption and decryption functionality of the Affine cipher. You can pass the plaintext to the `AffineCipher.encrypt()` method for encryption or pass the ciphertext to the `AffineCipher.decrypt()` method for decryption.


This article explores classical ciphers historically used. In the past, amid low productivity and primitive computing, these ciphers offered protection.

Some Classical Ciphers and Implementations


## Catalan Numbers

Catalan numbers $H_n$ can be applied to the following problems:

1. There are $2n$ people queuing up to enter a theater. The entrance fee is 5 yuan. Among them, only $n$ people have a 5 yuan bill, while the other $n$ people only have a 10 yuan bill. The theater has no other bills. How many ways are there to ensure that whenever a person with a 10 yuan bill buys a ticket, the ticket office has a 5 yuan bill for change?
2. There is a grid of size $n\times n$ with the lower left corner at $(0, 0)$ and the upper right corner at $(n, n)$. Starting from the lower left corner, you can only move one unit to the right or up each time, without going above the diagonal line $y=x$. How many possible paths are there to reach the upper right corner without crossing the line $y=x$?
3. Choose $2n$ points on a circle and connect these points pairwise to obtain $n$ line segments. How many ways are there to ensure that the $n$ line segments obtained do not intersect?
4. Without intersecting diagonals, how many ways are there to divide a convex polygon area into triangular regions?
5. If the stack (infinite) has a push sequence of $1,2,3, \cdots ,n$, how many different pop sequences are there?
6. How many different binary trees can be constructed with $n$ nodes?
7. Given $2n$ numbers consisting of $n$ $+1$s and $n$ $-1$s, denoted as $a_1,a_2, \cdots ,a_{2n}$, such that the partial sum satisfies $a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n)$, how many sequences satisfy this condition?

The corresponding sequence is:

| $H_0$ | $H_1$ | $H_2$ | $H_3$ | $H_4$ | $H_5$ | $H_6$ | ... |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :-: |
|   1   |   1   |   2   |   5   |  14   |  42   |  132  | ... |

## Recurrence Relation

The solution to this recurrence relation is:

$$
H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})
$$

Common formulas for Catalan numbers are:

$$
H_n = \begin{cases}
    \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\
    1 & n = 0, 1
\end{cases}
$$

$$
H_n = \frac{H_{n-1} (4n-2)}{n+1}
$$

$$
H_n = \binom{2n}{n} - \binom{2n}{n-1}
$$

> A common application: for a stack, the push sequence is $1,2, \ldots ,n$, find the total number of possible pop sequences.

```cpp
#include <iostream>
using namespace std;
int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // Here, formula 2 is used
  cout << f[n] << endl;
  return 0;
}
```

## Closed Form

The recurrence relation of Catalan numbers is

$$
H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2)
$$

where $H_0=1$ and $H_1=1$. Let its ordinary generating function be $H(x)$.

We find that the recurrence relation of Catalan numbers is similar to the form of convolution. Therefore, we construct an equation about $H(x)$ using convolution:

$$
\begin{aligned}
H(x)&=\sum_{n\ge 0}H_nx^n\\
&=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\
&=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\
&=1+xH^2(x)
\end{aligned}
$$

Solving this equation, we get

$$
H(x)=\frac{1\pm \sqrt{1-4x}}{2x}
$$

Now, we have a question: which root should we take? Rationalizing the numerator, we get

$$
H(x)=\frac{2}{1\mp \sqrt{1-4x}}
$$

Substituting $x=0$, we obtain the constant term of $H(x)$, which is $H_0$. When $H(x)=\dfrac{2}{1+\sqrt{1-4x}}$, we have $H(0)=1$, satisfying the requirement. The other root leads to the denominator being $0$ (non-convergence), so it is discarded.

Therefore, we obtain the closed form of the generating function of Catalan numbers:

$$
H(x)=\frac{1- \sqrt{1-4x}}{2x}
$$

Next, we need to expand it. But note that its denominator is not in the form of a polynomial like the Fibonacci sequence, so it is not convenient to use the expansion form of geometric sequences. Here we need to use Newton's binomial theorem. Let's first expand $\sqrt{1-4x}$:

$$
\begin{aligned}
(1-4x)^{\frac{1}{2}}
&=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\
&=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n
\end{aligned} \tag{1}
$$

Note that

$$
\begin{aligned}
\left(\frac{1}{2}\right)^{\underline{n}}
&=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\
&=\frac{(-1)^{n-1}(2n-3

)!!}{2^n}\\
&=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\
&=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!}
\end{aligned}
$$

Here, we use the simplification technique of double factorials. Then, substitute into $(1)$, we get

$$
\begin{aligned}
(1-4x)^{\frac{1}{2}}
&=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\
&=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\
&=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n
\end{aligned}
$$

Substitute back into the original expression, we get

$$
\begin{aligned}
H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\
&=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\
&=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\
&=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\
&=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\
\end{aligned}
$$

Thus, we obtain the general formula for Catalan numbers.

## Path Counting Problem

Non-decreasing paths refer to paths that can only move upwards or to the right.

1. The number of non-decreasing paths from $(0,0)$ to $(m,n)$ is equal to the number of permutations of $m$ $x$ and $n$ $y$, i.e., $\dbinom{n + m}{m}$.

2. The number of non-decreasing paths from $(0,0)$ to $(n,n)$ that do not touch the line $y=x$ except at endpoints:

   First, consider the paths below the line $y=x$, which all start from $(0, 0)$, pass through $(1, 0)$ and $(n, n-1)$, and reach $(n,n)$. This can be seen as the number of non-decreasing paths from $(1,0)$ to $(n,n-1)$ without touching $y=x$.

   All non-decreasing paths total $\dbinom{2n-2}{n-1}$. For any path that touches $y=x$, we can symmetrically transform the part from the point where it leaves this line to $(1,0)$, obtaining a non-decreasing path from $(0,1)$ to $(n,n-1)$. The reverse is also true. Hence, the number of non-decreasing paths below $y=x$ is $\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}$. Due to symmetry, the answer is $2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}$.

3. The number of non-decreasing paths from $(0,0)$ to $(n,n)$ that do not cross the line $y=x$: Similarly, we can obtain $\dfrac{2}{n+1}\dbinom{2n}{n}$ using similar methods.

> NOTE: This article is rewritten by [OI WIKI](https://oi-wiki.org/math/combinatorics/catalan/).


The article discusses Catalan numbers, a sequence used in combinatorial problems. It covers their recurrence relation, closed form, and applications in path counting. It provides insights into problem-solving using Catalan numbers.

Notation	Meaning	Intuition
$\Theta$	Tight Bound	Equivalent to "="
$O$	Upper Bound	Less than or equal to
$o$	Loose Upper Bound	Less than
$\Omega$	Lower Bound	Greater than or equal to
$\omega$	Loose Lower Bound	Greater than

NOTE & BLOG

Symbols and definitions

Average, Best, Worst Cases