文章目錄

• 一、限制條件的非降路徑數(shù)

一、限制條件的非降路徑數(shù)

---

從 $(0,0)$ 到 $(n,n)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù) ?

此時(shí)無法使用基本公式進(jìn)行處理了 , 必須使用組合對(duì)應(yīng)的思想 ;

上圖示例中 , 從 $(0,0)$ 出發(fā)到 $(n,n)$ , 只有兩個(gè)端點(diǎn) $(0,0)$ 和 $(n,n)$ 接觸了對(duì)角線 , 中間的每一步都沒有接觸該對(duì)角線 ;

1 . 計(jì)算原理 , 先計(jì)算對(duì)角線下方的非降路徑 : 這里只計(jì)數(shù)在對(duì)角線下方的非降路徑數(shù) , 因?yàn)?對(duì)角線上下的非降路徑是對(duì)稱的 , 因此這里 先將對(duì)角線下方的非降路徑計(jì)算出來 ;

對(duì)角線下方的非降路徑 乘以 $2$ , 就是總的 不接觸對(duì)角線的 非降路徑數(shù) ;

2 . 出發(fā)點(diǎn)分析 : 從 $(0,0)$ 出發(fā)后 , 第 $1$ 步必須向右走 , 走到 $(1,0)$ 點(diǎn) , 如果向上走就不能再下來了 ( 否則就會(huì)接觸對(duì)角線 ) , 此時(shí)就不是對(duì)角線下方的非降路徑了 ;

3 . 終止點(diǎn)分析 :

到達(dá) $(n,n)$ 點(diǎn) , 只有兩種情況 :

• 對(duì)角線上方 : 一種情況是從左邊 $(n?1,n)$ 到右邊的 $(n,n)$ 點(diǎn) , 該路徑在對(duì)角線上方 ;
• 對(duì)角線下方 : 一種情況是從下邊 $(n,n?1)$ 到上邊的 $(n,n)$ 點(diǎn) , 該路徑在對(duì)角線下方 ;

由于當(dāng)前只統(tǒng)計(jì) 對(duì)角線下方的非降路徑數(shù) , 到達(dá) $(n,n)$ 之前的一步 , 必須是從 $(n,n?1)$ 位置走到 $(n,n)$ 的 ;

4 . 對(duì)應(yīng)關(guān)系

上述 出發(fā)點(diǎn)之后必須走 $(1,0)$ 點(diǎn) , 終點(diǎn)之前必須走 $(n,n?1)$ 點(diǎn) ,

因此 在對(duì)角線下方 從 $(0,0)$ 到 $(n,n)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)

等價(jià)于

從 $(1,0)$ 到 $(n,n?1)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)

5 . 計(jì)算 $(1,0)$ 到 $(n,n?1)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)

下面討論 “從 $(1,0)$ 到 $(n,n?1)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)” 的計(jì)數(shù)方式 ;

使用反向思路考慮 , 統(tǒng)計(jì) 從 $(1,0)$ 到 $(n,n?1)$ 之間 , 接觸過對(duì)角線的非降路徑 , 剩下的就是不接觸對(duì)角線的路徑 ;

上述兩者的總數(shù)是 $C(2n?2,n?1)$ 個(gè) ;

上圖是 一個(gè) “從 $(1,0)$ 到 $(n,n?1)$ , 接觸過對(duì)角線的非降路徑” ,

圖中的 紅色點(diǎn) $A$ 是該非降路徑最后接觸對(duì)角線的位置 , 前面可能有多次接觸該對(duì)角線 ;

將 $(1,0)$ 點(diǎn) 與 $A$ 點(diǎn) 之間的藍(lán)色線段 , 關(guān)于對(duì)角線作對(duì)稱圖像 , 得到 紅色線段 ,

上圖中的 藍(lán)色線段 起點(diǎn)是 $(1,0)$ , 那么對(duì)應(yīng)的 紅色線段的起點(diǎn)必定是 $(0,1)$ ;

每一條從 $(1,0)$ 開始到 $(n,n?1)$ 的接觸對(duì)角線的非降路徑 , 都有藍(lán)色的線段 , 都可以使用對(duì)稱的方法 , 得到一個(gè) 從 $(0,1)$ 到達(dá) $A$ 點(diǎn)的紅色線段 ;

這里就得到了一個(gè)組合對(duì)應(yīng)關(guān)系 :

每條從 $(0,1)$ 出發(fā) , 到 $(n,n?1)$ 的 非降路徑 ( 即將 紅色的線段 與 剩余的 黑色線段 可以拼接起來的路徑 )

都可以與

從 $(1,0)$ 出發(fā) , 到 $(n,n?1)$ 的接觸對(duì)角線的 非降路徑

一一對(duì)應(yīng) ;

因此如果要求 "從 $(1,0)$ 出發(fā) , 到 $(n,n?1)$ 的接觸對(duì)角線的 非降路徑數(shù) " , 可以通過求 “從 $(0,1)$ 出發(fā) , 到 $(n,n?1)$ 的 非降路徑數(shù)” ;

“從 $(0,1)$ 出發(fā) , 到 $(n,n?1)$ 的 非降路徑數(shù)” 可以使用公式進(jìn)行計(jì)算 , 結(jié)果為 $C(2n?2,n)$ ,

對(duì)應(yīng)的 "從 $(1,0)$ 出發(fā) , 到 $(n,n?1)$ 的接觸對(duì)角線的 非降路徑數(shù) " , 結(jié)果為 $C(2n?2,n)$ ;

6 . 計(jì)算 $(1,0)$ 到 $(n,n?1)$ 的所有非降路徑數(shù)

根據(jù)公式計(jì)算即可 , 結(jié)果是 : $C(2n?2,n?1)$

7 . 計(jì)算 $(1,0)$ 到 $(n,n?1)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)

"$(1,0)$ 到 $(n,n?1)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)" 就是

"$(1,0)$ 到 $(n,n?1)$ 的所有非降路徑數(shù)" 減去 "$(1,0)$ 到 $(n,n?1)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)" ;

$C(2n?2,n?1)?C(2n?2,n)$

$=\left(\genfrac{}{}{0ex}{}{2n?2}{n?1}\right)?\left(\genfrac{}{}{0ex}{}{2n?2}{n}\right)$

8 . 計(jì)算 從 $(0,0)$ 到 $(n,n)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)

上面的 $\left(\genfrac{}{}{0ex}{}{2n?2}{n?1}\right)?\left(\genfrac{}{}{0ex}{}{2n?2}{n}\right)$ 只是計(jì)算的是對(duì)角線下面的非降路徑數(shù) ,

從 $(0,0)$ 出發(fā) , 到 $(n,n)$ 不接觸對(duì)角線的非降路徑數(shù) , 再乘以 $2$ , 就得到了本題目的最終結(jié)果 ;

從 $(0,0)$ 到 $(n,n)$ 除端點(diǎn)外 , 不接觸對(duì)角線的非降路徑數(shù)

最終結(jié)果是 : $2[(\genfrac{}{}{0ex}{}{2n?2}{n?1})?(\genfrac{}{}{0ex}{}{2n?2}{n})]$

總結(jié)

以上是生活随笔為你收集整理的【组合数学】非降路径问题 ( 限制条件的非降路径数 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。