Feb 4	 				      CSCI 2427 - Discrete Math

-----------------------------------------------------------------------

How many n-ominos are there as a function of n?

f(x) = # n-ominos
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 5
f(5) = 12
f(6) = 35
...

Nobody knows this a formula for this function. In fact, nobody knows f(50). This is a function nobody knows a formula for.

Counting takes talent!

Another one: How many patterns can I make on a Rubik's cube? More than billions! 
The number of cube patterns is 43,252,003,274,489,856,000 
That's over 43 quintillion. That would be enough pennies to go from here and back to the sun, 196,000 times.

Extra Credit Question: Where does this number come from?

Counting with Finesse: Use sets and functions.

Normal Counting			Discrete Math Counting
---------------		 |	---------------------
How many 5-ominos	 |	How large is the set
are there? (pentominos)	 |	of 5-ominos?
-----------------------------------------------------
How many Rubik's cube	 |	How big is the set of
patternsare there?	 |	legal rubik's cube
 (legal)		 |	patterns?
-----------------------------------------------------
How many 8-letter	 |	How large is the set of
passwords are there?	 |	functions from the set
			 |	{1,2,3,4,5,6,7,8} to the set
			 |	{a,b,c,...,A,B,C...Z}?
-----------------------------------------------------

			Sets
			----

A set is an unordered collection of objects.
Objects may be in the set at most once each.

Ex: {1,2,3}	{3,1,2}

These two sets are equal because they have the same elements.

Ex: {a,b,c,a,b,d} = {a,b,c,d}

The first way is not a good way to write a set because it is 
misleading; you can only have an element within a set at most once.

			Functions
			---------

A function is a correspondance between two sets.
A DOMAIN and a RANGE.

[1,23,4,5,6,7,8] = Domain
[a,b,c,d,...,z,A,B,C,...,X,Y,Z]

A correspondance between the domain and range are such that EVERY ELEMENT 
of the domain maps to EXACTLY ONE element of the range.

Correspondance = map.

Brandon was asked to come up with a correspondance. He decided that 1 maps to C. 
Is that a function? No, because every element has to be mapped.

He then decided to map 2 to capital A.
Then 3 to lowercase a.
Then 4 to capital W.
5 to lowercase b.
6 to capital B.
7 to capital Y.
8 to capital C.

Woody was asked to name the function. He named it a for alphabet. He was 
asked what a(5) is? It's lowercase b. Brian M. was asked what a(8) is, 
and it is capital C. Rashid was asked what a-1(Y) was. It's 7.

a-1 is inverse. The inverse is mapped backwards.

What could mess up this function? If 7 also mapped to d, in addition to mapping to Y,
because every domain element must be mapped to one element of the range. 
This would make a(7) undefined.

What about this function? It's the same function except 8 is mapped to 
capital B. Is that still a function? Yes, it is not a problem because 
you can have two different elements in the domain go to the same range element. 
Every element of the domain can only have one line coming out of it, when
we draw a picture of the function.

The first function is said to be "one-to-one" because each element of the
range is mapped to by no more than one element of the domain. The second 
function is not 1-1. There is a "collision."

DEF: A function is called 1-1 if we never have f(a) = f(b) for a != b.

DEF: A function f is called onto if for all elements b in the range there 
is some element a in the domain such that f(a) = b.

Both of our functions are not onto, because every not element in the range 
is mapped to an element on the domain.

The function above gives us a password: specifically, that password is cAaWbBYC. 
That function corresponds to that password. The number of passwords there are is 
the same as the number of functions from the domain {1,2,3,4,5,6,7,8} to the 
range {a,b,c,...,A,B,C...Z}