algorithm-math-combinatorial-count

组合计数

计数基本原理

$|A| = \sum\limits_{a \in A} 1$

加法定理

|A U B| = |A| + |B|

乘法定理

|A * B| = |A| * |B|

举例

n-bit二进制串一共有多少个： 2^n（乘法原理）
如果把0看作(，把1看作)，配对的括号序列有多少个？
0011->(())
101010->)()()(

对于长度为6的序列：

$序列 = \begin{cases} \underline{()}(()), & k = 2 \\ \underline{()}()(), & k = 2 \\ \underline{(}()\underline{)}(), & k = 4 \\ \underline{(}(())\underline{)}, & k = 6 \\ \underline{(}()()\underline{)}, & k = 6 \\ \end{cases}$

第一个位置只能是(，考虑第一个(匹配的右括号位置在偶数位(2,4,6…)，分析所有的组合序列
如果位置是2，那么括号里边只有空集，外边的长度是4，有1*2 = 2种情况
如果位置是4，那么里边长度2，外边长度2，都只有1*1 = 1种情况
如果位置是6，那么里边长度4，外边是空集，那么有2*1 = 2种情况

拓展到长度为n，则：

$f(n) = \sum\limits_k f(k) \cdot f(n-k)$

组合数

概念

组合数的定义是从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数

公式

从n个数里找m个数排列（比如找第一个数有n个）得到 $A^{m}_{n}$ ，再除以 $A^m_m$ 去除这m个数的排列，得到组合数

$C^m_n = \frac{A^m_n}{A^m_m} = \frac{n!}{m! \cdot (n-m)!}$

互补性： $C^m_n = C^{n-m}_n$

n-1个数中找m个数，在n-1个数中加1个数，这个数可能在m个数中，也可能不在

$C^m_n = C^{m-1}_{n-1} + C^m_{n-1}$

思考

事实上，从n个数中找m个数相当于把m个数插入到(n-m)个数中

举证

求 1 到 n 所有排列的数量

利用乘法原理可以直接得出答案：n!

此时继续考虑把n个数分成m和n-m两组

例如，1234567可以分成123和4567

123有3!个排列

4567有4!个排列

对于123和4567的所有排列分别取一种情况，比如就取1->2->3和4->5->6->7

那么在保持顺序不变的情况下，设把123添加到4567当中的所有排列情况一共有x个

那么 $7! = 3! \cdot 4! \cdot x$

推广到n和m：

$n! = m! \cdot (n-m)! \cdot x$

则 $x = \frac{n!}{m! \cdot (n-m)!}$

错位排列

求1到n的排列中，每个数字不在原位的排列数量

$f(n) = (n-1) \cdot (f(n-1) + f(n-2))$

f(1) = 0, f(2) = 1

举证

对于12345678这些数字

第一个数字可以是2345678，设第一个数字取2，那么

$1-2-3-4-5-6-7-8 \\ \uparrow \\ 2-1-3-4-5-6-7-8$

考虑第二个位置，如果取1，那么剩下的问题就是对345678求错位排列

如果第二个位置不取1，那么相当于第二个位置也是要求错位，那么剩下的问题就是对2345678求错位排列

所以 $f(8) = 7 \cdot (f(7) + f(6))$

容斥原理

$|A \cap B| = |A| + |B| - |A \cup B|$

许多问题都有"求交简单，求并难"的性质

单面值组合的第 K 小金额

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。

你有无限量的每种面额的硬币。但是，你不能组合使用不同面额的硬币。

返回使用这些硬币能制造的第 k^th 小金额。

示例 1：

输入： coins = [3,6,9], k = 3

输出： 9

**解释：**给定的硬币可以制造以下金额：
3元硬币产生3的倍数：3, 6, 9, 12, 15等。
6元硬币产生6的倍数：6, 12, 18, 24等。
9元硬币产生9的倍数：9, 18, 27, 36等。
所有硬币合起来可以产生：3, 6, 9, 12, 15等。

示例 2：

**输入：**coins = [5,2], k = 7

**输出：**12

**解释：**给定的硬币可以制造以下金额：
5元硬币产生5的倍数：5, 10, 15, 20等。
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。

提示：

1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 10^9
coins 包含两两不同的整数。

二分+容斥原理

class Solution {
    private long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a%b);
    }
    private long count(long k, List<long[]> lcmAndCnt) {
        long res = 0;
        for (long t[] : lcmAndCnt) {
            if (t[1] % 2 == 1) {  // 容斥原理，单数加，双数-
                res += k / t[0];
            }
            else {
                res -= k / t[0];
            }
        }
        return res;
    }
    public long findKthSmallest(int[] coins, int k) {
        int n = coins.length;
        long l = 1, r = 25L * k;
        List<long[]> lcmAndCnt = new ArrayList<>();
        for (int i = 1; i < 1<<n; i++) {
            long lcm = 1, cnt = 0;  // 计算所有组合的最小公倍数，同时记录每个组合中数的个数
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    lcm = lcm / gcd(lcm, coins[j]) * coins[j];
                    cnt++;
                }
            }
            lcmAndCnt.add(new long[]{lcm, cnt});
        }
        while (l < r) {
            long m = l + r >>> 1;
            if (count(m, lcmAndCnt) < k) l = m + 1;
            else r = m;
        }
        return l;
    }
}

求与n互质的正数个数

例如n = 5 * 7 * 13

与n不互质（因数）的个数 = n/5 + n/7 + n/13 - n/(5*7) - n/(5*13) - n/(7*13) + n/(5*7*13)

res = n - 不互质的个数