EM@组合数学@朱世杰恒等式@曲棍球恒等式Hockey-stick identity

文章目录

    • refs
    • 朱世杰恒等式(曲棍球恒等式)👺
      • 变形
      • 证明
        • 递归方法
        • 组合方法
    • 公式形式总结
    • 应用
      • 基础套用
      • 等幂求和问题

refs

  • Hockey-stick identity - Wikipedia

朱世杰恒等式(曲棍球恒等式)👺

  • 朱世杰恒等式是组合数的一阶求和公式。元朝数学家朱世杰在《四元玉鉴》中,利用垛积术、招差术给出:
    ∑ i = a n ( i a ) = ( n + 1 a + 1 ) \sum_{i=a}^{n} \binom{i}{a} = \binom{n+1}{a+1} i=an(ai)=(a+1n+1)

将上式记为式(0)

变形

  • 若以 m − 1 m-1 m1 n n n ,得到式(1)
    ∑ i = a m − 1 ( i a ) = ( m a + 1 ) \sum_{i=a}^{m-1} \binom{i}{a} = \binom{m}{a+1} i=am1(ai)=(a+1m)

  • 与上式作差,写成:记为式(2)
    ∑ i = m n ( i a ) = ( n + 1 a + 1 ) − ( m a + 1 ) \sum_{i=m}^{n} \binom{i}{a} = \binom{n+1}{a+1} - \binom{m}{a+1} i=mn(ai)=(a+1n+1)(a+1m)

证明

递归方法

欲证式(0),即证式(2),而式(2)移项得到式(3)
( m a + 1 ) + ∑ i = m n ( i a ) = ( n + 1 a + 1 ) \binom{m}{a+1}+\sum_{i=m}^{n} \binom{i}{a} = \binom{n+1}{a+1} (a+1m)+i=mn(ai)=(a+1n+1)
将其展开得到式(4)如下:
( m a + 1 ) + ( m a ) + ( m + 1 a ) + ⋯ + ( n a ) = ( n + 1 a + 1 ) , \binom{m}{a+1} + \binom{m}{a} + \binom{m+1}{a} + \cdots + \binom{n}{a} =\binom{n+1}{a+1}, (a+1m)+(am)+(am+1)++(an)=(a+1n+1),
最后证明式(0)等价于证明式(4)

可以反复使用帕斯卡法则合并式(4)等号左边首两项,最终得到其等于等号右边的结论

帕斯卡法则如下:
( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) \binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k} (kn1)+(k1n1)=(kn)
从排列组合的角度(构造适当的排列组合问题模型)容易证明该等式

组合方法

n n n 元集 S = { a 1 , a 2 , a 3 , … , a n } S = \{a_1, a_2, a_3, \ldots, a_n\} S={a1,a2,a3,,an} r r r 个元素,有 ( n r ) \binom{n}{r} (rn) 种方法。将这些方法分类:

  • 必有 a 1 a_1 a1 时,再在 n − 1 n-1 n1 个元素中选 r − 1 r-1 r1 个元素;这类方法有 ( n − 1 r − 1 ) \binom{n-1}{r-1} (r1n1)

  • 排除 a 1 a_{1} a1时,在 n − 1 n-1 n1个元素中选 r r r个元素,这类方法有 ( n − 1 r ) \binom{n-1}{r} (rn1)种;我们在这种大类情况在继续细分

    • 排除 a 1 a_1 a1,且必有 a 2 a_2 a2 时,在 n − 2 n-2 n2 个元素中选 r − 1 r-1 r1 个元素;这类方法有 ( n − 2 r − 1 ) \binom{n-2}{r-1} (r1n2)
    • 排除 a 1 a_1 a1, 并排除 a 2 a_{2} a2(即排除 a 1 , a 2 a_1,a_2 a1,a2),在 n − 2 n-2 n2个元素中选 r r r个元素,这类方法有 ( n − 2 r ) \binom{n-2}{r} (rn2)
    • 排除 a 1 , a 2 a_{1},a_{2} a1,a2,情况下
      • 包含 a 3 a_{3} a3的方法数有 ( n − 3 r − 1 ) \binom{n-3}{r-1} (r1n3)
      • 排除 a 3 a_{3} a3,的方法数有 ( n − 3 r ) \binom{n-3}{r} (rn3)
      • 排除 a 1 , a 2 , a 3 a_{1},a_{2},a_{3} a1,a2,a3情况下
        • 包含 a 4 a_{4} a4的方法数 ( n − 4 r − 1 ) \binom{n-4}{r-1} (r1n4)
        • 排除 a 4 a_{4} a4的方法数 ( n − 4 r ) \binom{n-4}{r} (rn4)
  • 如此类推,直到必有 a n − r + 1 a_{n-r+1} anr+1 时,在 r − 1 r-1 r1 个元素中选 r − 1 r-1 r1 个元素,此时方法数为 1 1 1,为了统一,仍然记为 ( r − 1 r − 1 ) \binom{r-1}{r-1} (r1r1)

    • 这里 a n − r + 1 a_{n-r+1} anr+1的下标如何确定?对于 a 1 ⋯ a x ⋯ a n a_{1}\cdots{a_{x}}\cdots{a_{n}} a1axan,最后一次类推处理,要求 a x ⋯ a n a_{x}\cdots_{a_{n}} axan r r r个元素,那么 n − x + 1 n-x+1 nx+1 a x ⋯ a n a_{x}\cdots{a_{n}} axan的元素数量,所以令 n − x + 1 = r n-x+1=r nx+1=r,得出 x = n − r + 1 x=n-r+1 x=nr+1
    • 不过在这里我们不是非得求出 x x x,只需要知道存在这么一个 x x x使得剩余元素恰好足够 r r r
  • 整理
    ( n − 1 r − 1 ) + ( n − 2 r − 1 ) + ⋯ + ( r − 1 r − 1 ) = ( n r ) \binom{n-1}{r-1}+\binom{n-2}{r-1}+\cdots+\binom{r-1}{r-1}=\binom{n}{r} (r1n1)+(r1n2)++(r1r1)=(rn)

将上述等式改写为求和式表示(可以先将等式左边调整一下顺序在改写为求和式)
( r − 1 r − 1 ) + ⋯ + ( n − 2 r − 1 ) + ( n − 1 r − 1 ) \binom{r-1}{r-1}+\cdots+\binom{n-2}{r-1}+\binom{n-1}{r-1} (r1r1)++(r1n2)+(r1n1)

∑ k = r − 1 n − 1 ( k r − 1 ) = ( n r ) \sum\limits_{k=r-1}^{n-1}\binom{k}{r-1}=\binom{n}{r} k=r1n1(r1k)=(rn)

为了形式的美观性,由求和式的性质特点,等价变形求和指标,得到
∑ k = r n ( k − 1 r − 1 ) = ( n r ) \sum_{k=r}^{n} \binom{k-1}{r-1} = \binom{n}{r} k=rn(r1k1)=(rn)
或者求和指标变量用 i i i来表示,总结如下

公式形式总结

  1. ∑ i = a n ( i − 1 a − 1 ) = ( n a ) \sum_{i=a}^{n} \binom{i-1}{a-1} = \binom{n}{a} i=an(a1i1)=(an)
  2. ∑ i = a n ( i a ) = ( n + 1 a + 1 ) \sum_{i=a}^{n} \binom{i}{a} = \binom{n+1}{a+1} i=an(ai)=(a+1n+1)
  • 如果将恒等式的左右两端对调,可以说,朱世杰恒等式将一个组合数 ( n a ) \binom{n}{a} (an)展开成 ( n − 1 r − 1 ) + ( n − 2 r − 1 ) + ⋯ + ( r − 1 r − 1 ) \binom{n-1}{r-1}+\binom{n-2}{r-1}+\cdots+\binom{r-1}{r-1} (r1n1)+(r1n2)++(r1r1) n − a + 1 n-a+1 na+1

    • 形式2中,将左边的求和式的上标和下标分别加一,分别作为等式右边 ( r 1 r 2 ) \binom{r_1}{r_2} (r2r1)中的 r 1 , r 2 r_1,r_2 r1,r2
  • 形式1和形式2其实是完全等价的

    • n = n − 1 n=n-1 n=n1, a = a − 1 a=a-1 a=a1,带入到形式2,并等价调整求和号的上下标以及被求和表达式,就得到形式1
    • 或者令 n = n + 1 n=n+1 n=n+1, a = a + 1 a=a+1 a=a+1,带入形式1,也可以得到形式2
      • ∑ i = a + 1 n + 1 ( i − 1 a ) \sum\limits_{i=a+1}^{n+1}\binom{i-1}{a} i=a+1n+1(ai1)= ∑ i = a n ( i a ) \sum\limits_{i=a}^{n}\binom{i}{a} i=an(ai)= ( n + 1 a + 1 ) \binom{n+1}{a+1} (a+1n+1)

应用

基础套用

利用朱世杰恒等式计算 ( 4 2 ) \binom{4}{2} (24)

分别用形式1,2计算

  1. ( 4 2 ) \binom{4}{2} (24)= ∑ i = 2 4 ( i − 1 1 ) \sum\limits_{i=2}^{4}\binom{i-1}{1} i=24(1i1)= ( 1 1 ) + ( 2 1 ) + ( 3 1 ) \binom{1}{1}+\binom{2}{1}+\binom{3}{1} (11)+(12)+(13)= 6 6 6
  2. ( 4 2 ) \binom{4}{2} (24)= ( 3 + 1 1 + 1 ) \binom{3+1}{1+1} (1+13+1)= ∑ i = 1 3 ( i 1 ) \sum\limits_{i=1}^{3}\binom{i}{1} i=13(1i)= 6 6 6

等幂求和问题

例如:
∑ i = 1 n i = ∑ i = 1 n ( i 1 ) = ( n + 1 2 ) \sum_{i=1}^{n} i = \sum_{i=1}^{n} \binom{i}{1} = \binom{n+1}{2} i=1ni=i=1n(1i)=(2n+1)

∑ i = 1 n i ( i + 1 ) \sum_{i=1}^{n} i(i+1) i=1ni(i+1)= 2 ∑ i = 1 n ( i + 1 2 ) 2 \sum_{i=1}^{n} \binom{i+1}{2} 2i=1n(2i+1)= 2 ∑ i = 2 n + 1 ( i 2 ) 2\sum\limits_{i=2}^{n+1}\binom{i}{2} 2i=2n+1(2i)= 2 ( n + 2 3 ) 2 \binom{n+2}{3} 2(3n+2)

上面的例子中出现的 ∑ i = 1 n ( i + 1 2 ) \sum_{i=1}^{n} \binom{i+1}{2} i=1n(2i+1),求和符号和被求和式的形式不符合朱世杰恒等式的基础(标准)形式,我们根据求和符号的变形特点对该式子变形,将求和号的指标变量 i i i的起始值改为 2 2 2(也就是增加1,此时需要调整商标 n n n,也增加1,最后将求和式中的指标变量减去1)

类似的方法,计算 ∑ i = 1 n ( i + 1 3 ) \sum_{i=1}^{n} \binom{i+1}{3} i=1n(3i+1)= ∑ i = 3 n + 2 ( i − 1 3 ) \sum_{i=3}^{n+2} \binom{i-1}{3} i=3n+2(3i1)= ( n + 3 4 ) \binom{n+3}{4} (4n+3)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/460378.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

复现第一周24

1.[SWPUCTF 2021 新生赛]gift_F12 1)打开题目 2)看源码 3)直接ctrl+f搜索flag 2.[SWPUCTF 2021 新生赛]nc签到 1)开题 2)下载附件用记事本打开 3)打开kali使用nc连接代码 输入l\s命令绕过黑名…

warmup

首页只有一个笑脸&#xff0c;没有什么有效信息&#xff0c; 查看源代码发现,source.php。 访问source.php,显而易见&#xff0c;php代码审计。 <?phphighlight_file(__FILE__);class emmm{public static function checkFile(&$page){ //设立白名单&#xff0c;so…

Python 的安装及开发环境搭建

Python 的安装及开发环境搭建 文章目录 Python 的安装及开发环境搭建一、基础环境二、适用场景三、过程方法 版权声明&#xff1a;本文为CSDN博主「杨群」的原创文章&#xff0c;遵循 CC 4.0 BY-SA版权协议&#xff0c;于2024年10月29日首发于CSDN&#xff0c;转载请附上原文出…

Spring的高效开发思维(二)

时间&#xff1a;2024年 10月 30日 作者&#xff1a;小蒋聊技术 邮箱&#xff1a;wei_wei10163.com 微信&#xff1a;wei_wei10 音频&#xff1a;喜马拉雅 大家好&#xff0c;我是小蒋&#xff01;今天咱们继续深入 Spring 和 Spring Boot 的核心哲学。其实开发并不只是“码…

LeetCode算法(链表)

今天的算法是链表篇&#xff0c;这篇比较简单&#xff0c;总体是之前完成的手写链表&#xff0c;几乎就是链表的大部分知识了&#xff0c;所以今天算是一个复习内容了。 链表是一种通过指针串联在一起的线性结构&#xff0c;每一个节点由两部分组成&#xff0c;一个是数据域一…

Docker:容器化和虚拟化

虚拟化 虚拟化是一种资源管理技术&#xff0c;它将计算机的各种实体资源&#xff08;如CPU、内存、磁盘空间、网络适配器等&#xff09;予以抽象、转换后呈现出来&#xff0c;并可供分割、组合为一个或多个电脑配置环境。这些资源的新虚拟部分是不受现有资源的架设方式、地域或…

如何有效提升MySQL大表分页查询效率(本文以一张900万条数据体量的表为例进行详细解读)

文章目录 1、提出问题1.1 问题测试 2、解决问题&#xff08;三种方案&#xff09;2.1、方案一&#xff1a;查询的时候&#xff0c;只返回主键 ID2.2、方案二&#xff1a;查询的时候&#xff0c;通过主键 ID 过滤2.3、方案三&#xff1a;采用 elasticSearch 作为搜索引擎 3、总结…

DGUS屏使用方法

1、DGUS工程下载 迪文DGUS屏的所有硬件参数和资料下载&#xff0c;都是通过屏上的SD/SDHC接口来完成的&#xff0c;文件必须使用FAT32文件格式。第一次使用SD卡前&#xff0c;推荐先格式化一次&#xff0c;流程如下&#xff1a; 1、 右键单击SD卡&#xff0c;在弹出来的菜单中选…

设计产品宣传册没头绪?推荐一个超多产品宣传册、画册的案例网站

在当今市场竞争激烈的背景下&#xff0c;产品宣传册和画册是企业宣传的重要手段之一。一本独具匠心的宣传册&#xff0c;不仅能够准确传达产品特点&#xff0c;还能吸引潜在客户&#xff0c;提升品牌形象。然而&#xff0c;设计一本优秀的宣传册并非易事&#xff0c;许多设计师…

接口测试(八)jmeter——参数化(CSV Data Set Config)

一、CSV Data Set Config 需求&#xff1a;批量注册5个用户&#xff0c;从CSV文件导入用户数据 1. 【线程组】–>【添加】–>【配置元件】–>【CSV Data Set Config】 2. 【CSV数据文件设置】设置如下 3. 设置线程数为5 4. 运行后查看响应结果

【网页布局技术】项目五 使用CSS设置导航栏

《CSSDIV网页样式与布局案例教程》 徐琴 目录 任务一 制作简单纵向导航栏支撑知识点1&#xff0e;合理利用display:block属性2&#xff0e;利用margin-bottom设置间隔效果3&#xff0e;利用border设置特殊边框 任务二 制作简单横向导航栏任务三 制作带图片效果的横向导航栏任务…

基于LangChain构建安全Agent应用实践(含代码)

概述&#xff1a;本文基于langchain和Cyber Security Breaches数据集构建Agent&#xff0c;并基于该Agent实现了数据分析、趋势图输出、预测攻击态势三个功能&#xff0c;最后给出Agent在安全领域应用的三点启示。 前提&#xff1a; 1、拥有openai API KEY&#xff1b;&#…

机器学习-决策树

登录后复制 import numpy as np import matplotlib.pyplot as plt from sklearn import datasetsiris datasets.load_iris() X iris.data[:,2:] y iris.target plt.scatter(X[y0,0], X[y0,1]) plt.scatter(X[y1,0], X[y1,1]) plt.scatter(X[y2,0], X[y2,1]) plt.show() 1.2.…

为什么大模型都是Decoder-only结构?

扫一扫下方&#xff0c;获取更多面试真题的集合 在探讨当前大型语言模型&#xff08;LLM&#xff09;普遍采用Decoder-only架构的现象时&#xff0c;我们可以从以下几个学术角度进行分析&#xff1a; 注意力机制的满秩特性&#xff1a;Decoder-only架构采用的因果注意力机制&am…

Linux系统块存储子系统分析记录

1 Linux存储栈 通过网址Linux Storage Stack Diagram - Thomas-Krenn-Wiki-en&#xff0c;可以获取多个linux内核版本下的存储栈概略图&#xff0c;下面是kernel-4.0的存储栈概略图&#xff1a; 2 存储接口、传输速度 和 协议 2.1 硬盘 《深入浅出SSD&#xff1a;固态存储核心…

北京迅为iTOP-LS2K0500开发板快速使用编译环境虚拟机Ubuntu基础操作及设置

迅为iTOP-LS2K0500开发板 迅为iTOP-LS2K0500开发板采用龙芯LS2K0500处理器&#xff0c;基于龙芯自主指令系统&#xff08;LoongArch&#xff09;架构&#xff0c;片内集成64位LA264处理器核、32位DDR3控制器、2D GPU、DVO显示接口、两路PClE2.0、两路SATA2.0、四路USB2.0、一路…

电子电气架构 --- 车载芯片现状

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 所有人的看法和评价都是暂时的&#xff0c;只有自己的经历是伴随一生的&#xff0c;几乎所有的担忧和畏惧…

MySQL分层结构由哪些组成?

1、MySQL分层结构由哪些组成&#xff1f; MySQL按照功能模块可以分为3层&#xff1a;连接层、服务层和存储引擎层。 连接层位于Server服务层的最外层&#xff0c;负责与客户端的直接交互&#xff0c;从功能上单独划分一层更合适。 不同的存储引擎在存储层有不同的实现&#x…

Vue3入门--[vue/compiler-sfc] Unexpected token, expected “,“ (18:0)

新手小白学习Vue–入门就踩坑系列 问题描述 创建了一个Person.vue&#xff0c;保存后直接报错&#xff1a; [plugin:vite:vue] [vue/compiler-sfc] Unexpected token, expected "," (18:0) 在网上搜了半天也没找到原因&#xff0c;最后还得靠自己&#xff0c;现将解…