双射法

✍ dations ◷ 2025-07-27 18:11:11 #Webarchive模板archiveit链接,组合计数,包含证明的条目,证明

双射法是组合数学中的一种重要的证明方法,用来证明两个有限集合A和B的元素数目相等。证明的思路是构造一个双射映射 : → ,于是根据双射的性质,A和B的元素数目就是相等的。这个证明是构造法证明的一种。由于双射法是给出具体的映射构造,而不是分别点算两个集合,所以不需要知道两个集合的元素个数。这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况。此外,双射法也可以用来计算一个集合(难以直接计算时),方法是将它映射到一个可以拆分或比较容易计算的集合。而作为构造性证明,双射法用到的也许可以用来更深刻地分析集合本身的性质。

二次项系数具有一定的对称性:

证明:这个等式可以视为两个集合的元素个数。考虑以下个元素的集合: S = { a 1 , a 2 , , a n } {\displaystyle S=\{a_{1},a_{2},\cdots ,a_{n}\}} 把C映射到它在S中的补集(有S中的 n k {\displaystyle n-k} 是一个从 A n {\displaystyle A_{n}} 是一个单射。

对于 B n + 2 {\displaystyle B_{n+2}} 也是一个满射。

也就是说,是一个双射。这就证明了 a n = b n + 2 . {\displaystyle a_{n}=b_{n+2}.}

相关

  • 实体实体(英语:Entity)是有可区别性且内于其自身而独立存在的某种事物。但它不需是物理存在。尤其是抽象和法律拟制也通常被视为实体。实体可被看成是一包含有子集的集合。在哲学中
  • 梦魇梦魇可以指:
  • 决策论决策论是一个交叉学科,和数学、统计、经济学、哲学、管理和心理学相关。它主要研究实际决策者如何进行决策,以及如何达到最优决策。决策论和博弈论关系密切;二者的区别是,决策论
  • 美国商业资讯美国商业资讯(英语:,BW),是美国一家新闻稿、公共关系等公开资讯发布的服务商,在全球拥有30多个办事处。利用其平台将文本新闻稿、图片以及其他多媒体内容传递给世界各地记者、金融
  • 玛丽·瑞瑙特玛丽·瑞瑙特(英语:Mary Renault,/ˈrɛnoʊlt/;1905年9月4日-1983年12月13日),出生名为“艾琳·玛丽·查兰斯”(Eileen Mary Challans),是一名联合王国籍旅居在南非的女作家。她以撰
  • 飓风曼努埃尔飓风曼努埃尔(英语:Hurricane Manuel)是2013年9月在墨西哥大部分地区引发洪灾的破坏性热带气旋,源于9月13日阿卡普尔科以南的一片强烈低气压区,是这年东北太平洋形成的第15场获命
  • 邹逸麟邹逸麟(1935年8月31日-2020年6月19日),浙江宁波人,中国历史地理学家,复旦大学首席教授。1935年8月31日生于上海。祖籍浙江绍兴,曾祖父辈举家搬至宁波做生意,父亲在上海办实业。1946
  • 斯赫尔加蒂斯赫尔加蒂(Sherghati),是印度比哈尔邦Gaya县的一个城镇。总人口32358(2001年)。该地2001年总人口32358人,其中男性17022人,女性15336人;0—6岁人口6078人,其中男3193人,女2885人;识字
  • 奥州仕置奥州仕置,为丰臣秀吉后以总无事令为由,在小田原之战中消灭北条家时,趁机要求出羽、陆奥两国的大名、豪族前来参阵,凭此重新决定日本东北地方的领土归属。自此以后,丰臣秀吉终于完
  • 欧洲围棋大会欧洲围棋大会(European Go Championship)是由欧洲围棋联盟(英语:European Go Federation)举办的围棋竞赛。欧洲围棋大会包括2周的公开竞争,每天一轮,总共10轮比赛产生最终冠军新兴