算法题01：递归：红篮球问题

递归：红篮球问题"/>

算法题01：递归：红篮球问题

将 m ≥ 0 m\ge 0 m≥0 个同样的红球， n ≥ 0 n\ge0 n≥0 个同样的蓝球排成一行。对排法要求如下：任意某个蓝球左侧的红球个数大于等于其左侧的蓝球个数加1（即蓝球个数计数时包含当前蓝球），例如：下列合法的排法1中，从左数到的第1个蓝球左侧有2个红球，所以满足 2 ≥ 1 2\ge 1 2≥1;且数到的第2个蓝球左侧有2个红球，满足 2 ≥ 2 2\ge2 2≥2，所以是合法排列。

例如

• 合法的排法1： ◯ ◯ ◯ ◯ \textcolor{red}{\bigcirc} \textcolor{red}{\bigcirc} \textcolor{blue}{\bigcirc} \textcolor{blue}{\bigcirc} ◯◯◯◯

• 合法的排法2： ◯ ◯ ◯ ◯ \textcolor{red}{\bigcirc} \textcolor{blue}{\bigcirc} \textcolor{red}{\bigcirc} \textcolor{blue}{\bigcirc} ◯◯◯◯

• 非法排列: ◯ ◯ ◯ ◯ \textcolor{red}{\bigcirc} \textcolor{blue}{\bigcirc} \textcolor{blue}{\bigcirc}\textcolor{red}{\bigcirc} ◯◯◯◯

总共有多少种合法的排法方式（分析递归表达式，要写出分析过程）。

解答：

写出递归表达式和分析

A = { A ( 0 , n ) = 0 for  n ≥ 0 A ( m , 0 ) = 1 for  m ≥ 1 A ( m , 1 ) = m for  m ≥ 1 A ( m , n ) = 0 for  m < n A ( m , n ) = A ( m , n − 1 ) + A ( m − 1 , n ) for  m ≥ n A=\left\{\begin{array}{lll} A(0,n)=0 & \text { for } & n\geq 0 \\ A(m,0)=1 & \text { for } & m\geq 1 \\ A(m,1)=m & \text { for } & m\geq1 \\ A(m,n)=0 & \text { for } & m < n \\ A(m,n)=A(m,n-1)+A(m-1,n) & \text{ for } & m\geq n\\ \end{array}\right. A=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​A(0,n)=0A(m,0)=1A(m,1)=mA(m,n)=0A(m,n)=A(m,n−1)+A(m−1,n)​ for  for  for  for  for ​n≥0m≥1m≥1m<nm≥n​

对于A(0,n) = 0 , n>=0

​ //因为没有红球，所以必然没有一种排列合法

对于A(m,0) = 1 , m>=1

//因为没有蓝球，所以合法排列为一种，全为红排列

对于A(m,1) = m , m>=1

//当m=1时，A(1,1) = 1=m ,当m>1时，在m+1个位置上，只有第一个位置不能放蓝球，所以合法排列为 m+1 -1=m

对于A(m,n) = 0 , m< n

//红球个数小于蓝球时，设任意某个蓝球左侧的红球为m₀个，必然有m₀<=m，无论任何一种排列，对其从右到左的第一个蓝球，必有其左侧+1蓝球数为n, 显然 m₀<=m<n,所以合法排列为0种。

对于A(m,n) = A(m, n-1)+ A(m-1, n) , m>=n

//把A(m,n)排列理解为在已有的合法排列的最后加上一个球，则有两种必不重复的排法，一、加红球，二、加蓝球。那么，只需将两种情况相加即可。也就是A(m,n) = 少一个红球的情况+少一个蓝球的情况。然后对应的两种情况又继续按上面的理解，递归到前一项，直到最开始的限制条件。

​ 这个题做了很久都是因为还没有习惯递归的思维，总是想的很复杂，想着找红球蓝球的位置的特征：比如在排列后面加红球必然合法等等，思维局限在通过找合法的排列来找到前一项与后一项的关系，然而递归的思想是"假设"前一项成立，直接找先后两项的关系，自己下套把自己整蒙了。本来想着先分类写几项，结果A(4,3)就已经有很多了，但是在写的时候也有刻意掺杂递归的思想来排列，所以在写排列的时候观察到了一些规律，受到了启发。