项链问题(problem of necklace)是一种圆排列问题,设由n个珠子串成一条项链,每个珠子可有r种不同的颜色,试问共有多少种不同花色的项链?(其中,两个项链认为是同一花色是指将一个项链朝一个方向旋转某个角度之后,便与另一个项链完全一样)。这个问题称为项链问题 [1]。
- 中文名
- 项链问题
- 外文名
- problem of necklace
- 所属学科
- 数学
- 所属问题
- 组合计数问题
- 简 介
- 可理解为第二种双绕向圆排列
项链问题是一种圆排列问题,用r种不同颜色的珠子穿成项链,求所有不同的项链数。这个问题称为项链问题。项链问题应解释为第二种双绕向圆排列。项链的珠子可以从r种颜色中允许重复任取n个,亦可以限定第i种颜色取bi(i=1,2,…,r)个,
两类项链问题的解如下:
1r种颜色珠子中允许重复任取n个所成不同的项链数
2.限定第i种颜色珠子取bi个,i=1,2,…,r,
当bi中奇数多于两个时,
圆排列
圆排列(circular permutation)是一类重要的排列,把若干元排列在圆周上,就构成了一个圆排列,这里并不指定圆周上哪一个位置上的元处于首位,因此圆排列与线排列不同。
有两种不同的圆排列:
第一种称为单绕向圆排列:对圆周上元的排列顺序,顺时针与反时针视为不同,典型问题为手镯问题。例如圆排列依顺时针绕向有abcd,bcda,cdab,dabc,这四种(线)排列都表示同一个单绕向圆排列;但依反时针绕向有adcb,dcba,cbad,badc,则表示与前者相异的一个单绕向圆排列,用群的观点说,这是在循环群作用下保持不变的圆排列。
第二种称为双绕向圆排列:对圆周上元的排列顺序,顺时针与反时针视为相同,典型问题为项链问题。如上例中八种(线)排列都表示同一个双绕向圆排列,用群的观点说,这是在两面体群作用下保持不变的圆排列。
求给定约束条件下所有不同圆排列的个数,称为圆排列问题,其基本形式有两种:
1.求从r种相异元中可重复地任取n个元所组成的圆排列数。
2.求从r种相异元中任取n个元,满足下述条件的圆排列数:第i种元恰有bi(i=1,2,…,r)个且