当前位置：网站首页>[combinatorics] non descending path problem (outline of non descending path problem | basic model of non descending path problem | non descending path problem expansion model 1 non origin starting poi

[combinatorics] non descending path problem (outline of non descending path problem | basic model of non descending path problem | non descending path problem expansion model 1 non origin starting poi

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

List of articles

One 、 Non descending path problem A synopsis
Two 、 Non descending path problem Basic model
Two 、 Non descending path problem Expand the model 1
3、 ... and 、 Non descending path problem Expand the model 2

Combinatorial identity reference blog :

【 Combinatorial mathematics 】 Binomial theorem and combinatorial identities ( binomial theorem | Three combinatorial identities recursion | recursion 1 | recursion 2 | recursion 3 Pascal / Yang Hui's trigonometric formula | Combination analysis method | Characteristics of recursive combinatorial identities )
【 Combinatorial mathematics 】 Combinatorial identity ( Recurrence Combinatorial identity | Change the next term to sum Combinatorial identity Simple and | Change the next term to sum Combinatorial identity Staggered and )
【 Combinatorial mathematics 】 Combinatorial identity ( Change the next term to sum 3 Combinatorial identity | Change the next term to sum 4 Combinatorial identity | binomial theorem + Derivation Prove the combinatorial identity | Use known combinatorial identities to prove combinatorial identities )
【 Combinatorial mathematics 】 Combinatorial identity ( Review of eight combinatorial identities | Combinatorial identity product 1 | prove | Use scenarios )
【 Combinatorial mathematics 】 Combinatorial identity ( Combinatorial identity Sum of product 1 | Sum of product 1 prove | Combinatorial identity Sum of product 2 | Sum of product 2 prove )

One 、 Non descending path problem A synopsis

Non descending path problem It is a combined counting model , Using this combined counting model , It can deal with some common combination counting problems ;

Non descending path problem :

( 1 ) Basic model

( 2 ) The number of non descending paths under limited conditions

( 3 ) Application of non descending path model

① Proof identity
② Monotone function count
③ Stack output

Two 、 Non descending path problem Basic model

Insert picture description here

Calculation from

(

)

(0,0)

$(0, 0)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths ?

1 . Non descending path requirements :

starting point : from

(

)

(0,0)

$(0, 0)$ set out ;

Moving coordinate requirements : turn right Integer coordinates , Both horizontal and vertical coordinates go Integer length ;

The direction of movement requires : Only right at a time , Or move up ; Not to the left , Go down ;

2 . Turn to the selection question : Turn it into a selection problem ,

Step analysis : from

(

)

(0,0)

$(0, 0)$ To

(

)

(m, n)

$(m, n)$ , Go to the right

$m$ Step , Go up

$n$ Step ;

Select the problem description : All in all

m+n

$m + n$ Step , You need to choose those steps up , Which steps to the right , As long as it is in the sum

m + n

$m + n$ In step , Turn to the right

$m$ After all steps are calibrated , The rest is the upward step ;

Select the number of problem combinations to calculate : So here's just from

m+n

$m + n$ Select

$m$ Step by step , The result is

(

)

C(m+n, m)

$C (m + n, m)$ , It can be written again

(

)

\dbinom{m + n}{m}

$(m m + n)$

Two 、 Non descending path problem Expand the model 1

Calculation from

(

)

(a,b)

$(a, b)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths ?

Above from

(

)

(a,b)

$(a, b)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths ,

be equal to

from

(

)

(0,0)

$(0, 0)$ To

(

−

)

(m-a, n-b)

$(m - a, n - b)$ The number of non descending paths ;

Coordinate translation : The above principle is Coordinate translation , Set the overall coordinates Pan left

$a$ , Translate down

$b$ , You can get from

(

)

(0,0)

$(0, 0)$ To

(

−

)

(m-a, n-b)

$(m - a, n - b)$ Of Basic model of non descending path problem ;

therefore from

(

)

(a,b)

$(a, b)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths is

(

−

)

C(m-a + n-b , m-a)

$C (m - a + n - b, m - a)$ strip ;

3、 ... and 、 Non descending path problem Expand the model 2

Calculation from

(

)

(a,b)

$(a, b)$ after

(

)

(c, d)

$(c, d)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths ?

1 . Description of calculation process :

( 1 ) Step by step processing : Use Step by step counting principle , Corresponding multiplication rule ;

( 2 ) First step : First calculate from

(

)

(a,b)

$(a, b)$ To

(

)

(c, d)

$(c, d)$ The number of non descending paths ;

( 3 ) The second step : And then calculate from

(

)

(c, d)

$(c, d)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths ;

( 4 ) product rule : According to the law of multiplication , Multiply the above two results , The final result is the number of non descending paths required by the result ;

2 . The first step in the calculation

Calculate from

(

)

(a,b)

$(a, b)$ To

(

)

(c, d)

$(c, d)$ The number of non descending paths , Before substituting The formula

from
(
a
,
b
)
(a,b)
$(a, b)$ To
(
m
,
n
)
(m, n)
$(m, n)$ The number of non descending paths is
C
(
m
−
a
+
n
−
b
,
m
−
a
)
C(m-a + n-b , m-a)
$C (m - a + n - b, m - a)$ strip

The result is :

(

−

)

C(c-a + c-b , c-a)

$C (c - a + c - b, c - a)$

3 . Calculate the second step

Calculate from

(

)

(c,d)

$(c, d)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths , Before substituting The formula

from
(
a
,
b
)
(a,b)
$(a, b)$ To
(
m
,
n
)
(m, n)
$(m, n)$ The number of non descending paths is
C
(
m
−
a
+
n
−
b
,
m
−
a
)
C(m-a + n-b , m-a)
$C (m - a + n - b, m - a)$ strip