从0-9中生成无重复数字且能被3整除的5位数的排列组合计数问题

咱们一步步来解决这个问题——要算无重复数字且能被3整除的5位数总数，得结合两个关键规则：一个数能被3整除当且仅当它的各位数字之和是3的倍数，而且5位数的首位不能是0。下面是具体的拆解思路：

第一步：对数字按模3余数分类 #

先把0-9这10个数字按除以3的余数分成三组：

• 余0组（数字本身是3的倍数）：{0, 3, 6, 9}（共4个数字）
• 余1组：{1, 4, 7}（共3个数字）
• 余2组：{2, 5, 8}（共3个数字）

我们需要选5个不同的数字，它们的总和是3的倍数，只有以下4种有效组合（其他组合要么数字数量不够，要么总和无法被3整除）：

情况1：1个余1数字 + 1个余2数字 + 3个余0数字 #

• 选数字的组合数：C(3,1) × C(3,1) × C(4,3) = 3×3×4 = 36
• 这里要分包含0和不包含0两种子情况计算排列数：
  • 包含0的选法：必须从余0组选0，再从剩下3个余0数字里选2个，组合数为C(3,1)×C(3,1)×C(3,2)=27。每个组合的有效排列数：总排列数5!减去首位为0的排列数4!，即120-24=96。这部分总数：27×96=2592
  • 不包含0的选法：余0组选{3,6,9}，组合数为C(3,1)×C(3,1)×C(3,3)=9。每个组合全排列：5!=120。这部分总数：9×120=1080
• 情况1总计：2592 + 1080 = 3672

情况2：2个余1数字 + 2个余2数字 + 1个余0数字 #

• 选数字的组合数：C(3,2) × C(3,2) × C(4,1) = 3×3×4 = 36
• 同样分包含0和不包含0：
  • 包含0的选法：余0组选0，组合数为C(3,2)×C(3,2)×C(1,1)=9。有效排列数：5!-4!=96。这部分总数：9×96=864
  • 不包含0的选法：余0组选3/6/9中的一个，组合数为C(3,2)×C(3,2)×C(3,1)=27。全排列：5!=120。这部分总数：27×120=3240
• 情况2总计：864 + 3240 = 4104

情况3：3个余1数字 + 0个余2数字 + 2个余0数字 #

• 选数字的组合数：C(3,3) × C(3,0) × C(4,2) = 1×1×6 = 6
• 分包含0和不包含0：
  • 包含0的选法：余0组选0+另一个非0余0数字，组合数为C(3,3)×C(3,0)×C(3,1)=3。有效排列数：96。总数：3×96=288
  • 不包含0的选法：余0组选2个非0数字，组合数为C(3,3)×C(3,0)×C(3,2)=3。全排列：120。总数：3×120=360
• 情况3总计：288 + 360 = 648

情况4：0个余1数字 + 3个余2数字 + 2个余0数字 #

这和情况3完全对称（余1和余2组的数字数量相同），所以计算结果也是648

最终总数 #

把所有情况的结果相加：
3672 + 4104 + 648 + 648 = 9072

内容的提问来源于stack exchange，提问作者Marble