ลักษณะทั่วไปของหลายชุด
พิสูจน์ว่าสำหรับใด ๆ $c,d \in \mathbb{R}$ และ $k\in\mathbb{N}, \left({c+d\choose k}\right) = \sum_{j=0}^k \left({c\choose j}\right) \left({d\choose k-j}\right).$
ฉันรู้ว่าจะแสดงออกอย่างไร ${a+b\choose k} = \sum_{j=0}^k {a\choose j}{b\choose k-j}$ สำหรับ $a,b\in \mathbb{R}$โดยใช้การพิสูจน์พีชคณิต แต่ฉันไม่แน่ใจว่าจะแสดงเวอร์ชันมัลติเซ็ตของสิ่งนี้อย่างไร ฉันรู้แล้ว$\left({n\choose k}\right) = {n+k-1\choose k}$. แต่ถ้าเรายืนยันว่า$c,d\in\mathbb{N},$ฉันคิดว่าฉันสามารถหาข้อพิสูจน์เชิงผสมได้ ปล่อย$S$ แสดงถึงชุดของ $j$-multisets (เช่นขนาด $j$) ของ $[1,\cdots, c+d]$. ปล่อย$C_j$ แสดงถึงชุดของหลายขนาด $j$ จาก $[1,\cdots, c]$ และ $D_{k-j}$ แสดงถึงชุดของหลายขนาด $k-j$ จาก $[c+1,\cdots, c+d]$. ปล่อย$E_j$ แสดงถึงชุดของ $k$-multisets จาก $[1,\cdots, c+d]$ ด้วย $j$ องค์ประกอบจาก $[1,\cdots, c].$ สังเกตว่าแต่ละ $E_j$ ไม่ปะติดปะต่อและ $S = \cup_{j=0}^k E_j\Rightarrow |S| = \sum_{j=0}^k |E_j|\tag{1}.$ นอกจากนี้การกำหนด bijection ไม่ใช่เรื่องยาก $f : E_j \to C_j \times D_{k-j}.$ ตั้งแต่ $|C_j| = \left({c\choose j}\right)$ และ $|D_{k-j}| = \left({d\choose k-j}\right)$ และ $ |E_j| = |C_j||D_{k-j}|$แทนที่ผลลัพธ์เหล่านี้เป็น $(1)$ให้ความเท่าเทียมกันที่ต้องการ แต่แน่นอนว่าใช้ได้กับ$c,d\in \mathbb{N}.$
คำตอบ
สำหรับคงที่ $k\in\Bbb N$ การแสดงออก
$$p(c,d)=\left(\!\!\binom{c+d}k\!\!\right)-\sum_{j=0}^k\left(\!\!\binom{c}j\!\!\right)\left(\!\!\binom{d}{k-j}\!\!\right)$$
เป็นพหุนามใน $c$ และ $d$. ถ้าเราแก้ไข$c\in\Bbb N$มันจะกลายเป็นพหุนามใน $d$. พหุนามนี้เหมือนกัน$0$หรือมีศูนย์มากเท่านั้น เนื่องจากมันเป็น$0$ แต่ละ $d\in\Bbb N$มันต้องเหมือนกัน $0$. ด้วยประการฉะนี้$p(n,d)=0$ แต่ละ $n\in\Bbb N$ และ $d\in\Bbb R$. แต่ตอนนี้เราสามารถถือ$d$ คงที่และดู $p(c,d)$ เป็นพหุนามใน $c$และโดยอาร์กิวเมนต์เดียวกันว่าพหุนามต้องเหมือนกัน $0$. ด้วยประการฉะนี้$p(c,d)=0$ เพื่อทุกสิ่ง $c,d\in\Bbb R$.
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $\ds{\bbox[5px,#ffd]{\mbox{Prove that for any}\ c,d \in \mathbb{R}\ \mbox{and}\ k\in\mathbb{N}, \left(\!{c + d \choose k}\!\right) = \sum_{j = 0}^{k}\left(\!{c\choose j}\!\right) \left(\!{d\choose k - j}\!\right)}:\ {\Large ?}}$.
\begin{align} &\bbox[#ffd,5px]{\sum_{j = 0}^{k}\left(\!{c\choose j}\!\right) \left(\!{d\choose k-j}\!\right)} = \sum_{j = 0}^{k}{c^{\,\large\overline{j}} \over j!} {d^{\,\overline{k - j}} \over \pars{k - j}!} \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \sum_{j = 0}^{k}{k! \over j!\pars{k - j}!} {\Gamma\pars{c + j}\Gamma\pars{d + k - j} \over \Gamma\pars{c + d + k}} \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \sum_{j = 0}^{k}{k \choose j}\int_{0}^{1}t^{c + j - 1} \pars{1 - t}^{d + k - j - 1}\,\dd t \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!}\int_{0}^{1}t^{c - 1}\pars{1 - t}^{d + k - 1} \sum_{j = 0}^{k}{k \choose j}\pars{t \over 1 - t}^{j}\,\dd t \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \int_{0}^{1}t^{c - 1}\pars{1 - t}^{d + k - 1}\, \pars{1 + {t \over 1 - t}}^{k}\,\dd t \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \int_{0}^{1}t^{c - 1}\pars{1 - t}^{d - 1}\,\dd t \\[5mm] = &\ \require{cancel} {\pars{c + d + k - 1}! \over \cancel{\pars{c - 1}!\pars{d - 1}!}} \,{1 \over k!} \bracks{\cancel{\pars{c - 1}!\pars{d - 1}!} \over \pars{c + d - 1}!} = {c + d + k - 1 \choose k} \\[5mm] = &\ \bbx{\large\left(\!{c + d \choose k}\!\right)} \\ & \end{align}