Processing math: 100%
组合数学





组合数和基本组合数公式


鲜花:距离上一次整理数学知识还是在 2023 年,不知不觉已经过去了两年,真快啊…… 那个时候我还很菜,不过现在的我并没有成为之前想成为的样子。

组合数和基本组合数公式

  1. (nm)=n!(nm)!m!

    更广义的定义为 nmm!m}}{m!},可在 n 为实数,m 为非负整数时定义。

  2. (nm)=(nnm)

    组合意义:n 个选 m 个相当于从 n 个里面选择 m 个不选。

  3. (nm)=(n1m)+(n1m1)(加法公式)

    组合意义:相当于枚举第一个选还是不选。

  4. ni=0(ni)=2n

    组合意义:n 个中任意选相当于选择不同数量的方案数之和。

  5. (nm)=nm(n1m1) (吸收公式)

    常用于 m(nm)n(n1m1) 相互转换,使得前面那个系数变为定值提到外面去。

    组合意义:从 n 个里选 m 个再选 1 个特殊的等价于先从 n 个里选出特殊的再从剩下 n1 里选 m1 个。是公式 6 的特殊形式。

  6. (nm)(mk)=(nk)(nkmk)

    组合意义:从 n 个选 m 再选 k,从 n 个选 k 再从 nk 个选 mk,显然二者等价。

  7. ni=0(im)=(n+1m+1) (上指标求和)

    组合意义:有 n+1 个位置,从中选取 m+1 个,按照最后一个被选的位置统计。当最后一个位置为 i+1 时,选出 m+1 个位置的组合数就等价于从前 i 个位置选出 m 个位置的组合数之和。

  8. mi=0(n+ii)=(n+m+1n)(平行求和)

    代数解释:=mi=0(n+in),直接套上指标求和公式。

    组合意义:我不知道。

  9. mi=0(ni)(1)i=(1)k(n1k) (下指标差求和)

  10. ki=0(ni)(mki)=(n+mk)(范德蒙德卷积)

    组合意义:从 n+m 种选 k 个相当于从前 n 个选 i 个,后 m 个选 ki

  11. ni=0xiyni(ni)=(x+y)n(二项式定理)

    组合意义:n 个球染色,每个球都可以染成 x 种暖色之一和 y 种冷色之一。

更多组合意义

  1. 插板法

    m 个变量赋值为正整数和为 n 方案数为 (n1m1)

    组合意义:n 个小石子用 m1 个板分成 m 个部分。

    如果赋值成非负整数的方案数量为 (n+m1m1)

    组合意义:将所有数字 +1 最后 1 即满足调前

  2. 捆绑法

    如果集合 S 必须抱团取暖,把他们当成一个整体,最后乘上集合内部排列的方案数即 S!

入门题

[ARC144D] AND OR Equation

你并不用在意这个题讲的什么,我们来推式子,尝试化简:

ni=0ks=i(ni)2i(s1i1)(ks+1)

要求 O(n) 计算。

=ni=0(ni)2iks=i((k+1)(s1i1)i(si))=ni=0(ni)2i((k+1)(ki)i(k+1i+1))=ni=0(ni)2i((i+1)(k+1i+1)i(k+1i+1))=ni=0(ni)2i(k+1i+1)

(1) 简单移项,(2) 上指标求和化简,(3) 吸收公式化简,(4) 简单整理。


暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇