当前位置：网站首页>[combinatorics] recursive equation (example 1 of recursive equation | list recursive equation)

[combinatorics] recursive equation (example 1 of recursive equation | list recursive equation)

2022-07-03 16:41:00 【Programmer community】

List of articles

One 、 Examples of recursive equations 1
Two 、 Summary of recursive equation examples

One 、 Examples of recursive equations 1

The coding system uses

$8$ Hexadecimal Numbers , Code the information ,

$8$ Hexadecimal digits can only be taken

0,1,2,3,4,5,6,7

$0, 1, 2, 3, 4, 5, 6, 7$ ,

Only when a code contains Even number

$7$ when , This code is valid ,

seek

$n$ The number of valid codes in the coding of bits ?

analysis :

$n$ Bit length encoding , Sure from

−

n-1

$n - 1$ Bit length encoding , Followed by a

$8$ Hexadecimal Numbers constitute ;

For each

−

n-1

$n - 1$ Bit length encoding , Add a digit after it , Make the final coding Satisfy Requirements for effective coding , It contains an even number

$7$ , You can get an effective

$n$ Bit length encoding ;

1 . set up

$n$ The number of effective codes of bit length is

a_n

$a_{n}$ individual ;

Then there are

−

n-1

$n - 1$ The number of effective codes of bit length is

−

a_{n-1}

$a_{n - 1}$ individual ;

Now consider

$n$ Bit length encoding And

−

n-1

$n - 1$ The correlation between bit length codes ;

( 1 ) Even number

$7$ : Suppose there is already one

−

n-1

$n - 1$ Bit long

$8$ Hexadecimal encoding string , It happens to contain an even number

$7$ , That is, the code has met the requirements of effective coding , Add a digit :

Figures that cannot be added : Cannot add
Numbers that can be added : Can only add
$7$ Ways of planting ;

By a

−

n-1

$n - 1$ Bit long , Code that meets the requirements , Yes

$7$ There are ways to generate one

$n$ Bit length encoding ;

( 2 ) An odd number

$7$ : Suppose there is already one

−

n-1

$n - 1$ Bit long

$8$ Hexadecimal encoding string , It happens to contain an odd number

$7$ , That is, the code does not meet the requirements of effective coding , Add a digit :

Figures that cannot be added : Cannot add
Numbers that can be added : Can only add
$7$ , Become a valid code ;

By a

−

n-1

$n - 1$ Bit long , Codes that do not meet the requirements , Yes

$1$ There are ways to generate one

$n$ Bit length encoding ;

3 . Total number

−

8^{n-1}

$8^{n - 1}$ :

−

n-1

$n - 1$ The total number of bit length encodings is

−

8^{n-1}

$8^{n - 1}$ individual , Every position has

$8$ Two possible options , Yes

−

n-1

$n - 1$ A place ;

It can also be expressed as :

−

n-1

$n - 1$ Bits long include , An odd number

$7$ , Even number

$7$ , The total number of codes is

−

8^{n-1}

$8^{n - 1}$

If there is no

$7$ , yes

$0$ individual

$7$ , Count even numbers

$7$ ;

4 .

−

n-1

$n - 1$ The effective number of bit codes

−

a_{n-1}

$a_{n - 1}$ :

−

n-1

$n - 1$ In a , Even number

$7$ The number of , Is the number of effective codes , That is, the above hypothetical

“ set up

$n$ The number of effective codes of bit length is

a_n

$a_{n}$ individual ” , Then there are

−

n-1

$n - 1$ The number of effective codes of bit length is

−

a_{n-1}

$a_{n - 1}$ individual "

5 .

−

n-1

$n - 1$ Invalid number of bit codes

−

8^{n-1} - a_{n-1}

$8^{n - 1} - a_{n - 1}$ :

−

n-1

$n - 1$ Bits long include An odd number

$7$ , Even number

$7$ Of The total number of codes is

−

8^{n-1}

$8^{n - 1}$

−

n-1

$n - 1$ In a , Even number

$7$ The number of , Namely Number of valid codes , That is, the above hypothetical

−

a_{n-1}

$a_{n - 1}$

−

n-1

$n - 1$ In a , An odd number

$7$ The number of , Is the number of invalid codes , The aforementioned Subtract the number of effective codes from the total number , The result is :

−

8^{n-1} - a_{n-1}

$8^{n - 1} - a_{n - 1}$

6 . Analysis section

$n$ Item and

−

n-1

$n - 1$ The relationship between items , namely

$n$ Number of bit effective codes And

−

n-1

$n - 1$ Number of bit effective codes :

The number of adding methods corresponding to the number of effective codes :

−

n-1

$n - 1$ The effective number of bit codes

−

a_{n-1}

$a_{n - 1}$ , Contains an even number of

$7$ , Each valid code , Add one digit , form

$n$ Bit valid encoding , Yes

$7$ Corresponding addition methods , Add

0,1,2,3,4,5,6

$0, 1, 2, 3, 4, 5, 6$ Numbers , Seven ways ; The number of methods is

−

7a_{n-1}

$7 a_{n - 1}$

The number of adding methods corresponding to the number of invalid codes :

−

n-1

$n - 1$ Invalid number of bit codes

−

8^{n-1} - a_{n-1}

$8^{n - 1} - a_{n - 1}$ , There are also odd numbers

$7$ , Each invalid code , Only one number can be added

$7$ , form

$n$ Bit valid encoding , There is only one way ; The number of methods is

−

8^{n-1} - a_{n-1}

$8^{n - 1} - a_{n - 1}$

So here we can write

$n$ The effective number of bit codes

a_n

$a_{n}$ And

−

n-1

$n - 1$ Effective number of bit codes

−

a_{n-1}

$a_{n - 1}$ The relationship between :

a_n

$a_{n}$

$=$

−

7a_{n-1}

$7 a_{n - 1}$

$+$

−

8^{n-1} - a_{n-1}

$8^{n - 1} - a_{n - 1}$

After simplification, we get :

a_n

$a_{n}$

$=$

−

6a_{n-1}

$6 a_{n - 1}$

$+$

−

8^{n-1}

$8^{n - 1}$

7 . Initial value discussion

If only

$1$ Bit code , It can't be

$7$ , This will contain an odd number (

$1$ individual )

$7$ , Is an invalid code ;

Can only be

0,1,2,3,4,5,6

$0, 1, 2, 3, 4, 5, 6$ this

$7$ Kind of , So there is

$1$ Bit encoding , The number of effective codes is

$7$ individual ,

produce Initial value of recurrence equation

a_1 = 7

$a_{1} = 7$

8 . The resulting recursive equation :

Recurrence equation :

a_n

$a_{n}$

$=$

−

6a_{n-1}

$6 a_{n - 1}$

$+$

−

8^{n-1}

$8^{n - 1}$

initial value :

a_1 = 7

$a_{1} = 7$

The general term formula for solving the above recursive equation :

a_n = \cfrac{6^n + 8^n}{2}

$a_{n} = \frac{6 ^{n} + 8 ^{n}}{2}$

Two 、 Summary of recursive equation examples

This problem is a specific counting problem , The above problem is not simply counting ,

This count has parameters

$n$ ,

This type of counting , Can be seen as a Sequence count result ,

If you can find the sequence , consequent , the aforesaid , Dependency of ,

And know initial value ,

Can Solve the general term formula of the sequence ,

The general term formula just corresponds to the counting result ;

原网站

版权声明
本文为[Programmer community]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202150426447898.html

当前位置：网站首页>[combinatorics] recursive equation (example 1 of recursive equation | list recursive equation)

[combinatorics] recursive equation (example 1 of recursive equation | list recursive equation)

List of articles

One 、 Examples of recursive equations 1

Two 、 Summary of recursive equation examples

边栏推荐

猜你喜欢

随机推荐