首页 > 其他分享 >12.7闲话

12.7闲话

时间:2023-12-07 16:22:06浏览次数:29  
标签:排列 frac 闲话 个数 times cdots 12.7 binom

今天一看那个高中楼都被围起来了,估计快学考了

为啥和同学打招呼都没人理我,哦原来因为我是菜√,太菜了导致的

推歌

虚拟歌手贺岁纪《万物有灵》

歌词 似一捧细泉的奔逃

跃过石缝岩角

降落到我怀抱

待天地再静默一秒

这蓬勃的心跳

就将划开晨晓

我是亿万株花草 破土时的微渺

渴盼你能听到

有多少 不经意的喧嚣 穿越世界的浩邈

交织成我歌谣 在你耳畔停靠

生命的祈祷 是风吹拂过树梢 万物曾来过的记号

俯瞰河流蜿蜒盘绕

滋养荒瘠山坳

湿润了你眼角

一座森林突然繁茂

满目花开枝摇

等谁寻来落脚

我 是远行的归鸟 那啾啾的鸣叫

渴盼你能听到

有多少 不经意的喧嚣 与生俱来就美好

纵使烟火零凋 都是温柔语调

生命的祈祷 是风吹拂过树梢 万物曾来过的记号

有多少 不经意的喧嚣 穿越世界的浩邈

交织成我歌谣 在你耳畔停靠

生命的祈祷 是风吹拂过树梢 万物曾来过的记号

多重集的排列

  • 定理1:

    设集合\(S\)为有\(k\)种不同类型对象的多重集合,每种对象都有无限个,那么\(S\)的\(r\)排列数目为\(k^r\)

    • 证明:

      因为每种对象都有无限个,所以每一位的选择都和前面的选择无关,根据乘法原理可以轻易得到\(S\)的\(r\)排列数目为\(k^r\)

  • 定理2:

    对于多重集合\(S=\{{n_1\times a_1,n_2\times a_2,\cdots,n_k\times a_k}\}\),\(S\)的全排列个数为

    \[\frac{n!}{n_1!\times n_2!\times \cdots \times n_k!} \]

    • 证明

      放置\(a_1\)时,一共有\(n\)个位置,也就是在\(n\)个位置中放置\(n_1\)个数,也就是\(\large \binom{n}{n_1}\)

      放置\(a_2\)时,还剩余\(n-n_1\)个位置,放置\(n_2\)个数,也就是
      \(\large \binom{n-n_1}{n_2}\)

      以此类推

      在最后根据乘法原理相乘可以得到

      \[ \begin{aligned} &\ \ \ \binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\cdots\binom{n-n_1-n_2-n_3-\cdots-n_{k-1}}{n_k}\\ &=\frac{n!}{n_1!\times{(n-n_1)!}}\times\frac{(n-n_1)!}{n_2!\times{(n-n_1-n_2)!}}\times\frac{(n-n_1-n_2)!}{n_3!\times{(n-n_1-n_2-n_3)!}}\times\cdots \times \frac{(n-n_1-n_2-\cdots-n_{k-1})!}{n_k!\times{(n-n_1-n_2-n_3-\cdots-n_k)!}}\\ &=\frac{n!}{n_1!\times n_2!\times n_3! \times \cdots \times n_k!} \end{aligned}\]

      证毕

    • 根据这个定理还可以得到一个结论

      对于\(S=\{a_1\times n_1,a_2\times n_2\}\),S的全排列为\(\binom{n}{n_1}\)

      • 证明:

        \[\begin{aligned} \frac{n!}{n_1!n_2!}&=\frac{n!}{n_1!\times{(n-n_1)}} \\&=\binom{n}{n_1} \end{aligned} \]

  • 定理3

    把\(n\)个对象的集合\(S\)划分成\(k\)个序列且第一个序列有\(n_1\)个对象,第二个有\(n_2\)个对象\(\cdots\)第\(k\)个有\(n_k\)个对象且\(n=n_1+n_2+\cdots+n_k\)那么划分方法个数为

    \[\frac{n!}{n_1!\ n_2!\ n_3!\cdots n_k!} \]

    如果序列没有编号且\(n_1=n_2=n_3\cdots=n_k\)则个数为

    \[\frac{n!}{k!\ n_1!\ n_2!\ n_3!\cdots n_k!} \]

    • 证明:

      对于前者,证明类似定理二,选择的方法数同样为$$\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\cdots\binom{n-n_1-n_2-n_3-\cdots-n_{k-1}}{n_k}$$

      对于后者,同前面的例子一样,把这些对象分配到\(k\)个无编号序列中有\(k!\)种方法为之编号,使用除法原理可得出划分个数为

      \[\frac{n!}{k!\ n_1!\ n_2!\ n_3!\cdots n_k!} \]

错位排列

错位排列是没有任何元素出现在其有序位置的排列。

对于 \(1\sim n\) 的排列 \(S\) ,如果满足 \(S_i\neq i\) ,则称 \(S\) 是 \(n\) 的错位排列。

递推公式为:

\[D_n=(n−1)(D_{n−1}+D_{n−2})\tag{1} \]

\[D_n=nD_{n−1}+(-1)^n\tag{2} \]

  • 证明:
    先把 \(n\) 放在第 \(n\) 位,对于一个有 \(n−1\) 个数的排列,我们分情况讨论:

    • 满足要求:随便用一个数和 \(n\) 交换,为 \((n−1)D_{n−1}\)

    • 有且只有一位 \(k(1≤k≤n−1)\) 不满足:把 \(k\) 和 \(n\) 交换,为 \((n−1)D_{n−2}\)

    • 有 \(k(2≤k≤n−1)\) 位不满足:不可能一次换完,应该已经换完了

    合并一下,总方案数为:

    \[D_n=(n−1)(D_{n−1}+D_{n−2}) \]

标签:排列,frac,闲话,个数,times,cdots,12.7,binom
From: https://www.cnblogs.com/LuoTianYi66ccff/p/17881715.html

相关文章

  • 12.7周五每日博客(课堂测试)
    今天上课进行了面向对象建模分析的测试,试题内容为某物品拍卖网站为参与者提供物品拍卖平台,组织拍卖过程,提供在线或线下交易服务。网站的主要功能描述如下:(1)拍卖参与者分为个人参与者和团体参与者两种,不同的团体也可以组成新的团体参与拍卖活动。网站记录每个参与者的名称。(2)一次......
  • 12.7
    atcoderbeginner331C-SumofNumbersGreaterThanMe(atcoder.jp)这道题求后缀和,差不多是后缀和吧,然后佬用我没写过的一种树状数组直接秒掉,不服不行膜拜学习#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmaxn=1e6+10;intn,sum;inta......
  • 12.7
    有一些文献阅读的习惯还有形成,这几天在阅读材料的时候正好想一下大概的阅读和回顾流程。    作者:知乎用户mq5dxs链接:https://www.zhihu.com/question/19600673/answer/16623308来源:知乎著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。以下是我......
  • 闲话12.6
    换了一个拉格兰头像。做了做化学生物的样卷,生物样卷91pts,化学样卷95pts,赢!物理明天再做......
  • 2023-12-05 闲话 收收手,写写字
    因为摆烂既不想做厂子笔试题,也不想学Rust,也不想做AGC了,那么随便写点东西记录一下之前的生活啊。今天是我们亲爱的杨卓凡同学的最后一天未成年生活了。提前祝他成年快乐,上个月我去白净的时候他问我要不要12-6去,但是我明天上午11点有一个面试,后天下午可能同时约了两个笔试,......
  • 12.2闲话
    树剖树剖调了好久的板子终于过了,主要原因是建线段树出了问题,警钟长鸣本来应该是t[q].dat=a[T[l].rnk];然后我打的是t[q].dat=a[l];DFS序2点击查看代码#include<bits/stdc++.h>#defineMAXM0X66CCFF#defineintlonglongnamespaceIO{inlinevoidclose(){std::i......
  • 2023-11-29 闲话 垃圾桶是这里吗
    算法竞赛学不了一点。刷点b站视频吧。纯纯当作水博客用,看再多哔哩哔哩也和研究怎么拍个照片让机器把力矩学了没有半毛钱关系是吧。昨天刷了一个参加IROS2022kyoto的分享。现在仍然有印象的几点是:advisor觉得他很social,问他有没有经验。他说大概可以先加入一些小团体......
  • 11.29闲话
    今天也是为了解LCA,然后学了树链剖分这边写个讲解树剖分为重链剖分和长链剖分通常指的是重链剖分重链剖分对于任意一个位于树上的节点重子节点表示其子节点中子树最大的子结点。如果有多个子树最大的子结点,取其一。如果没有子节点,就无重子节点。轻子节点表示剩余的所有子......
  • 11.28闲话
    今天突然想起来几句歌词便是我掏空予你一半心房也借你一半替我浅吟低唱纵然纸片凉薄爱轻狂虚妄你歌声里亦浸着我的痴放越想越难受所以...推歌纸片人【ilem投稿九周年】这是图片V4:佬啊,佬啊怎么是纸片儿啊调啊,调啊调的我心动啊佬啊,佬啊怎么是纸片儿呐调啊,......
  • 2023-11-28 闲话 无人之境
    http://www.stat.ucla.edu/~sczhu/research_blog.html昨天只读了文章千古事,得失寸心知的一篇,非常非常大收获。感觉比以前水的东西有意义多了。以后考虑多上各种大学网站上搜教授主页,看paper或者article都是不错的选择是吧。......