一排 9 个座位，9 人依次入座，每人入座时，尽量不与已入座者相邻，有几种不同坐法？

pgcci7339

有9個座位排成一排，9名同學按學號排隊依次入座，每個座位坐一人，每名同學入座時，如果有空著的座位不與任何已經坐下的同學相鄰，
則這名同學一定選擇這樣的空座位，則最終9人位置的不同可能數目為?

想請教這題目如何做呢? 謝謝

luyuanhong

pgcci7339

謝謝老師

王守恩

luyuanhong 发表于 2019-2-24 19:01

杨辉三角万岁！伟大的杨辉三角万岁！ 中国人的杨辉三角万岁！  
   
         a(1)=1×1!×0!=
    a(2)=2×1!×1!=
a(3)=1×1!×2!+1×2!×1!=
         a(4)=3×2!×2!=
    a(5)=3×2!×3!+1×3!×2!=
a(6)=1×2!×4!+4×3!×3!=
         a(7)=6×3!×4!+01×4!×3!=
    a(8)=4×3!×5!+05×4!×4!=
a(9)=1×3!×6!+10×4!×5!+01×5!×04!=
         a(10)=10×4!×6!+06×5!×05!=
    a(11)=05×4!×7!+15×5!×06!+01×6!×05!=
a(12)=01×4!×8!+20×5!×07!+07×6!×06!=
          a(13)=15×5!×08!+21×6!×07!+01×7!×06!=
    a(14)=06×5!×09!+35×6!×08!+08×7!×07!=
a(15)=01×5!×10!+35×6!×09!+28×7!×08!+001×8!×07!=
          a(16)=21×6!×10!+56×7!×09!+009×8!×08!=
     a(17)=07×6!×11!+70×7!×10!+036×8!×09!+001×9!×08!=
a(18)=01×6!×12!+56×7!×11!+084×8!×10!+010×9!×09!=
           a(19)=28×7!×12!+126×8!×11!+045×9!×10!+001×10!×09!=
     a(20)=08×7!×13!+126×8!×12!+120×9!×11!+011×10!×10!=
a(21)=01×7!×14!+084×8!×13!+210×9!×12!+055×10!×11!+001×11!×10!=
           a(22)=036×8!×14!+252×9!×13!+165×10!×12!+012×11!×11!=
     a(23)=009×8!×15!+210×9!×14!+330×10!×13!+066×11!×12!+001×12!×11!=
a(24)=001×8!×16!+120×9!×15!+462×10!×14!+220×11!×13!+013×12!×12!=
            a(25)=045×9!×16!+462×10!×15!+495×11!×14!+078×12!×13!+001×13!×12!=
      a(26)=010×9!×17!+330×10!×16!+792×11!×15!+286×12!×14!+014×13!×13!=
a(27)=001×9!×18!+165×10!×17!+924×11!×16!+715×12!×15!+091×13!×14!+001×14!×13!=
            a(28)=055×10!×18!+792×11!×17!+1287×12!×16!+364×13!×15!+015×14!×14!=
      a(29)=011×10!×19!+495×11!×18!+1716×12!×17!+1001×13!×16!+105×14!×15!+001×15!×14!=
a(30)=001×10!×20!+220×11!×19!+1716×12!×18!+2002×13!×17!+455×14!×16!+016×15!×15!=
              a(31)=066×11!×20!+1287×12!×19!+3003×13!×18!+1365×14!×17!+120×15!×16!+001×16!×15!=
       a(32)=012×11!×21!+715×12!×20!+3432×13!×19!+3003×14!×18!+560×15!×17!+017×16!×16!=
a(33)=001×11!×22!+286×12!×21!+3003×13!×20!+5005×14!×19!+1820×15!×18!+136×16!×17!+001×17!×16!=
             a(34)=078×12!×22!+2002×13!×21!+6435×14!×20!+4368×15!×19!+680×16!×18!+018×17!×17!=

王守恩

luyuanhong 发表于 2019-2-24 19:01

谢谢 pgcci7339！  谢谢陆老师！

通项公式自然就有了！

中括号[a]是 a 取圆整，即四舍五入。

王守恩

luyuanhong 发表于 2019-2-24 19:01

谢谢陆老师！对（二）作点补充。
只有前面 4 人能做到不与已入座者相邻，后面 5 人都必须与已入座者相邻。
前面 4 人的位置在一排 9 个座位中的分布，可以这样考虑。
9 个座位按 1,2,3,4,5,6,7,8,9 编号，9 个数选 4 个数且满足 3 条：
第1条，第一个数必须在 1,2 中选一个，
第2条，第四个数必须在 8,9 中选一个，
第3条， 4 个数有 3 个间隔，每个间隔只能是 2 或 3。可得下列 10 种。
1,3,5,8，1,3,6,8，1,3,6,9，1,4,6,8，1,4,6,9，
1,4,7,9，2,4,6,8，2,4,6,9，2,4,7,9，2,5,7,9，
还可以简化：
第1条，重点考虑第一个数是 1 的可能，
1,3,5,8 与 2,5,7,9 是互补的一对
1,3,6,8 与 2,4,7,9 是互补的一对
1,4,6,8 与 2,4,6,9 是互补的一对
第2条，第二个数是 2 时，第四个数只能是 8。

王守恩

网友pgcci7339！能介绍一下此题的背景(来龙去脉)吗？我还是想往前推一推。