#mth311

[trying2eecs-blog]

Balls and Boxes

Just killed my discrete structures final. (First one this semester, by the way.) But I messed up on one of the simplest of questions.

True or False? There are 45 ways to sort 8 identical balls into 3 boxes.

I answered false, stating that there are about several powers of ten above it, but that’s due to very, very incorrect miscalculation.

The correct answer is true, and can be answered using binomial coefficients.

 Binomial coefficients take the form of \(\binom {m}{n}\) and can be used to count the number of ways to choose \(n\) distinct things from \(m\) distinct objects. Although the eight balls are identical (read: not distinct), the possibilities of sorting these balls into three distinct boxes can be counted with the Balls and Boxes Theorem (or more accurately Balls and Separators).

Sorting 8 identical balls into 3 distinct boxes creates a Diophantine equation of the form \(x_1+x_2+x_3=8, x_n \ge 0\). The number of solutions to this equation is equivalent to the answer of the original equation. (Yes, 45, but how?) The \(x_n\)’s in the equation are the boxes, and their value represents the number of balls in that box. There are certain limitations: the total of these number cannot exceed 8 because there are only 8 balls total and the \(x_n\) values cannot be negative because anti-balls are not of our concern.

Now binomials. I’m just going to cut to the chase. \(\binom{10}{2}\) is the answer. Where does this come from? Well, it comes from \(\binom{8+2}{2}\). It’s easiest to draw a picture.

_ _ _ _ _ _ _ _ _ _

Each space represents either a possible ball or separator. There are ten spaces, and you’d need to choose 2 places put separators. (That’s where \(\binom{10}{2}\) comes from.) Choosing these separators leaves 8 empty spaces. Each empty space is representative of a ball. These separators also leave 3 groups of balls each representative of the \(x_n\)’s. Using |’s as separators, here is one example of a distribution:

_ _ _ | _ _ | _ _ _ 

In this example, \(x_1 = 3, x_2 = 2, x_3 = 3\). But how do you evaluate \(\binom{10}{2} = 45\)?

[trying2eecs-blog]

6 Relations and Functions

6.1 Relations Relations occur between elements from two sets (different or the same). The set of all possible relations from set S to itself can be described as S x S. Elements of this relation set, R, take the form of (a,b) is an element of R such that  a and b are elements of S. My professor likes to denote this as a~b (a is related to b) rather than having an ordered pair an element of the relation set R.

6.2 Equivalence Relations Equivalence relations occur when multiple elements are related to the same thing. I think. I need to study this one a little harder. I’m assuming that equivalence relations are kind of  like a~c and b~c so a and b are kind of equivalent. I’m not sure at all actually, but finals are next week.

Oh! I just remembered, they have to have three specific characteristics to be an equivalence relations. Reflective, something, and something. 

6.3 Functions Functions are special relations. For a relation to be a function there should be two defined sets - a domain and codomain - and a subset of the codomain - range. I forgot if images and preimages apply to relations too, but the image of an element in the domain is its corresponding element of the range. The preimage is that backwards. Forgot something important, any element in the range can only have one preimage in the domain (but multiple elements in the codomain can have the empty set as its preimage.)

Attributes! Alright, so there are three basic attributes of functions. It can be, monic, epic, and/or bijective. 

Monic, one-to-one, or injective functions are those with the following condition: for each element in the domain there exists a unique image in the range. In other words, it passes the horizontal line test.

Epic, onto, or surjective functions are those that satisfy the following condition: the range and codomain are equivalent. In otherwords, when you pump the entirety of the domain into the function, it pumps out the entire codomain set.

Bijective functions are both monic and epic. 

6.4 Compositions

6.5 Pigeonhole Principle