2017.9.15 Slections with repetition Porposition6:#{integer solutions to +...+n=k.where >0=(n-i /k-1 proof:The question is equivalent to How many ways of distribut- ing sweets to n children.Such that each child has at least one sweet. Lay out the sweets in a single row of length k,cut it into n pieces.then given yhe sweets in the ith piece to child i.So we need n-1 cuts from k-1 possibles. -(-) integer solutions tok.where n-1 罗中太-+轻5奇之 A…6w头=+ie时 (1)fis weiidefined..if(c1,…,tn)∈A then(h,…,n)∈B. (2)injection. (3)surjection. →4==(+-1 n-1/ Porposition7:X=[n],A={{a a}X,1≤a1≤2≤ ≤n,anda+1-a:≥k+l,i∈r-1 62017.9.15 Slections with repetition Porposition6: # {integer solutions to x1 + · · · + xn = k. where xi > 0}=  k − 1 n − 1  . proof: The question is equivalent to How many ways of distribut￾ing k sweets to n children.Such that each child has at least one sweet. Lay out the sweets in a single row of length k,cut it into n pieces.then given yhe sweets in the ith piece to child i.So we need n − 1 cuts from k − 1 possibles. ⇒  k − 1 n − 1  . # {integer solutions to x1+· · ·+xn = k. where xi ≥ 0}=  n + k − 1 n − 1  . proof:LetA={integer solutions x1 + · · · + xn = k, xi ≥ 0} B ={integer solutions y1 + · · · + yn = n + k, yi > 0} Define f : A → B,(x1, · · · , xn) 7→ (y1, · · · , yn) by yi = xi+1, i ∈ [n]. Show:f is a bijection. (1) f is weiidefined.if (x1, · · · , xn) ∈ A then (y1, · · · , yn) ∈ B. (2) injection. (3) surjection. ⇒ |A| = |B| =  n + k − 1 n − 1  Porposition7: X = [n], A = {{a1, · · · , ar} ⊆ X, 1 ≤ a1 ≤ a2 ≤ · · · ≤ ar ≤ n, and ai+1 − ai ≥ k + 1, i ∈ [r − 1]}. 6