補設計

補設計(complementary design)是由一個區組設計派生的另一個區組設計，若一個區組設計(X，B)的區組為B₁，B₂，…，B_b，對每個區組B_i，做B′_i=X\B_i，把這樣得到的所有B′_i作為區組族B′，則稱(X，B′)為區組設計(X，B)的補設計。

基本介紹

• 中文名：補設計
• 外文名：complementary design
• 所屬學科：數學
• 所屬問題：組合學（組合設計）
• 簡介：由一區組設計派生的另一區組設計

基本介紹

若一個區組設計(X，B)的區組為B₁，B₂，…，B_b，對每個區組B_i，做B′_i=X\B_i，把這樣得到的所有B′_i作為區組族B′，則稱(X，B′)為區組設計(X，B)的補設計。一個(v，b，r，k，λ)-BIBD的補設計是一個(v，b，b-r，v-k，b-2r+λ)-BIBD，若區組設計(X，B)的關聯矩陣為A，則其補設計的關聯矩陣 =J_b×v-A，這裡J_b×v是元素全為1的b×v矩陣。

相關介紹

m×n的(0，1)矩陣A=(a_ij)的補矩陣 是指滿足條件

的m×n的(0，1)矩陣，矩陣也稱為(A₁，A₂，…，A_m)限位排列的關聯矩陣A的補，與相應的限位排列問題，稱為原限位排列問題的補問題。一個限位排列問題的補問題與一個車問題相對應。

關聯矩陣(1)的補是

對待矩陣(2)可有兩種觀點。第一，可把(2)看作某一個限位排列問題——稱為原限位排列問題的補問題——的關聯矩陣，其限制條件正好是原限制條件的補：

元j的限位集為，禁位集為B_j；

第i位的限元集為，禁元集為A_i.

第二，可以把(2)看作一個棋陣，它由一個m×n的矩形棋盤上的mn個格子組成，每個格子要么是1，要么是零；把有1的格子稱為實格，其他格子稱為虛格。

如果約定，在棋陣的實格處不允許放上棋子，那么，-限位排列問題就化為，尋求在棋陣(2)上放置m個互不相遇的棋子的放法的個數。這裡，所謂二個棋子相遇，意指它們在棋盤上的同一行或同一列。