Introduction II – Counting and Sets

A house is build brick by brick – Counting and Sets is our first brick.

Warning: The first bricks are never the most exciting nor the most interesting bricks, nonetheless they’re important somewhat even the most important part because everything else is build on them. The same applies here. “Counting and Sets” might not be the most interesting thing out there but they are what everything else, or most of the following topics will be build on.

Sets

Let us start with sets and some definitions:

  • A Set is a collection of elements. Sets are therefore actually nothing else than boxes or buckets where you put things (elements) in, like a red ball, blue ball etc.
  • Element: x \in S; The element x is in the set S. For example the red ball from above.
  • Subset: A \subset S; The set A is contained in the set S. For example if S is a bucket of red, blue, pink, black and white balls and A is in the bucket of S and contains the red, blue and pink ball, then A is contained in S.
  • Complement: { A }^{ c } or S-A; The complement set of A contains all elements that are in S but not in A. In the example above it would be the black and white ball.
  • Union: A \cup B; The union of the sets A and B are just all elements together.
  • Intersection: A \cap B; The intersection of the sets A and B are the elements A and B have in common or in other words the elements both A and B contain.
  • Empty Set: \o; The empty set is a set that contains nothing.

A great way to visualise sets are Venn Diagrams. I recommend a visit of the Wikipedia page.

Product of Sets

productsets

The sets [2,3] and [2,4] for a rectangle. That applies for the product of all sets. The new set contains combinations of both sets:

[2,2][2,3][3,2][3,3][4,2][4,3] ] = new Set

Counting

Counting is a bit more exciting than sets. It enables us the calculate our first probabilities.

Example: Suppose we have a fair coin, therefore the probability of heads and tails is equal. We toss the coin three times. What is the probability of two heads?

If we toss a coin three times, there are eight possible outcomes:

{HHH, HHT, HTT, HTH, THT, TTH, THH, TTT} three of these outcomes have exactly two heads: {HHT, HTH, THH}. Our probability of two heads in three tosses is therefore \frac { 3 }{ 8 }. Or in general:

P\left( x\:heads\:in\:y\:tosses \right)=\frac { Combinations\;with\;x\;heads }{ Combinations\;of\;y\;tosses }

We can basically count in two different ways.

Inclusion-Exclusion-Principle:

|A\cupB| = |A| + |B| – |A\capB|

Rule of Product

If there are n ways to do action A and ways to do action B then there are nm ways to do action A followed by action B.

Example: We toss a coin two times. How many possible outcomes are there?

If we use the Rule of Product then there are two possible outcomes for the first toss and two possible outcomes for the second toss, so there are 2\times 2 possible outcomes for two tosses.

Permutations

Suppose we have the characters A,B,C and D. How many ways are there to draw three out of these four characters. The Rule of Product also applies here. There are four ways for the first draw, three four the second draw and two for the third draw. So there are 4\times 3\times 2=24 possible draws. Or in general:

{ _{ n }{ P }_{ k } } =\frac { n! }{ (n-k)! } with n the number of characters in the example and k the number of group “members”.

The order of the characters plays a role in permutations. ABC is not the same as ACB. The opposite is combinations where ABC and ACB is the same.

Combinations

In the example above, how many groups of three can we form? Here ABC and ACB are the same because the group consists of the same “members”. We can calculate the number of possible groups with:

{ _{ n }{ C }_{ k } } =\frac { n! }{ k!(n-k)! }

Counting and Sets might not be the most interesting topic but it is what all the other topics are build on. A complete understanding of Counting and sets is therefore important. And frankly, being able to calculate the number of possible combinations can come in handy in some situations.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s