[组合] 多次错排问题

青青子衿

某一天，学校领导检查，抓出了十对情侣，并威胁到不分手就处分；
    第二天，这十对情侣就都分手了；
    第三天，之前的十对情侣重新组合成了新的十对情侣。
    其中，新的十对情侣与最开始十对情侣完全不同，
    即没有一对情侣在检查前后保持一致，都被拆散了。
    （不考虑同性恋的情形）
①那么问题来了，有多少种组合方式？
    一个月后，学校领导又来检查，又抓出了这一批人，
    于是有趣的事情发生了！
    第二次组成的十对情侣又重新组合成了第三次的十对情侣（与之前两次的情形完全不同）。
②那么问题来了，在给定某个第二次所组成十对情侣的情况下，又有多少种组合方式？

zhcosin

第一次被抓重排就是十个人的错位排列问题，答案是现成的，但是第二次被抓嘛。。。。我只想说。。。。我他妈转学行不行？

Infinity

最初编号1到10，这是一种配对情况，第一次被抓时候则是1到10的某个错排$\sigma$，错排方案数为1334961。第二次被抓后，第三次重新组合为$\sigma$的错排，但要排除最初的1到10顺序配对情况，结果就是1334960.

青青子衿

最初编号1到10，这是一种配对情况，第一次被抓时候则是1到10的某个错排$\sigma$，错排方案数为1334961。第二次被抓后，第三次重新组合为$\sigma$的错排，但要排除最初的1到10顺序配对情况，结果就是1334960. ...
Infinity 发表于 2019-5-7 13:47

你没有理解我的意思……

一个月后，学校领导又来抓一次，
第二次组成的十对情侣又重新组合成了第三次的十对情侣（与之前两次的情形完全不同）。 ...
青青子衿 发表于 2019-5-7 11:08

举个例子，先不考虑十对情侣的情形，就拿四对情侣的情形举例：
设原配分别为：AaBbCcDd
经过第一次被抓，有可能出现如下九种情形：
1.AbBaCdDc
2.AbBcCdDa
3.AbBdCaDc
**********
4.AcBaCdDb
5.AcBdCaDb
6.AcBdCbDa
**********
7.AdBaCbDc
8.AdBcCaDb
9.AdBcCbDa
假设经过第一次被抓后组成的第二次四对情侣为：1.AbBaCdDc
那么经过第二次被抓，有可能出现如下四种情形：
.
.
.
**********
.
5.AcBdCaDb
6.AcBdCbDa
**********
.
8.AdBcCaDb
9.AdBcCbDa

青青子衿

一个月后，学校领导又来抓一次，
第二次组成的十对情侣又重新组合成了第三次的十对情侣（与之前两次的情形完全不同）。 ...
青青子衿 发表于 2019-5-7 11:08

补一个LaTeX表格：
\begin{array}{|c|c|c|c|}      
\hline      
1.AbBaCdDc  
&2.AbBcCdDa  
&3.AbBdCaDc  
&4.AcBaCdDb  
&5.AcBdCaDb  
&6.AcBdCbDa  
&7.AdBaCbDc  
&8.AdBcCaDb  
&9.AdBcCbDa\\      
\hline     
1.\color{red}{AbBaCdDc} &1.\color{red}{Ab}Ba\color{red}{Cd}Dc &1.\color{red}{Ab}BaCd\color{red}{Dc} &
1.Ab\color{red}{Ba}\color{red}{Cd}Dc &1.AbBaCdDc &1.AbBaCdDc &
1.Ab\color{red}{Ba}Cd\color{red}{Dc} &1.AbBaCdDc &1.AbBaCdDc \\

2.\color{red}{Ab}Bc\color{red}{Cd}Da &2.\color{red}{AbBcCdDa} &2.\color{red}{Ab}BcCdDa &
2.AbBc\color{red}{Cd}Da &2.AbBcCdDa &2.AbBcCd\color{red}{Da} &
2.AbBcCdDa &2.Ab\color{red}{Bc}CdDa &2.Ab\color{red}{Bc}Cd\color{red}{Da} \\

3.\color{red}{Ab}BdCa\color{red}{Dc} &3.\color{red}{Ab}BdCaDc &3.\color{red}{AbBdCaDc} &
3.AbBdCaDc &3.Ab\color{red}{Bd}\color{red}{Ca}Dc &3.Ab\color{red}{Bd}CaDc &
3.AbBdCa\color{red}{Dc} &3.AbBd\color{red}{Ca}Dc &3.AbBdCaDc \\

4.Ac\color{red}{Ba}\color{red}{Cd}Db &4.AcBa\color{red}{Cd}Db &4.AcBaCdDb &
4.\color{red}{AcBaCdDb} &4.\color{red}{Ac}BaCd\color{red}{Db} &4.\color{red}{Ac}BaCdDb &
4.Ac\color{red}{Ba}CdDb &4.AcBaCd\color{red}{Db} &4.AcBaCdDb \\

5.AcBdCaDb &5.AcBdCaDb &5.Ac\color{red}{Bd}\color{red}{Ca}Db &
5.\color{red}{Ac}BdCa\color{red}{Db} &5.\color{red}{AcBdCaDb} &5.\color{red}{Ac}\color{red}{Bd}CaDb &
5.AcBdCaDb &5.AcBd\color{red}{Ca}\color{red}{Db} &5.AcBdCaDb \\

6.AcBdCbDa &6.AcBdCb\color{red}{Da} &6.Ac\color{red}{Bd}CbDa &
6.\color{red}{Ac}BdCbDa &6.\color{red}{Ac}\color{red}{Bd}CbDa &6.\color{red}{AcBdCbDa} &
6.AcBd\color{red}{Cb}Da &6.AcBdCbDa &6.AcBd\color{red}{Cb}\color{red}{Da} \\

7.Ad\color{red}{Ba}Cb\color{red}{Dc} &7.AdBaCbDc &7.AdBaCb\color{red}{Dc} &
7.Ad\color{red}{Ba}CbDc &7.AdBaCbDc &7.AdBa\color{red}{Cb}Dc &
7.\color{red}{AdBaCbDc} &7.\color{red}{Ad}BaCbDc &7.\color{red}{Ad}Ba\color{red}{Cb}Dc \\

8.AdBcCaDb &8.Ad\color{red}{Bc}CaDb &8.AdBc\color{red}{Ca}Db &
8.AdBcCa\color{red}{Db} &8.AdBc\color{red}{Ca}\color{red}{Db} &8.AdBcCaDb &
8.\color{red}{Ad}BcCaDb &8.\color{red}{AdBcCaDb} &8.\color{red}{Ad}\color{red}{Bc}CaDb \\

9.AdBcCbDa &9.Ad\color{red}{Bc}Cb\color{red}{Da} &9.AdBcCbDa &
9.AdBcCbDa &9.AdBcCbDa &9.AdBc\color{red}{Cb}\color{red}{Da} &
9.\color{red}{Ad}Bc\color{red}{Cb}Da &9.\color{red}{Ad}\color{red}{Bc}CbDa &9.\color{red}{AdBcCbDa} \\
\hline      
\end{array}


\begin{array}{|c|c|c|c|}     
\hline     
1.AbBaCdDc
&2.AbBcCdDa
&3.AbBdCaDc
&4.AcBaCdDb
&5.AcBdCaDb
&6.AcBdCbDa
&7.AdBaCbDc
&8.AdBcCaDb
&9.AdBcCbDa\\     
\hline   
&&&
&1.AbBaCdDc &1.AbBaCdDc &
&1.AbBaCdDc &1.AbBaCdDc \\
&&&
&2.AbBcCdDa &&
2.AbBcCdDa &&\\
&&&
3.AbBdCaDc &&&
&&3.AbBdCaDc \\
&&4.AcBaCdDb &
&&&
&&4.AcBaCdDb \\
5.AcBdCaDb &5.AcBdCaDb &&
&&&
5.AcBdCaDb &&5.AcBdCaDb \\
6.AcBdCbDa &&&
&&&
&6.AcBdCbDa &\\
&7.AdBaCbDc &&
&7.AdBaCbDc &&
&&\\
8.AdBcCaDb &&&
&&8.AdBcCaDb &
&& \\
9.AdBcCbDd &&9.AdBcCbDd &
9.AdBcCbDd &9.AdBcCbDd &&
&&\\
\hline     
\end{array}

Infinity

回复 4# 青青子衿
明白了。第二次对应关系有10对配对，每个配对后续都不能再出现。

Infinity

这个问题称为“二重错排”问题，结果见https://www.docin.com/p-1194250467.html中的定理2（以及定义2）。

青青子衿

回复 7# Infinity
根据四对的情形列的表格可以发现一个有趣的事情：
①每一列“可行的”字符串都有偶数个；
②如果把某一列的字符串看作是拼图，刚好可以拼成几个完整的字符串。
\begin{array}{|c|c|c|c|}        
\hline        
1.AbBaCdDc   
&2.AbBcCdDa   
&3.AbBdCaDc   
&4.AcBaCdDb   
&5.AcBdCaDb   
&6.AcBdCbDa   
&7.AdBaCbDc   
&8.AdBcCaDb   
&9.AdBcCbDa\\        
\hline      
\color{white}{1.\color{red}{AbBaCdDc}} &\color{white}{1.\color{red}{Ab}Ba\color{red}{Cd}Dc} &\color{white}{1.\color{red}{Ab}BaCd\color{red}{Dc}} &   
\color{white}{1.Ab\color{red}{Ba}\color{red}{Cd}Dc} &\color{white}{1.AbBaCdDc} &\color{white}{1.AbBaCdDc} &   
\color{white}{1.Ab\color{red}{Ba}Cd\color{red}{Dc}} &\color{white}{1.AbBaCdDc} &\color{white}{1.AbBaCdDc} \\  
  
\color{white}{2.\color{red}{Ab}Bc\color{red}{Cd}Da} &\color{white}{2.\color{red}{AbBcCdDa}} &\color{white}{2.\color{red}{Ab}BcCdDa} &   
\color{white}{2.AbBc\color{red}{Cd}Da} &\color{white}{2.AbBcCdDa} &\color{white}{2.AbBcCd\color{red}{Da}} &   
\color{white}{2.AbBcCdDa} &\color{white}{2.Ab\color{red}{Bc}CdDa} &\color{white}{2.Ab\color{red}{Bc}Cd\color{red}{Da}} \\  
  
\color{white}{3.\color{red}{Ab}BdCa\color{red}{Dc}} &\color{white}{3.\color{red}{Ab}BdCaDc} &\color{white}{3.\color{red}{AbBdCaDc}} &   
\color{white}{3.AbBdCaDc} &\color{white}{3.Ab\color{red}{Bd}\color{red}{Ca}Dc} &\color{white}{3.Ab\color{red}{Bd}CaDc} &   
\color{white}{3.AbBdCa\color{red}{Dc}} &\color{white}{3.AbBd\color{red}{Ca}Dc} &\color{white}{3.AbBdCaDc} \\  
  
\color{white}{4.Ac\color{red}{Ba}\color{red}{Cd}Db} &\color{white}{4.AcBa\color{red}{Cd}Db} &\color{white}{4.AcBaCdDb} &   
\color{white}{4.\color{red}{AcBaCdDb}} &\color{white}{4.\color{red}{Ac}BaCd\color{red}{Db}} &\color{white}{4.\color{red}{Ac}BaCdDb} &   
\color{white}{4.Ac\color{red}{Ba}CdDb} &\color{white}{4.AcBaCd\color{red}{Db}} &\color{white}{4.AcBaCdDb} \\  
  
\color{white}{5.AcBdCaDb} &\color{white}{5.AcBdCaDb} &\color{white}{5.Ac\color{red}{Bd}\color{red}{Ca}Db} &   
\color{white}{5.\color{red}{Ac}BdCa\color{red}{Db}} &\color{white}{5.\color{red}{AcBdCaDb}} &\color{white}{5.\color{red}{Ac}\color{red}{Bd}CaDb} &   
\color{white}{5.AcBdCaDb} &\color{white}{5.AcBd\color{red}{Ca}\color{red}{Db}} &\color{white}{5.AcBdCaDb} \\  
  
\color{white}{6.AcBdCbDa} &\color{white}{6.AcBdCb\color{red}{Da}} &\color{white}{6.Ac\color{red}{Bd}CbDa} &   
\color{white}{6.\color{red}{Ac}BdCbDa} &\color{white}{6.\color{red}{Ac}\color{red}{Bd}CbDa} &\color{white}{6.\color{red}{AcBdCbDa}} &   
\color{white}{6.AcBd\color{red}{Cb}Da} &\color{white}{6.AcBdCbDa} &\color{white}{6.AcBd\color{red}{Cb}\color{red}{Da}} \\  
  
\color{white}{7.Ad\color{red}{Ba}Cb\color{red}{Dc}} &\color{white}{7.AdBaCbDc} &\color{white}{7.AdBaCb\color{red}{Dc}} &   
\color{white}{7.Ad\color{red}{Ba}CbDc} &\color{white}{7.AdBaCbDc} &\color{white}{7.AdBa\color{red}{Cb}Dc} &   
\color{white}{7.\color{red}{AdBaCbDc}} &\color{white}{7.\color{red}{Ad}BaCbDc} &\color{white}{7.\color{red}{Ad}Ba\color{red}{Cb}Dc} \\  
  
\color{white}{8.AdBcCaDb} &\color{white}{8.Ad\color{red}{Bc}CaDb} &\color{white}{8.AdBc\color{red}{Ca}Db} &   
\color{white}{8.AdBcCa\color{red}{Db}} &\color{white}{8.AdBc\color{red}{Ca}\color{red}{Db}} &\color{white}{8.AdBcCaDb} &   
\color{white}{8.\color{red}{Ad}BcCaDb} &\color{white}{8.\color{red}{AdBcCaDb}} &\color{white}{8.\color{red}{Ad}\color{red}{Bc}CaDb} \\  
  
\color{white}{9.AdBcCbDa} &\color{white}{9.Ad\color{red}{Bc}Cb\color{red}{Da}} &\color{white}{9.AdBcCbDa} &   
\color{white}{9.AdBcCbDa} &\color{white}{9.AdBcCbDa} &\color{white}{9.AdBc\color{red}{Cb}\color{red}{Da}} &   
\color{white}{9.\color{red}{Ad}Bc\color{red}{Cb}Da} &\color{white}{9.\color{red}{Ad}\color{red}{Bc}CbDa} &\color{white}{9.\color{red}{AdBcCbDa}} \\  
\hline        
\end{array}


\begin{array}{|c|c|c|c|}        
\hline        
1.AbBaCdDc   
&2.AbBcCdDa   
&3.AbBdCaDc   
&4.AcBaCdDb   
&5.AcBdCaDb   
&6.AcBdCbDa   
&7.AdBaCbDc   
&8.AdBcCaDb   
&9.AdBcCbDa\\        
\hline      
1.\color{white}{AbBaCdDc} &1.\color{white}{Ab}Ba\color{white}{Cd}Dc &1.\color{white}{Ab}BaCd\color{white}{Dc} &   
1.Ab\color{white}{Ba}\color{white}{Cd}Dc &1.\color{blue}{AbBaCdDc} &1.\color{blue}{AbBaCdDc} &   
1.Ab\color{white}{Ba}Cd\color{white}{Dc} &1.\color{blue}{AbBaCdDc} &1.\color{blue}{AbBaCdDc} \\  
  
2.\color{white}{Ab}Bc\color{white}{Cd}Da &2.\color{white}{AbBcCdDa} &2.\color{white}{Ab}BcCdDa &   
2.AbBc\color{white}{Cd}Da &2.\color{blue}{AbBcCdDa} &2.AbBcCd\color{white}{Da} &   
2.\color{blue}{AbBcCdDa} &2.Ab\color{white}{Bc}CdDa &2.Ab\color{white}{Bc}Cd\color{white}{Da} \\  
  
3.\color{white}{Ab}BdCa\color{white}{Dc} &3.\color{white}{Ab}BdCaDc &3.\color{white}{AbBdCaDc} &   
3.\color{blue}{AbBdCaDc} &3.Ab\color{white}{Bd}\color{white}{Ca}Dc &3.Ab\color{white}{Bd}CaDc &   
3.AbBdCa\color{white}{Dc} &3.AbBd\color{white}{Ca}Dc &3.\color{blue}{AbBdCaDc} \\  
  
4.Ac\color{white}{Ba}\color{white}{Cd}Db &4.AcBa\color{white}{Cd}Db &4.\color{blue}{AcBaCdDb} &   
4.\color{white}{AcBaCdDb} &4.\color{white}{Ac}BaCd\color{white}{Db} &4.\color{white}{Ac}BaCdDb &   
4.Ac\color{white}{Ba}CdDb &4.AcBaCd\color{white}{Db} &4.\color{blue}{AcBaCdDb} \\  
  
5.\color{blue}{AcBdCaDb} &5.\color{blue}{AcBdCaDb} &5.Ac\color{white}{Bd}\color{white}{Ca}Db &   
5.\color{white}{Ac}BdCa\color{white}{Db} &5.\color{white}{AcBdCaDb} &5.\color{white}{Ac}\color{white}{Bd}CaDb &   
5.\color{blue}{AcBdCaDb} &5.AcBd\color{white}{Ca}\color{white}{Db} &5.\color{blue}{AcBdCaDb} \\  
  
6.\color{blue}{AcBdCbDa} &6.AcBdCb\color{white}{Da} &6.Ac\color{white}{Bd}CbDa &   
6.\color{white}{Ac}BdCbDa &6.\color{white}{Ac}\color{white}{Bd}CbDa &6.\color{white}{AcBdCbDa} &   
6.AcBd\color{white}{Cb}Da &6.\color{blue}{AcBdCbDa} &6.AcBd\color{white}{Cb}\color{white}{Da} \\  
  
7.Ad\color{white}{Ba}Cb\color{white}{Dc} &7.\color{blue}{AdBaCbDc} &7.AdBaCb\color{white}{Dc} &   
7.Ad\color{white}{Ba}CbDc &7.\color{blue}{AdBaCbDc} &7.AdBa\color{white}{Cb}Dc &   
7.\color{white}{AdBaCbDc} &7.\color{white}{Ad}BaCbDc &7.\color{white}{Ad}Ba\color{white}{Cb}Dc \\  
  
8.\color{blue}{AdBcCaDb} &8.Ad\color{white}{Bc}CaDb &8.AdBc\color{white}{Ca}Db &   
8.AdBcCa\color{white}{Db} &8.AdBc\color{white}{Ca}\color{white}{Db} &8.\color{blue}{AdBcCaDb} &   
8.\color{white}{Ad}BcCaDb &8.\color{white}{AdBcCaDb} &8.\color{white}{Ad}\color{white}{Bc}CaDb \\  
  
9.\color{blue}{AdBcCbDa} &9.Ad\color{white}{Bc}Cb\color{white}{Da} &9.\color{blue}{AdBcCbDa} &   
9.\color{blue}{AdBcCbDa} &9.\color{blue}{AdBcCbDa} &9.AdBc\color{white}{Cb}\color{white}{Da} &   
9.\color{white}{Ad}Bc\color{white}{Cb}Da &9.\color{white}{Ad}\color{white}{Bc}CbDa &9.\color{white}{AdBcCbDa} \\  
\hline        
\end{array}

Infinity

小规模时有一些现象（规律）会退化为平凡情形甚至消失，在大规模情况下也许还会出现新的规律。

wwdwwd117

欧拉都只弄一重错排见好就收了。。。

realnumber

试了2组数据
a0,a1,a2,a3,a4,a5,a6,a7,a8,a9（男）
第1次0，1，2，3，4，5，6，7，8，9（女）
第2次 1，7，5，6，9，4，8，3，2，0（女）
输出是439792种
a0,a1,a2,a3,a4,a5,a6,a7,a8,a9
第1次0，1，2，3，4，5，6，7，8，9
第2次1，0，3，4，5，6，7，2，9，8
输出是439952种，第2组数据程序如下：
var a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,k:longint;
begin
   k:=0;
   for a0:=2 to 9 do
     for a1:=0 to 9 do if (a1<>1)and(a1<>0)and(a1<>a0) then
       for a2:=0 to 9 do if (a2<>2)and(a2<>3)and(a2<>a1)and(a2<>a0) then
         for a3:=0 to 9 do if (a3<>3)and(a3<>4)and(a3<>a2)and(a3<>a1)and(a3<>a0) then
           for a4:=0 to 9 do if (a4<>4)and(a4<>5)and(a4<>a3)and(a4<>a2)and(a4<>a1)and(a4<>a0) then
             for a5:=0 to 9 do if (a5<>5)and(a5<>6)and(a5<>a4)and(a5<>a3)and(a5<>a2)and(a5<>a1)and(a5<>a0) then
               for a6:=0 to 9 do if (a6<>6)and(a6<>7)and(a6<>a5)and(a6<>a4)and(a6<>a3)and(a6<>a2)and(a6<>a1)and                     (a6<>a0) then
                 for a7:=0 to 9 do if (a7<>7)and(a7<>2)and(a7<>a6)and(a7<>a5)and(a7<>a4)and(a7<>a3)and(a7<>a2)and(a7<>a1)and(a7<>a0) then
                   for a8:=0 to 9 do if (a8<>8)and(a8<>9)and(a8<>a7)and(a8<>a6)and(a8<>a5)and(a8<>a4)and(a8<>a3)and(a8<>a2)and(a8<>a1)and(a8<>a0) then
                     for a9:=0 to 9 do if (a9<>9)and(a9<>8)and(a9<>a8)and(a9<>a7)and(a9<>a6)and(a9<>a5)and(a9<>a4)and(a9<>a3)and(a9<>a2)and(a9<>a1)and(a9<>a0) then
                       k:=k+1;

writeln(k);
end.
一共有11种类型：
a0,a1,a2,a3,a4,a5,a6,a7,a8,a9（男）
第1次0，1，2，3，4，5，6，7，8，9（女）
第2次 1，0，3，2，5，4，7，6，9，8（女）记为"2+2+2+2+2"
a0,a1,a2,a3,a4,a5,a6,a7,a8,a9（男）
第1次0，1，2，3，4，5，6，7，8，9（女）
第2次 1，2，0，4，5，3，7，6，9，8（女）记为"3+3+2+2"
依次还有"4+2+2+2",“4+3+3”,“4+4+2”,“5+3+2”,“5+5”,“6+4”,"6+2+2","7+3","8+2"

最多几次成功错排后可能导致无法继续错排？也就是说不能保证情侣都换个新人.