更新时间:2022-09-20 10:26
手镯问题(problem of bracelet)是一种圆排列问题,用r种不同颜色的珠子穿成手镯,求所有不同的手镯数,这个问题称为手镯问题。手镯问题应解释为第一种单绕向圆排列。
手镯问题:用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)个且
一般地可用反演公式或伯恩赛德引理来求解圆排列问题。