組合數(shù)學(xué)第六章(編輯修改稿)
2025-09-01 20:27 本頁面
【文章內(nèi)容簡介】 2={3},X3=?,X4={1,5},X5={2,5} 1 2 3 4 5 i1 X X i2 X i3 i4 X X i5 X X Xi是第 i行的 禁止位置 定義 rk (p122) 1 2 3 4 5 6 i1 X i2 X X i3 X X i4 X X i5 i6 r1=7, r2=15, r3=10, r4=2, r5 = r6 = 0 定義 : 設(shè)將 k個棋子放在棋盤的禁止位置上 , 沒有棋子位于同行同列 ,方案數(shù)為 rk. 定義 : Ak = { ik ? Xk } 即 : ik在禁止位 , 其它 ij任意 問題的解 (p121122) 定義 : 設(shè)將 k個棋子放在棋盤的禁止位置上 , 沒有棋子位于同行同列 ,方案數(shù)為 rk. 定義 : Ak = { ik ? Xk } 即 : ik在禁止位 , 其它 ij任意 關(guān)聯(lián) : |A1| + |A2| + … + |A n| = r1(n1)! )!(||111knrAA kniiiikk ????????? ??定理 : 帶禁止位置的排列數(shù)為 n! r1(n1)! + r2(n2)! … + ( 1)nrn 0!, 1 2 3 4 5 i1 X X i2 X i3 i4 X X i5 X X 問題舉例 (p122123) X X X X X X X r1=7, r2=15, r3=10, r4=2, r5 = r6 = 0 帶如圖禁止位置排列數(shù)為 6!7?5!+15?4!10?3!+2?2! = 184 另外的禁排問題 (p123124) n個人練走步 , 排成一列前行 . 第二天要求 每人前面的人與前一天不同 , 記方案數(shù)為 Qn. 定理 : 對于 n0, !111)1( )!2(21)!1(11!?????????????????? ????????? ???nnnnnnnQnn?魔法手鐲 (補充 ) Potter的女朋友 Ginny的生日快到了 . Potter打算做魔法手鐲作為生日禮物 . 手鐲上要均勻地點綴 n(1?n?109)個魔珠 . 有 m(1?m?10)種魔珠 ,有些魔珠不能相鄰 . 輸入第一行 : t // 測試樣例數(shù) . 第二行 : n m k // 1?k?m(m1)/2 接下來 k行 : a b // 1?a,b?m, a和 b號珠不能相鄰 … 輸出 : 不同手鐲數(shù)模 9973的結(jié)果 . k種元素多重集的圓排列 (
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1