手鐲問題

手鐲問題

手鐲問題(problem of bracelet)是一種圓排列問題,用r種不同顏色的珠子穿成手鐲,求所有不同的手鐲數,這個問題稱為手鐲問題。手鐲問題應解釋為第一種單繞向圓排列

基本介紹

  • 中文名:手鐲問題
  • 外文名:problem of bracelet
  • 所屬學科:數學
  • 所屬問題:組合計數問題
基本介紹,相關介紹,

基本介紹

手鐲問題:用r種不同顏色的珠子穿成手鐲,求所有不同的手鐲數,這個問題稱為手鐲問題。手鐲問題應解釋為第一種單繞向圓排列。
穿手鐲的珠子可以從r種顏色中允許重複任取n個,也可以限定第i種顏色取bi(i=1,2,…,r)個,從而構成兩類不同問題(參見下文“圓排列”),兩類手鐲問題的解如下:
1.r種顏色珠子中允許重複任取n個所成不同的手鐲數
式中(k,n)為k,n的最大公約數
2.限定第i種顏色珠子取bi(i=1,2,…,r)個,
所成不同的手鐲數
式中B為b1,b2,…,br的最大公約數。

相關介紹

圓排列
圓排列(circular permutation)是一類重要的排列,把若干元排列在圓周上,就構成了一個圓排列,這裡並不指定圓周上哪一個位置上的元處於首位,因此圓排列與線排列不同。
有兩種不同的圓排列:
第一種稱為單繞向圓排列:對圓周上元的排列順序,順時針與反時針視為不同,典型問題為手鐲問題。例如圓排列依順時針繞向有abcd,bcda,cdab,dabc,這四種(線)排列都表示同一個單繞向圓排列;但依反時針繞向有adcb,dcba,cbad,badc,則表示與前者相異的一個單繞向圓排列,用群的觀點說,這是在循環群作用下保持不變的圓排列。
第二種稱為雙繞向圓排列:對圓周上元的排列順序,順時針與反時針視為相同,典型問題為項鍊問題。如上例中八種(線)排列都表示同一個雙繞向圓排列,用群的觀點說,這是在兩面體群作用下保持不變的圓排列。
求給定約束條件下所有不同圓排列的個數,稱為圓排列問題,其基本形式有兩種:
1.求從r種相異元中可重複地任取n個元所組成的圓排列數。
2.求從r種相異元中任取n個元,滿足下述條件的圓排列數:第i種元恰有bi(i=1,2,…,r)個且
一般地可用反演公式或伯恩賽德引理來求解圓排列問題。

相關詞條

熱門詞條

聯絡我們