#Unit 3-Lecture 4：Repetitions & Binomial Theorem

1 The Division Rule

A k-to-1 function maps exactly k elements of the domain to every element of the codomain. Rule: If  f:A→B  is  k−to−l, then  |A|=k⋅|B| $$If/ / f:A /to B/ / is/ / k-to-l,/ then/ / |A| =k/cdot|B|$$

2 Counting Subset

Subset Rule: The number of k-element subsets of an n-element set is: (nk)=n!k!(n−k)! $$/binom{n}{k} = /frac{n!}{k!(n-k)!}$$

3 Sequences with Repetitions

Definition： For n,k1,...,km∈N$n,k_1,...,k_m /in /mathbb N$, such that k1+k2+...+km=n$k_1 + k_2 + ...+ k_m =n$, define the mutinomial coefficient (nk1,k2,...,km)::=n!k1!k2!...km! $$/binom{n}{k_1,k_2,...,k_m}::=/frac{n!}{k_1!k_2!...k_m!}$$ Subset Split Rule: The number of (k1,k2,...,km)$(k_1,k_2,...,k_m)$ -splits of an n-elements set is: (nk1,k2,...,km) $$/binom{n}{k_1,k_2,...,k_m}$$ Bookkeeper Rule: Let l1,...,lm$l_1,...,l_m$ be distinct elements. The number of sequences with k1$k_1$ occurences of l1$l_1$, and k2$k_2$ occurence of l2$l_2$… and km$k_m$ occurence of lm$l_m$ is: (k1+k2+...+kmk1,k2,...,km) $$/binom{k_1+k_2+...+k_m}{k_1,k_2,...,k_m}$$ The Binomial Theorem: For all n∈N$n /in /mathbb N$ and a,b∈R$a,b /in /mathbb R$： (a+b)n=∑k=0n(nk)an−kbk $$(a+b)^n = /sum_{k=0}^{n}/binom{n}{k}a^{n-k}b^k$$ The multinomial Theorem: For all n∈N$n /in /mathbb N$: (z1+z2+...+zm)n=∑k1+k2+...+km=n(nk1,k2,...,km)zk11zk22...zkmm $$(z_1+z_2+...+z_m)^n=/sum_{k_1 + k_2 + ...+ k_m =n}/binom{n}{ {k_1,k_2,...,k_m}}z_1^{k_1}z_2^{k_2}...z_m^{k_m}$$

Reference

[1] Lehman E, Leighton F H, Meyer A R. Mathematics for Computer Science[J]. 2015.