Friday May 29
We defined a partition of a set X: it is a set P of subsets of X, with the properties that
(1) unionS in P S = X, i.e. x in X <=> there exists S in P with x in S
(2) for any two distinct S1, S2 in P, the intersection is empty
(3) the empty set is not an element of P.
We also defined the {n choose k} notation for binomial coefficients, proved the Pascal recurrence combinatorially, and proved the formula with factorials in two different ways (by induction and using a bijection).
(Note that the Wikipedia article differs from how I did things in terms of which one is the definition and which one is the theorem. I think the order given there is silly.)
Something I didn't have time to emphasize: the middle expression in
makes sense for arbitrary n, not just for integers. (k should still be an integer.) This is important for the last HW question.
(1) unionS in P S = X, i.e. x in X <=> there exists S in P with x in S
(2) for any two distinct S1, S2 in P, the intersection is empty
(3) the empty set is not an element of P.
We also defined the {n choose k} notation for binomial coefficients, proved the Pascal recurrence combinatorially, and proved the formula with factorials in two different ways (by induction and using a bijection).
(Note that the Wikipedia article differs from how I did things in terms of which one is the definition and which one is the theorem. I think the order given there is silly.)
Something I didn't have time to emphasize: the middle expression in
makes sense for arbitrary n, not just for integers. (k should still be an integer.) This is important for the last HW question.
posted by Allen Knutson @ 11:54 PM
0 Comments:
Post a Comment
<< Home