?

?

一. 錯排

?

1.計算公式：

1） D[n] = (n-1)*(D[n-1]+D[n-2])?，n>=2, D[0] = 1, D[1] = 0 。

解釋：對于第n個要加入錯排的數，它可以和已經錯排的n-1個數的其中一個進行交換，構成錯排，于是又 (n-1)*D[n-1]；此外，第n個數還可以與n-1個數中唯一一個沒有加入錯排的數（n-2個構成錯排，剩下一個待定）進行交換，這樣就構成了n錯排，而這n-1個數之中，每個數都可以作為那個唯一一個沒有加入錯排的數，故(n-1)*D[n-2]。所以 D[n] = (n-1)*(D[n-1]+D[n-2])。

?2） A[n] - sigma(C[n][k]*A[n-k])， 1<=k<=n，容斥原理。

?

2.題目：

HDU1465 不容易系列之（全錯排）

HDU2049 不容易系列之(4)考新郎（部分錯排）

HDU2068 RPG的錯排

Codeforces Round #198 (Div. 2) E. Iahub and Permutations（限定條件下的錯排）

?

?

?

二.卡特蘭數

卡特蘭數的初步學習，卡特蘭數多種模型?。

?

1.卡特蘭數計算公式：

?1） h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (n>=1) ， 其中 h[0] = 1；

?2） h(n) = c(2n,n) - c(2n,n+1)(n=0,1,2,...) <==>?h(n) = C(2n,n)/(n+1)

?3） h(n) = h(n-1)*(4*n-2) / (i+1)? ……此條計算公式容易溢出

3.注意：卡特蘭數的計算很容易溢出。

?

2.題目：

HDU2067 小兔的棋盤

HDU1133 Buy the Ticket?

HDU3723 Delta Wave

?

?

?

三.第一類斯特林數

?

1. 定義：n個人（有區別）圍成m個圈（無區別）的方案數。

?

2. 計算公式：S[n][m] = S[n-1][m-1] + (n-1)*S[n-1][m]

解釋：第n個人要加入進去，那么他有兩種選擇：一是自己作為一圈，那么有S[n-1][m-1]種情況；二是加入已存在的圈子中，那么他有n-1種站位方式（可以想象成站在某個人的左邊），所以有?(n-1)*S[n-1][m]種情況。所以總的方案數為：S[n][m] = S[n-1][m-1] + (n-1)*S[n-1][m] 。

?

3. 題目：

HDU4372 Count the Buildings

?

?

?

四.第二類斯特林數

?

1.定義：將n個不同的球放入m個無差別的盒子中，要求盒子非空，有幾種方案？

?

2.計算公式：S(n+1, m) = S(n, m-1) + m*S(n, m)

解釋：假設要把n個元素分成m個集合。如果n-1個元素構成了m-1個集合，那么第n個元素單獨構成一個集合。方案數為 S ( n-1, m-1 )。如果n個元素已經構成了m個集合，將第n+1個元素插入到任意一個集合。方案數 m * S ( n-1, m ) 。綜合兩種情況得：?S ( n+1, m ) = S ( n, m-1 ) + m * S ( n, m )?。

?

3.幾種變形：

第二類Stirling數主要是用于解決組合數學中的幾類放球模型。主要是針對于球之前有區別的放球模型： （1）n個不同的球，放入m個無區別的盒子，不允許盒子為空。 方案數：? ?S ( n, m ) 。這個跟第二類Stirling數的定義一致。 （2）n個不同的球，放入m個有區別的盒子，不允許盒子為空。 方案數：? m! * S ( n, m ) 。因盒子有區別，乘上盒子的排列即可。 （3）n個不同的球，放入m個無區別的盒子，允許盒子為空。 方案數：?sigma ( S ( n, k ) )， 0<=k<=m。枚舉非空盒的數目便可。 （4）n個不同的球，放入m個有區別的盒子，允許盒子為空。 ①方案數：?sigma ( P( m, k ) * S( n, k )? )， 0<=k<=m。同樣可以枚舉非空盒的數目，注意到盒子有區別，乘上一個排列系數。 ②既然允許盒子為空，且盒子間有區別，那么對于每個球有m中選擇，每個球相互獨立。有方案數：? m^n 。 4.題目：

HDU2512 一卡通大冒險?

HDU4045 Machine scheduling

Gym - 101147G G - The Galactic Olympics

?

轉載于:https://www.cnblogs.com/DOLFAMINGO/p/8336472.html

總結

以上是生活随笔為你收集整理的错排、卡特兰数、斯特林数小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。