旧文另一形式的再放送

Posted on Edited on

版权声明:本文作者 22 班周裕杭，未经作者允许严禁转载。

记以下过程为一次”随机生成“：

  • 从 {1,2,⋯ ,n}\{1, 2, \cdots, n\} 中均匀随机得到正整数 rr；
  • 再从 {1,2,⋯ ,r}\{1, 2, \cdots, r\} 中均匀随机得到正整数 ll；
  • 如此得到区间 [l,r][l, r]。

在固定正整数 nn 的情况下，进行 kk 次”随机生成“，可以得到 kk 个区间 [l1,r1],[l2,r2],⋯ ,[lk,rk][l_1, r_1], [l_2, r_2], \cdots, [l_k, r_k]。求这 kk 个区间两两交为空的概率。

为了防止剧透答案，在这里写一点闲话。

在过去的两周里，我一直在十一学校训练。最大的感触是，十一真的非常豪华，豪华到不像是一个公立学校。

首先是十一的食堂。十一的食堂至少有两层，还有至少三个咖啡厅。食堂里有多达数十个打饭窗口，里面包含了中国各大菜系，乃至于法餐、俄餐以及美式快餐内的不同美食。即使是最寻常的自助餐，饭菜的品相、味道以及性价比也比实验高到不知道哪里去了。咖啡厅里主要是一些快餐和简餐，虽然味道一般，不过可以在忙碌时用来充饥。

然后是运动场地。十一有接近二十块篮球场、一个标准足球场（部分场地用于橄榄球训练和飞盘）、一个七人制的小场还有一个棒球场。此外，体育馆里也有不少其他运动的场地，这里就不提了。学校各处都能看见足球和学生踢球的身影。操场上有非常清晰的场地使用规则，从未见到过玩飞盘的和踢足球的因为场地原因起过冲突。

十一的教学环境也不差。我们的训练所在地在图书馆，其容量比信毅楼之大不小，里面的书籍存量不是实验小小的地下图书馆可以比的。具体到我们训练的教室，则是一个法语教室，好像十一的学生可以自由选择选修这些课程。十一的国际部和普通学生在同一个校区，里面有剧院，有空中花园、滑梯和海洋球池（虽然看上去都比较简陋），有不少乐队教室和六七间琴房，还有数架钢琴可以供任何人随意使用——这是真正可以练琴的地方。

可能十一唯一的缺点就是位置比较偏僻吧。相比之下，实验只有可亲可敬的陆老师，令人感慨。

Hint：对于序列 a1,a2,⋯ ,ana _ 1, a _ 2, \cdots, a _ n，有

∑σ∏i=1naσ(i)∑j=1iaσ(j)=1\begin {aligned} \sum _ {\sigma} \prod _ {i = 1} ^ n \frac {a _ {\sigma(i)}} {\sum _ {j = 1} ^ i a _ {\sigma(j)}} = 1 \end {aligned}

其中 σ\sigma 为所有 {1,2,⋯ ,n}\{ 1, 2, \cdots, n \} 的排列。换言之，

E(∏i=1naσ(i)∑j=1iaσ(j))=1n!E \left( \prod _ {i = 1} ^ n \frac {a _ {\sigma(i)}} {\sum _ {j = 1} ^ i a _ {\sigma(j)}} \right) = \frac {1} {n!}

Hint 的证明：构建形如 此题 的组合模型即可。

再给大家一点思考的空间，放一点歌词吧。

悴（かじか）んだ心（こころ） ふるえる眼差（まなざ）し世界（せかい）で

ka ji kan da ko ko ro fu ru e ru ma na za shi se kai de

憔悴的心 摇曳不定的目光 这世间

僕（ぼく）はひとりぼっちだった散（ち）ることしか 知（し）らない春（はる）は

boku wa hitori bocchi da tta chi ru koto shika shi ra nai ha ru wa

唯我是 孤身一人 这不停凋零的春季

毎年（まいとし）冷（つめ）たくあしらう

mai toshi tsu metaku ashi ra u

每年都只是冷淡地应付

暗（くら）がりの中（なか） 一方通行（いっぽうつうこうに）ただ ただ

kuragari no naka ippou tsuukou ni tadatada

在黑暗深处 单向通行 仅仅 仅仅是

言葉（ことば）を書（か）き殴（なぐ）って 期待（きたい）するだけ むなしいと分かっていても

kotoba wo kaki nagutte kitai suru dake munashi to wakatte i te mo

草草写下话语 仅仅是心怀期待 即便知道一切空虚

救（すく）いを求（もと）め続（つづ）けた

sukui wo motome tsuzuke ta

也在持续寻求着救赎

せつなくて いとおしい

setsunaku te itooshii

苦闷不已 惹人怜悯

今（いま）ならば分（わ）かる気（き）がする

ima nara ba wakaru ki ga suru

若是如今 好像已经明白

しあわせで くるおしい

shiawase de kuruoshi

幸福满溢 宛若疯狂

あの日（ひ）泣（な）けなかった僕（ぼく）を

ano hi nake nakatta boku wo

那天没有哭出来的我

光（ひかり）は やさしく連（つ）れ立（だ）つよ

hikari wa yasashiku tsuredatsu yo

是光芒温柔地与我结伴前行

雲間（くもま）をぬって きらり きらり 心満（こころみ）たしては溢（あふ）れ

kumoma wo nutte kirari kirari kokoro mitashi te wa afure

穿过彩云之间 闪闪发光 心中满足 似要溢出

いつしか頬（ほお）を きらり きらり 熱（あつ）く 熱く 濡（ぬ）らしてゆく

itsushika hoo wo kirari kirari atsuku atsuku nurashi te yuku

不知何时 脸颊莹莹闪光 炽热地 炽热地将其濡湿

君（きみ）の手（て）は どうして こんなにも 温（あたた）かいの？

kimi no te wa doushite konna ni mo atatakai no ?

你的手心 为何会这样温暖呢？

ねえ お願（ねが）い　どうかこのまま

nee onegai douka kono mama

那个 求求你 请你永远这样

離（はな）さないでいて

hanasa nai de i te

不要离开我的身边

縁（えん）を結（むす）んではほどきほどかれ誰（だれ）しもが

en wo musun de wa hodoki hodoka re dareshimo ga

缔结于人人之间的缘分 却总是分分合合 无论是谁

それを喜（よろこ）び　悲（かな）しみながら 愛（あい）を数（かぞ）えてゆく

sore wo yorokobi kanashi mi nagara ai wo kazoe te yuku

都在其中的欢喜 与悲痛之中 细数那一份又一份的爱意

鼓動（こどう）を確（たし）かめるように

kodou wo tashikameru you ni

似在确认这心脏的搏动

うれしくてさびしくて

ureshiku te sabishiku te

喜悦不已 却又孤寂

今（いま）だからわかる気（き）がした

ima da kara wakaru ki ga shi ta

若是如今 好像已经察觉

たいせつでこわくって

taise tsu de kowakutte

无比重要 却又畏惧

あの日（ひ）泣（な）けなかった僕（ぼく）を

ano hi nake nakatta boku wo

那天没有哭出来的我

光（ひかり）はやさしく抱（だ）きしめた

hikari wa yasashiku daki shime ta

是光芒温柔地与我紧紧相拥

照（て）らされた世界（せかい）

terasa re ta sekai

在这明媚耀眼的世界

咲（さ）き誇（ほこ）る大切（たいせつ）な人（ひと）

sakihokoru taisetsu na hito

绽放着最为重要之人

あたたかさを知（し）った春（はる）は

atatakasa wo shitta haru wa

这春日知晓温暖何来

僕（ぼく）のため　君（きみ）のための涙（なみだ）を流（なが）すよ

boku no tame kimi no tame no namida wo nagasu yo

为我 亦为你 流淌下热泪

あぁ　なんて眩（まぶ）しいんだろう

a a nante mabushiin darou u

啊啊 这是如此耀眼

あぁ　なんて美（うつく）しいんだろう

a a nante utsukushiin darou u …

啊啊 又是多么迷人

雲間（くもま）をぬって きらり きらり 心満（こころみ）たしては溢（あふ）れ

kumoma wo nutte kirari kirari kokoro mitashi te wa afure

穿过彩云之间 闪闪发光 心中满足 似要溢出

いつしか頬（ほお）を きらり きらり 熱（あつ）く 熱く 濡（ぬ）らしてゆく

itsushika hoo wo kirari kirari atsuku atsuku nurashi te yuku

不知何时 脸颊莹莹闪光 炽热地 炽热地将其濡湿

君（きみ）の手（て）は どうして こんなにも 温（あたた）かいの？

kimi no te wa doushite konna ni mo atatakai no ?

你的手心 为何会这样温暖呢？

ねえ お願（ねが）い　どうかこのまま

nee onegai douka kono mama

那个 求求你 请你永远这样

離（はな）さないでいて

hanasa nai de i te

不要离开我的身边

ずっと　ずっと

zutto zutto

永远 永远

離（はな）さないでいて

hanasa nai de i te

不要离开我的身边

回到原题，记所有的 rr 从小到大依次为 1≤r1<r2<⋯<rk≤n1\le r _ 1 < r _ 2 < \cdots < r _ k \le n，则 ll 需要满足 1≤l1≤r1,r1<l2≤r2,⋯ ,rk−1<lk≤rk1\le l _ 1 \le r _ 1, r _ 1 < l _ 2 \le r _ 2, \cdots, r _ {k - 1} < l _ k \le r _ k。记 ai=ri−ri−1a _ i = r _ i - r _ {i - 1}；特别的，a1=r1a _ 1 = r _ 1。那么，选出若干 ll 使这些区间不交的概率即为 P(a)=∏i=1nai∑j=1iajP (a) = \prod _ {i = 1} ^ n \frac {a_i} {\sum _ {j = 1} ^ i a _ j}。

引理启示我们，如果可重集 {a1,a2,⋯ ,ak}\{a _ 1, a _ 2, \cdots, a _ k\} 固定不变，那么其每一种本质不同的重排的 P(a)P (a) 的期望即为 1k!\frac{1}{k!}（虽然所有 k!k! 种重排有可能有重复，但是由对称性，每一种本质不同的重排地位均等，所以其期望不变）。从而总的概率可以视作 nk‾nk⋅1k!=(nk)nk\frac {n ^ {\underline k}} {n ^ k} \cdot \frac {1} {k!}= \frac {\binom n k} {n ^ k}，即为答案。