计数原理-埙指法个数

最近玩埙，是一个十孔树脂竹形埙，有箫的基础，上手就能吹响，看着指法表就能吹曲。埙指法怪异、音域有限，但是便携，总的来说还是能玩的。

回想箫指法是自己推演的，埙也应如此。计算得知十孔有 1024 种组合，这也太多了。偶然看到一个 B站视频讲到「埙是闭口乐器，音高与孔的位置无关，只与开孔面积有关。」这是宝贵的经验。观察十孔埙，发现有 4 种尺寸：1微3小3中3大。这种情况刚好应用前面研究「质因数幂积」问题得到的结论，共有 128 种组合。早上想起这个问题，发现如果十孔各不相同得到 1024 种组合也是符合该结论的。

至此，关于埙的问题抽象为纯数学问题。这一大类问题目的就是为了「数数」，核心是「计数原理」，包括加法原理和乘法原理。（代数数据类型 ADT 也是计数原理的应用）

组合可以看做将一堆东西分成两堆，选取其中一堆，因此天然存在对称性，例如10选3等于10选7。如果每个元素各不相同，可以看作每个元素都是一个类别。（相同有两种含义：同一个、同一类，一般指同一类）这样就与前面的「质因数幂积」问题联系起来了。现在新的问题是指定选取的元素个数，有多少种组合？例如十孔埙开 5 个孔有几种指法？

这个问题使用枚举法研究，得到以下组合，汇总得到结果 1+4+9+16+22+24+22+16+9+4+1=128 符合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1  3  3  3

1:
1  10  100  1000

2:
2  11  20  101  110  200
1001  1010  1100

3:
3  12  21  30
102  111  120  201  210  300
1002  1011  1020  1101  1110  1200

4:
13  22  31
103  112  121  130  202  211  220  301  310
1003  1012  1021  1030  1102  1111  1120  1201  1210  1300

5:
23  32
113  122  131  203  212  221  230  302  311  320
1013  1022  1031  1103  1112  1121  1130  1202  1211  1220  1301  1310

另外一种思路是从上至下分解，将问题记作 N|(n0,n1,...) 分解为子问题 M1|(n1,...) + M2|(n1,...) + ...

编写 Python 程序计算并验证通过：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

"""
多类别组合数计算

例如 4 种类别 (1,3,3,3)
选 5 个，有多少组合？

这个问题记作 N | (n1,n2,...)

使用枚举法研究发现该问题可以从上至下分解计算，
于是编写该程序。
"""

from functools import lru_cache, reduce
from operator import mul

type X = tuple[int, ...]


def f(N: int, nn: X) -> int:
    assert all(n > 0 for n in nn)
    sn = sum(nn)
    if N == 0 or N == sn:
        return 1
    assert 0 < N < sn
    return _f(N, nn)


@lru_cache
def _f(N: int, nn: X) -> int:
    if len(nn) == 1:
        return 1

    right = min(nn[0], N)
    left = max(0, N - sum(nn[1:]))
    value = sum(_f(N - x, nn[1:]) for x in range(left, right + 1))

    return value


def test_f():
    nn = (1, 3, 3, 3)
    expected = [1, 4, 9, 16, 22, 24, 22, 16, 9, 4, 1]
    for N, exp in enumerate(expected):
        # print(f(N, nn))
        assert exp == f(N, nn)


def g1(nn: X) -> int:
    NN = sum(nn)
    return sum(f(N, nn) for N in range(NN + 1))


def g2(nn: X) -> int:
    return reduce(mul, (n + 1 for n in nn))


def test_g():
    nn = (1, 3, 3, 3)
    assert g1(nn) == g2(nn) == 128

构思许多，落于实处遗失许多，不再多言。

EOF