# 4.3 ticket change

## Basic question: before the start of a fierce football match, ticket sales are in intense progress. Each ticket is 50 yuan. Now there are 2n people waiting in line to buy tickets, including n people holding 50 yuan bills and n people holding 100 yuan bills. Suppose there is no change at the ticket office when the ticket is sold How many queuing methods do these 2n individuals have to avoid the situation that the ticket office can't find money?

answer

## Catalan number

Let's start with the Cartland number:

- Catalan satisfies recursion formula: \ (H (n) = H (0) * H (n-1) + H (1) * H (n-2) ++ h(n-1) * h(0)\)
- Catalan alternative recurrence formula: \ (h(n) = \frac{h(n-1) * (4*n-2)}{n+1} \)
- The solution of recurrence relation is: \ (C_n = C_{2n}^n - C_{2n}^{n+1} = \frac{1}{n+1}C_{2n}^n \)

## Proof of Cartland number:

Given an N, a 0,1 sequence with a length of 2n is required, so that the number of 1 in any prefix of the sequence is not less than the number of 0

prove:

Consider a 2n bit binary number containing N ones and N zeros. When scanning to the 2m+1 bit, there are m+1 zeros and M ones, then the numbers of the following 0 and 1 are: N-M 1 and n-m-1 0 respectively,

If 2m+2 and subsequent 0 become 1 and 1 becomes 0, it corresponds to a binary number of n+1 0 and n-1 1 1, which does not meet the requirements

Thus \ (c_n = c_n = C {2n} ^ n - C {2n} ^ {n + 1} = \ frac {1} {n + 1} C {2n} ^ n \)

## Expansion issues:

### 1 matrix multiplication problem: \ (P = a_1 * a_2 * a_3 *... * a_n \) according to the multiplication combination law, do not change the mutual order of matrices, and only use parentheses to represent paired products. How many bracketed schemes are there?

The left bracket is equivalent to 1 and the right bracket is equivalent to 0. It is essentially a Cartland number

### 2 polygon division is called triangle problem. Find the number of methods for dividing a convex polygon region into a triangle region.

We start from node 1. In order to divide into triangular areas, node 1 cannot be connected with its adjacent nodes, so node 1 can connect 3, 4 n-1

We assume that node 1 connects i, then this line divides the polygon area into i convex polygon and N+2-i convex polygon, that is, for node 1, \ (f_1 (n) = f (3) * f (n + 2-3) ++ f(n-1)f(3)\)

The total segmentation method is \ (N*f_1(n) \), half of which is repeated

### 3 a resident of a city needs to walk 2n blocks to work every day (he works n blocks north and N blocks east of his residence). If he never crosses the diagonal from home to the company, how many possible paths are there?

Conform to Cartland number

### 4 select 2n points on the circle, connect these points in pairs, and find the number of methods to make the obtained N line segments disjoint?

Similar to expansion 2

### How many different binary trees can be constructed from 5 n nodes?

n = 0 , f(0) = 1

n = 1 , f(1) = 1

n = 2 , f(2) = 4

Where \ (f(i)*f(n-i-1) represents the number that can be constructed when the left subtree has I nodes and the right subtree has n-i-1 nodes \)

Conform to Cartland number

// 4.3 ticket change // Catalan number class Test{ public static void main(String[] args) { /** Basic questions: The intense work is going on before the football match. Each ticket is 50 yuan. Now there are 2n people queuing to buy tickets, including n people holding 50 yuan bills and n people holding 100 yuan bills. Suppose there is no change at the ticket office when the ticket is sold. How many queuing methods do these 2n individuals have to avoid the situation that the ticket office can't find money? answer $$res = C_{2n}^n - C_{2n}^{n-1} = \frac{1}{n+1}C_{2n}^n$$ */ /** Let's start with the Cartland number: Catalan Satisfy recursion formula: $H (n) = H (0) * H (n-1) + H (1) * H (n-2) ++ h(n-1) * h(0)$ Catalan Alternative recurrence formula: $h(n) = \frac{h(n-1) * (4*n-2)}{n+1}$ The solution of recurrence relation is: $C_n = C_{2n}^n - C_{2n}^{n+1} = \frac{1}{n+1}C_{2n}^n$ Proof of Cartland number: Given an N, a 0,1 sequence with a length of 2n is required, so that the number of 1 in any prefix of the sequence is not less than the number of 0 prove: Consider a 2n bit binary number containing N ones and N zeros. When scanning to the 2m+1 bit, there are m+1 zeros and M ones, then the numbers of the following 0 and 1 are: N-M 1 and n-m-1 0 respectively, If 2m+2 and subsequent 0 become 1 and 1 becomes 0, it corresponds to a binary number of n+1 0 and n-1 1 1, which does not meet the requirements Thus $C_n = C_n = C_{2n}^n - C_{2n}^{n+1} = \frac{1}{n+1}C_{2n}^n$ */ /** Expansion issues: 1 Matrix multiplication problem: $p = a_ 1 * a_ 2 * a_ 3 * ... * a_ According to the law of multiplicative combination, n $does not change the mutual order of matrices, and only brackets represent paired products. How many bracketed schemes are there? The left bracket is equivalent to 1 and the right bracket is equivalent to 0. It is essentially a Cartland number 2 The division of polygons is called triangle problem. Find the number of methods for dividing a convex polygon region into a triangle region. We start from node 1. In order to divide into triangular areas, node 1 cannot be connected with its adjacent nodes, so node 1 can connect 3, 4 n-1 Assuming that node 1 connects i, this line divides the polygon region into i convex polygon and N+2-i convex polygon, that is, $f for node 1_ 1(n) = f(3)*f(n+2-3) + ... + f(n-1)f(3)$ The total segmentation method is $N*f_1(n) $, half of which are duplicates $$f(n) = \sum_{i=3}^{n-1}f(i)*f(n+2-i)*\frac{n}{2}$$ 3 A resident of a city needs to walk 2n blocks to work every day (he works n blocks north and N blocks east of his residence). If he never crosses the diagonal from home to the company, how many possible paths are there? Conform to Cartland number 4 Select 2n points on the circle, connect these points in pairs, and find the number of methods to make the obtained N line segments disjoint? Similar to expansion 2 5 n How many different binary trees can a node construct? n = 0 , f(0) = 1 n = 1 , f(1) = 1 n = 2 , f(2) = 4 $$f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(i)*f(n-i-1) + ... + f(n-1) * f(0)$$ Where $f(i)*f(n-i-1) represents the number that can be constructed when the left subtree has I nodes and the right subtree has n-i-1 nodes$ Conform to Cartland number */ } }