【数学建模】（LeetCode 1227）小鸟回笼/飞机座位问题

题目

有 nnn 只小鸟，各有自己的笼子（编号 1,2,⋯ ,n1, 2, \cdots, n1,2,⋯,n）。第一天，第一只小鸟（编号 1）没有回到自己的笼子（笼 1），而是随机进了其它某个笼子。后续的小鸟每天回来时，如果自己的笼子空着就进自己的笼子，否则从剩下的空笼子中随机选一个。

问：最后一只回笼的小鸟回到自己笼子的概率是多少？

这个问题和经典的飞机座位问题等价（见下），但需要注意的时初始条件不同，下面的问题第一个人位置也是随机的（可能回到自己的位置），而上面小鸟回笼问题则是在没有回到自己的笼子情况下。

有nnn位乘客即将登机，飞机正好有nnn个座位。第一位乘客的票丢了，他随便选了一个座位坐下。剩下的乘客将会：如果他们自己的座位还空着，就坐到自己的座位上；当他们自己的座位被占用时，随机选择其他座位，问：

第nnn位乘客坐在自己的座位上的概率是多少？

解答

**解：**设当所有鸟回到笼子后鸟和笼子编号的映射为
f(n)=m f(n) = m f(n)=m
其中nnn为鸟的编号，mmm为笼子编号，

显然，

• 当n=1n=1n=1时，第111只鸟即为最后一只鸟，因此其回到自己的鸟笼的概率为P=1P=1P=1；
• 当n=2n=2n=2时，第111只鸟因为没有回到自己的笼子，必然选择了第222只鸟即最后一只回笼小鸟所属的笼子，因此最后一只回笼小鸟回到自己的笼子的概率为P=0P=0P=0。

下面讨论当n≥3n\geq3n≥3时的情况，显然：

• f(1)≠1f(1)\neq1f(1)=1;
• 若最后一只鸟回到自己的笼子，有f(n)=nf(n)=nf(n)=n，否则f(n)≠nf(n)\neq nf(n)=n。

再设当第iii只鸟回到笼子时（1<i<n1<i<n1<i<n），剩下还没有鸟回笼的笼子编号集合为Cil\mathbb{C}^l_iCil​，剩下的鸟所属的笼子编号的集合为Cib={i,i+1,⋯ ,n}\mathbb{C}_i^b = \{i,i+1,\cdots,n\}Cib​={i,i+1,⋯,n}。设
f(1)=k,k≠1 f(1)=k,\quad k\neq1 f(1)=k,k=1
若k=nk=nk=n，则第nnn只鸟必然无法回到自己的笼子；当k≠nk\neq nk=n时，考虑第kkk只鸟回笼时，会发生如下情况：

• f(j)=j, 1<j<kf(j)=j,\ 1<j<kf(j)=j, 1<j<k;
• Ckl={1,k+1,k+2,⋯ ,n}\mathbb{C}^l_k=\{1,k+1,k+2,\cdots,n\}Ckl​={1,k+1,k+2,⋯,n}，共n−k+1n-k+1n−k+1项。

显然，这一系列事件发生概率是由f(1)=kf(1)=kf(1)=k直接导致的，设此事件发生的概率为Pk=1n−1P_k=\dfrac{1}{n-1}Pk​=n−11​，此时第kkk只鸟必须从Ckl={1,k+1,⋯ ,n}\mathbb{C}^l_k=\{1,k+1,\cdots,n\}Ckl​={1,k+1,⋯,n}中随机选择一个笼子回笼，会出现三种情况：

• 选择笼子111回笼，则从i>ki>ki>k开始，第iii只鸟的笼子都没有被占，后续所有鸟都会回到自己的笼子，这个事件发生的概率为Pk1=Pk⋅1n−i+1P^{1}_k=P_k\cdot\dfrac{1}{n-i+1}Pk1​=Pk​⋅n−i+11​；
• 选择笼子nnn回笼，则第nnn只鸟因为自己的笼子已被占，因此必然无法回到自己的笼子，这个事件发生的概率也为Pkn=Pk⋅1n−i+1P^n_k=P_k\cdot\dfrac{1}{n-i+1}Pkn​=Pk​⋅n−i+11​；
• 选择笼子k+lk+lk+l回笼，则当第k+lk+lk+l只鸟回笼时，Ck+ll={1,k+l+1,k+l+2,⋯ ,n}\mathbb{C}^l_{k+l}=\{1,k+l+1,k+l+2,\cdots,n\}Ck+ll​={1,k+l+1,k+l+2,⋯,n}，显然第k+lk+lk+l只鸟回笼选择笼子的情况和第kkk只鸟相同，发生了一个递归过程。

这里可以定性的分析出，不论在哪个递归的分支，都有P1=PnP^1=P^nP1=Pn，即当笼子被占用的鸟随机选择笼子时，选择笼子111和nnn会直接决定第nnn只鸟能否回到自己的笼子，而这两种结果的概率是永远相等的。因此当f(1)=k,k≠1,k≠nf(1)=k,k\neq1,k\neq nf(1)=k,k=1,k=n时，第nnn只鸟能回到自己笼子的概率为Pks=12⋅PkP^s_k=\dfrac{1}{2}\cdot P_kPks​=21​⋅Pk​，利用全概率公式，最终概率为
P=∑k=2n−212⋅Pk=n−22(n−1) P=\sum_{k=2}^{n-2}\dfrac{1}{2}\cdot P_k=\frac{n-2}{2(n-1)} P=k=2∑n−2​21​⋅Pk​=2(n−1)n−2​
综上，最后一只鸟回到自己的鸟笼的概率为
P={1,n=10,n=2n−22(n−1),n≥3 P=\begin{cases} 1,&n=1\\ 0,&n=2\\ \dfrac{n-2}{2(n-1)},&n\geq 3 \end{cases} P=⎩⎨⎧​1,0,2(n−1)n−2​,​n=1n=2n≥3​

和经典问题的区别

在飞机座位问题中，由于第一个人也是随机选择的，迭代可以从第一个乘客开始，因此最终答案为
P=12 P=\frac{1}{2} P=21​

进一步地分析，如果我们从第一只鸟开始迭代（即第一只鸟是随机选择自己的鸟笼的），有如下情况:

• 显然当n=1n=1n=1，P=1P=1P=1；
• 显然当n=2n=2n=2，P=12P=\dfrac{1}{2}P=21​；
• 显然当n≥3n\geq 3n≥3，有：
  • 若f(1)=nf(1)=nf(1)=n，则最后一只鸟必然无法回到自己的笼子中；
  • 若f(1)=1f(1)=1f(1)=1，则后续回笼的鸟都能回到自己的笼子；
  • 设总共有nnn只鸟时，最后一只鸟能回到自己鸟笼的事件为AnA_nAn​，若f(1)=k,1<k<nf(1)= k, 1<k<nf(1)=k,1<k<n，则当第kkk只鸟进行选择时，其实际上面对的是一个n−k+1n-k+1n−k+1规模的同样的问题，因此有

P(An)=P[f(1)=1]+P[f(1)≠1,n]⋅∑k=2n−1P(An−k+1=1n+1n∑k=2n−1P(An−k+1) P(A_n)=P[f(1)=1]+P[f(1)\neq 1,n]\cdot\sum_{k=2}^{n-1}P(A_{n-k+1}=\frac{1}{n}+\frac{1}{n}\sum_{k=2}^{n-1}P(A_{n-k+1}) P(An​)=P[f(1)=1]+P[f(1)=1,n]⋅k=2∑n−1​P(An−k+1​=n1​+n1​k=2∑n−1​P(An−k+1​)

可以递推出P(A2)=P(A3)=12P(A_2)=P(A_3)=\dfrac{1}{2}P(A2​)=P(A3​)=21​，用数学归纳法，假设n≥3n\geq 3n≥3时，P(An)=12P(A_n)=\dfrac{1}{2}P(An​)=21​，则
P(An+1)=1n+1+1n+1⋅(n−1)⋅12=12 P(A_{n+1}) = \frac{1}{n+1}+\frac{1}{n+1}\cdot(n-1)\cdot\frac{1}{2}=\frac{1}{2} P(An+1​)=n+11​+n+11​⋅(n−1)⋅21​=21​
这和经典问题是相同的。综上，
P(An)={1,n=112,n≥2 P(A_n)=\begin{cases} 1,&n=1\\ \dfrac{1}{2},&n\geq 2 \end{cases} P(An​)=⎩⎨⎧​1,21​,​n=1n≥2​

小鸟回笼问题事实上是第一只鸟没有选择笼子111的条件BBB下（对应地第一只鸟选择笼子111的条件为Bˉ\bar{B}Bˉ），事件AnA_nAn​发生的概率P(An∣B)P(A_n|B)P(An​∣B)。根据上述讨论结果，显然
P(AnBˉ)=1n P(A_n\bar{B}) = \frac{1}{n} P(An​Bˉ)=n1​
最后一只鸟能回到自己笼子事件AAA发生的概率，其中
P(AnB)=P(An)−P(AnBˉ)=12−1n=n−22n P(A_nB)=P(A_n)-P(A_n\bar{B})=\frac{1}{2}-\frac{1}{n}=\frac{n-2}{2n} P(An​B)=P(An​)−P(An​Bˉ)=21​−n1​=2nn−2​
则
P(An∣B)=P(AnB)P(B)=n−22nn−1n=n−22(n−1) P(A_n|B) = \frac{P(A_nB)}{P(B)}=\frac{\dfrac{n-2}{2n}}{\dfrac{n-1}{n}}=\frac{n-2}{2(n-1)} P(An​∣B)=P(B)P(An​B)​=nn−1​2nn−2​​=2(n−1)n−2​
因此两个问题本质是相同的，只是小鸟回笼问题多了一个条件，在这个条件下，最后一只鸟回到自己的笼子的概率就发生变化了。

代码验证

本题小鸟回笼C++验证代码如下：

#include<bits/stdc++.h>usingnamespace std;staticboolone_trial(int n, mt19937 &rng){// occupied[cage] = bird occupying it (1..n), 0 means empty vector<int>occupied(n +1,0);// list of empty cages + position map for O(1) erase vector<int> empty; empty.reserve(n);for(int c =1; c <= n;++c) empty.push_back(c); vector<int>pos(n +1,-1);for(int i =0; i < n;++i) pos[empty[i]]= i;auto erase_empty =[&](int cage){int idx = pos[cage];int last = empty.back(); empty[idx]= last; pos[last]= idx; empty.pop_back(); pos[cage]=-1;};auto occupy =[&](int bird,int cage){ occupied[cage]= bird;erase_empty(cage);};auto pick_from_empty =[&](int m)->int{ uniform_int_distribution<int>dist(0, m -1);return empty[dist(rng)];};if(n ==1){occupy(1,1);returntrue;// bird 1 is also the last one}// Bird 1: must NOT choose cage 1, choose uniformly from {2..n}// Since all cages are empty now, we can sample an integer in [2,n]. uniform_int_distribution<int>dist_first(2, n);int cage1 =dist_first(rng);occupy(1, cage1);// Birds 2..nfor(int bird =2; bird <= n;++bird){if(occupied[bird]==0){occupy(bird, bird);}else{int cage =pick_from_empty((int)empty.size());occupy(bird, cage);}}return occupied[n]== n;}staticdoublesimulate(int n,int trials,uint32_t seed){ mt19937 rng(seed);int success =0;for(int t =0; t < trials;++t){if(one_trial(n, rng)) success++;}return(double)success / trials;}staticdoubletheory(int n){if(n ==1)return1.0;if(n ==2)return0.0;return(n -2)/(2.0*(n -1));}intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector<int> ns ={1,2,3,4,5,10,20,50,100};int trials =200000;// 可调大：1e6 会更准但更慢uint32_t seed =42; cout <<"Trials per n = "<< trials <<"\n";for(int n : ns){double est =simulate(n, trials, seed);double th =theory(n); cout <<"n="<<setw(3)<< n <<" est="<< fixed <<setprecision(5)<< est <<" theory="<< fixed <<setprecision(5)<< th <<"\n";}return0;}

经典问题验证代码如下：

#include<bits/stdc++.h>usingnamespace std;booltrial(int n, mt19937 &rng){ vector<int>occupied(n +1,0); vector<int> empty; empty.reserve(n);for(int c =1; c <= n;++c) empty.push_back(c); vector<int>pos(n +1,-1);for(int i =0; i < n;++i) pos[empty[i]]= i;auto occupy =[&](int bird,int cage){ occupied[cage]= bird;int idx = pos[cage];int last = empty.back(); empty[idx]= last; pos[last]= idx; empty.pop_back(); pos[cage]=-1;};auto choice_index =[&](int m){ uniform_int_distribution<int>dist(0, m -1);returndist(rng);};// bird 1int cage1 = empty[choice_index((int)empty.size())];occupy(1, cage1);// birds 2..nfor(int bird =2; bird <= n;++bird){if(occupied[bird]==0){occupy(bird, bird);}else{int cage = empty[choice_index((int)empty.size())];occupy(bird, cage);}}return occupied[n]== n;}doublesimulate(int n,int T,uint32_t seed=42){ mt19937 rng(seed);int success =0;for(int t =0; t < T;++t){if(trial(n, rng)) success++;}return(double)success / T;}intmain(){ vector<int> ns ={1,2,3,4,5,10,50,100};int T =200000;for(int n : ns){double est =simulate(n, T); cout <<"n="<<setw(3)<< n <<", estimated P="<< fixed <<setprecision(4)<< est <<"\n";}}

常见误区

以下是一种常见的错误解法，主要问题在于遗漏了“如果自己的笼子空着就进自己的笼子”这一条件，因此独立地计算了每只鸟回笼的概率，实际上编号靠前的鸟回笼的选择会影响后续鸟的策略，因此各个事件不是相互独立的。

**解：**显然n=1n=1n=1时，第一只鸟就是最后一只鸟，其回到自己笼子的概率为
P=1 P=1 P=1

最后一只鸟能回到鸟笼的情况需要以下两个条件：

1. 第一只鸟在没有进入自己鸟笼的前提下没有进到最后一只鸟的鸟笼中；
2. 剩下的鸟都没有进到最后一只鸟的鸟笼中。

n=2n=2n=2时，第一只鸟没有回到自己的笼子，必然进入了最后一只鸟的笼子，因此最后一只鸟回到自己笼子的概率为

P=0 P=0 P=0

n>2n>2n>2时，对于第一个条件，有一个前提是第一只鸟没有进入自己的鸟笼，因此其是在剩下的n−1n-1n−1个鸟笼中随机选择一个，其不选到最后一只鸟的概率为：

P1=n−2n−1 P_1 = \frac{n-2}{n-1} P1​=n−1n−2​

对于第二个条件，即前面的鸟都没有选到最后一个鸟笼

P2=n−2n−1⋅n−3n−2⋯12=1n−1 P_2 = \frac{n-2}{n-1}\cdot\frac{n-3}{n-2}\cdots\frac{1}{2}=\frac{1}{n-1} P2​=n−1n−2​⋅n−2n−3​⋯21​=n−11​

因此，最终的概率为

P=P1⋅P2=n−2n−1⋅1n−1=n−2(n−1)2 P = P_1\cdot P_2=\frac{n-2}{n-1}\cdot \frac{1}{n-1} = \frac{n-2}{(n-1)^2} P=P1​⋅P2​=n−1n−2​⋅n−11​=(n−1)2n−2​

综上，最后一只鸟回到自己笼子的概率为：

P={1,n=1;n−2(n−1)2,n>1. P = \begin{cases} 1,& n=1;\\ \dfrac{n-2}{(n-1)^2},& n>1. \end{cases} P=⎩⎨⎧​1,(n−1)2n−2​,​n=1;n>1.​