Binomial Coefficient: ·(（）份-fk-ofn ·ax=n(因）=k-bodts of(-() ·nl=n(n-1)…21. (n),=n(n-1)…(m-r-1) 0!=1. (Θ-1 (份=0>n Porpoaitiond(份)=a点o proof:Let B =fall vectors of length k over [n]consisting k dif- ferent elements.} (Double Counting) Way1:just directly count the number of vectors. Way2-Thre are(（)份）ysoe-fore-abat ,there are k!ways to order it to a vector. →B=(N →（份）=Binomial Coefficient: •  n k  := #k−elements subsets of an n elements set. • a|X| = n,  X k  :={all k−subsets of X}.      X k     =  n k  . • n! = n(n − 1)· · · 2 · 1. (n)r := n(n − 1)· · ·(n − r − 1). 0! = 1.  n 0  = 1.  n k  = 0 if k > n. Porposition4:  n k  = n! k!(n−k)! . proof: Let B ={all vectors of length k over [n] consisting k dif￾ferent elements.} (Double Counting) Way1:just directly count the number of vectors.|B| = n! k!(n−k)! . Way2:There are  n k  ways to choode k−subset of X.For each k−subset ,there are k! ways to order it to a vector. ⇒ |B| =  n k  k! ⇒  n k  = n! k!(n−k)! . 4