2
edits
Changes
Jump to navigation
Jump to search
Line 15:
Line 15: − + + + + + + + + + + + + + +
Put in combinatorics and "n choose k".
Define "A" as the set of all false assertions, and "B" as the set of all the Bible passages. Since there are no [[Counterexamples to the Bible]], the intersection between set A and set B is the [[empty set]].
Define "A" as the set of all false assertions, and "B" as the set of all the Bible passages. Since there are no [[Counterexamples to the Bible]], the intersection between set A and set B is the [[empty set]].
==See also==
==More Applications -- Combinatorics==
Sets, and their cardinalities, are used in some very important aspects of combinatorics, that is, the study of combinations. Let <math>X = \{a,b,c\}</math> and <math>Y = \{p,q,r\}</math>. The cardinalities of both are <math>\|X\| = \|Y\| = 3</math>. Let <math>S = \{\{x,y\}\ |\ x \in X \and y \in Y\}</math>. The vertical bar means "such that", and the epsilon-like symbol means "is an element of". So this means that S is the collection of sets<ref>Mathematicians don't like to use the phrase "set of sets", since this can lead to some unpleasant paradoxes. So they say "collection of sets." A "collection" is really just a set.</ref> which are pairs x and y such that x is in X and y is in Y. We can enumerate this. <math>S = \{\{a,p\}, \{a,q\}, \{a,r\}, \{b,p\}, \{b,q\}, \{b,r\}, \{c,p\}, \{c,q\}, \{c,r\}\}</math>. Its cardinality is <math>\|S\| = 9</math>.
Now try a harder example, based on the same two sets. Let <math>G = \{F\ |\ F \subset (X \cup Y) \and \|F\|=2\}</math>. Now <math>X \cup Y = \{a,b,c,p,q,r\}</math>, so <math>\|X \cup Y\| = 6</math>. The problem of finding the number of subsets of a set that has some particular cardinality is the ''combination choosing'' problem, and shows up in many areas of probability and statistics. In this case, it's the problem of choosing 2 elements out of a set of 6 elements. The number of such choices is often written <math>{}_6C_2</math> or <math>6 \choose 2</math>, and is often pronounced "six choose two". These numbers are also called the [[binomial coefficients]] because they appear as coefficients in the expansion of <math>(x+y)^n</math>. In this case, <math>6 \choose 2</math> is the coefficient of <math>x^2y^4</math> in <math>(x+y)^6</math>.
There is a simple formula for <math>n \choose k</math>. It is <math>{n \choose k} = \frac{n!}{n! (n-k)!}</math>. In the case of the set <math>G = \{F\ |\ F \subset \{a,b,c,p,q,r\} \and \|F\|=2\}</math>, the set is <math>G = \{\{a,b\}, \{a,c\}, \{a,p\}, \{a,q\}, \{a,r\}, \{b,c\}, \{b,p\}, \{b,q\}, \{b,r\}, \{c,p\}, \{c,q\}, \{c,r\}, \{p,q\}, \{p,r\}, \{q,r\}\}</math>. Its cardinality is 15.
We can check that <math>{6 \choose 2} = \frac{6!}{2! (6-2)!} = \frac{720}{2 \cdot 24} = 15</math>.
==References==
<references/>
==see also==
*[[union (set theory)]]
*[[union (set theory)]]
*[[intersection]]
*[[intersection]]