Discrete Mathematics
Discrete mathematics is the study of mathematical structures that are countable or otherwise distinct and separable. Examples of structures that are discrete are combinations, graphs, and logical statements. Discrete structures can be finite or infinite. Discrete mathematics is in contrast to continuous mathematics, which deals with structures which can range in value over the real numbers, or have some non-separable quality.
Since the time of Isaac Newton and until quite recently, almost the entire emphasis of applied mathematics has been on continuously varying processes, modeled by the mathematical continuum and using methods derived from the differential and integral calculus. In contrast, discrete mathematics concerns itself mainly with finite collections of discrete objects. With the growth of digital devices, especially computers, discrete mathematics has become more and more important.
Discrete structures can be counted, arranged, placed into sets, and put into ratios with one another. Although discrete mathematics is a wide and varied field, there are certain rules that carry over into many topics. The concept of independent events and the rules of product, sum, and PIE are shared among combinatorics, set theory, and probability. In addition, De Morgan's laws are applicable in many fields of discrete mathematics.
Often, what makes discrete mathematics problems interesting and challenging are the restrictions that are placed on them. Although the field of discrete mathematics has many elegant formulas to apply, it is rare that a practical problem will fit perfectly to a specific formula. Part of the joy of discovering discrete mathematics is to learn many different approaches to problem-solving, and then be able to creatively apply disparate strategies towards a solution.
Combinatorics
Main Article: Combinatorics
Combinatorics is the mathematics of counting and arranging. Of course, most people know how to count, but combinatorics applies mathematical operations to count things that are much too large to be counted the conventional way.
Combinatorics is especially useful in computer science. Combinatorics methods can be used to develop estimates about how many operations a computer algorithm will require. Combinatorics is also important for the study of discrete probability. Combinatorics methods can be used to count possible outcomes in a uniform probability experiment.
Combinatorics is often concerned with how things are arranged. In this context, an arrangement is a way objects could be grouped. The most basic rules regarding arrangements are the rule of product and the rule of sum. These rules govern how to count arrangements using the operations of multiplication and addition, respectively.
At a local deli, the following options are given for a sandwich:
- Bread types: White, Rye, Wheat
- Cheese Types: Swiss, Cheddar, Havarti, Provolone
- Meat Types: Roast Beef, Turkey, Ham, Corned Beef, Pulled Pork
If a customer chooses exactly one of each type of item, then how many possible sandwiches can be made?
A more specific type of arrangement is a permutation. A permutation is an arrangement of objects with regard to order.
At the start of a horse race, there are 12 distinct horses in the field. 3 horses can place at the end of the race, and it matters what order the horses placed in. For example, if horses \(\text{A},\) \(\text{B},\) and \(\text{C}\) placed, then it would matter which horse came in \(1^\text{st}, 2^\text{nd},\) and \(3^\text{rd}.\) The order \(\text{ABC}\) would be different than \(\text{ACB}.\)
How many possible fields of placed horses are there?
A combination (not to be confused with combinatorics) is another type of arrangement that is related to permutations. A combination is an arrangement of objects without regard to order.
There are 12 distinct players about to play a pick-up game of football. The two team captains are Brandon and Meredith (included in the 12). They will each take turns selecting a player to be on their team until all players are selected.
How many ways can the players be divided into teams?
As a field of mathematics, combinatorics is nearly as broad as discrete mathematics. Other topics within combinatorics include
derangements: a permutation such that no object is in its original spot in the order;
rectangular grid walks: determining the number of ways a rectangular lattice can be traversed;
distribution of objects into bins: determining how objects can be grouped into bins.
Set Theory
Main Article: Set Theory
See Also:
Set theory is the branch of mathematics that is concerned about collections of objects. Sets can be discrete or continuous; discrete mathematics is primarily concerned with the former. At a basic level, set theory is concerned with how sets can be arranged, combined, and counted.
The cardinality of a finite set is the number of elements in that set. For a given set \(A,\) its cardinality is denoted by \(|A|.\)
What is the cardinality of the set of prime numbers less than 25?
The set of prime numbers less than 25 is
\[\{2,3,5,7,11,13,17,19,23\}.\]
There are 9 elements in this set, so the cardinality is 9. \(_\square\)
Cardinality can also be extended to infinite sets. Although this kind of cardinality cannot be counted, each cardinality can be compared with another cardinality.
Let \(A\) and \(B\) be sets. Their cardinalities are compared as follows:
If there exists a bijection between \(A\) and \(B,\) then \(|A|=|B|.\)
If there exists an injective function from \(A\) to \(B,\) but no bijective function, then \(|A|<|B|.\)
Show that the set of integers and the set of even integers have the same cardinality.
It might seem strange that these sets have the same cardinality. After all, the even integers are more "rare." However, these sets are both infinite. Therefore, the "common sense" thinking about finite sets must be discarded. Instead, the goal is to obtain a bijective function from the set of integers to the set of even integers:
\[f(n)=2n, \ n \in \mathbb{Z}.\]
The function above gives a one-to-one correspondence between each integer \(n\) and each even integer \(2n.\) Since the bijection is established, the set of integers and the set of even integers have the same cardinality. \(_\square\)
A complement of a set \(A\) is the set of elements that are not in \(A.\) The study of set complements gives a number of efficient methods to calculate cardinalities of finite sets. For example, one can efficiently obtain the cardinality of a set that contains "at least one" element of another set.
David is the leader of the David Committee. He wants to appoint 3 people to be on the Head Council. He has to choose from 9 applicants, three of whom are Tommy, Jack, and Michael. In how many ways can he choose the people to be on the Council, so that at least one of Tommy, Jack, and Michael is chosen?
The union and intersection give ways to describe how sets can be combined.
A positive integer less than 1000 is not only a perfect square but also a perfect cube.
How many such numbers are there?
Person "A" says the truth 60% of the time, and person "B" does so 90% of the time.
In what percentage of cases are they likely to contradict each other in stating the same fact?
De Morgan's laws give identities for the complements of unions and intersections.
How many integers between 1 and 1000 (inclusive) are neither multiples of 2 nor multiples of 5?
The principle of inclusion and exclusion, or PIE, gives a method to find the union or intersection of more than two sets.
How many integers from \(1\) to \(10^6\) (inclusive) are neither perfect squares nor perfect cubes nor perfect fourth powers?
Graph Theory
Main Article: Graph Theory
Graph theory is the study of graphs, which are a collection of connected nodes.
A basic graph of 3-Cycle
Graphs are useful for representing all kinds of real-world problems.
If there is a greedy algorithm that will traverse a graph, selecting the largest node value at each point until it reaches a leaf of the graph, what path will the greedy algorithm follow in the graph below?
John lives in the Trees of Ten Houses, and it is a most ideal and idyllic place for him and the other dwellers up in the canopy. They have invested a tremendous amount of time in engineering these houses, and to ensure no house felt isolated from the others, they built a fresh, finely crafted bridge between each and every house!
Unfortunately, the Trees of Ten Houses were not immune to thunderstorms, nor were the bridges well engineered. The night was treacherous, howling with wind and freezing with rain, so the odds for the bridges were not good--each bridge seemed just as likely to survive as to be shattered!
Fortunately, as there were so very many bridges in the Trees of Ten Houses, when John did wake the following morning, he found he was able to make his way to each and every house using only the existing bridges, though round-about routes may have been necessary. As they began rebuilding, John became curious... what were the chances that they'd all be so lucky?
More formally, if \(P\) is the probability that, after the storm, John is able to traverse to each and every house, what is \(\big\lfloor 10^{10} P \big\rfloor?\)
Details and Assumptions:
- The Trees of Ten Houses do, in fact, contain precisely 10 houses.
- Before the storm, there exists a single bridge between each and every unique pair of houses.
- The storm destroys each bridge with independent probability \(\frac{1}{2}\).
- John is allowed to traverse through others' houses to try to reach all of them, but he must only use the surviving bridges to get there. No vine swinging allowed.
Tagged under #ComputerScience as this problem is quite tedious to do without it, though not impossible.
Image Credit: http://hdscreen.me/wallpaper/2645876-bridges-fantasy-art-landscapes-mountains
Probability
Main Article: Probability
A probability is a number, between 0 and 1 inclusive, that represents the likelihood of an event. Discrete probability is a probability based on discrete sets of outcomes. The most basic type of probability is a uniform probability. If each outcome in a set is equally likely, then the probability of an event is equal to a ratio of cardinalities.
Let \(S\) be a sample space of outcomes. If each outcome in this set is equally likely, then the probability of an event \(A\) in \(S\) is
\[P(A)=\frac{|A|}{|S|}.\]
What is the probability of getting 53 Sundays in a leap year?
Many of the rules of probability are analogous to the rules of combinatorics. The probabilistic rules of product, sum, and complement work similarly to those same rules from combinatorics. In addition, the structure of the probabilistic principle of inclusion and exclusion is the same as PIE for sets.
A biased coin is tossed repeatedly. Assume that the outcomes of different tosses are independent and the probability of heads is \(\frac{2}{3}\) for each toss. What is the probability of obtaining an even number of heads in 5 tosses?
A discrete probability distribution is a function that takes a numerical outcome as an argument and gives a probability as a result. Discrete probability distributions can be created using the rules and guidelines described above. There are also some discrete probability distributions that show up in many problems:
- Geometric Distribution: Given repeated trials in which the probability of success is the same each time, this gives the probability that the first success will occur on a certain trial. Example: You roll a dice until you roll a 6. What is the probability that the first 6 will occur on the third roll?
- Binomial Distribution: Given a certain number of trials in which the probability of success is the same each time, this gives the probability of a certain number of successes. Example: You flip a coin 10 times. What is the probability that there will be exactly 5 heads?
- Poisson Distribution: Given a time period in which an event occurs a certain average number of times, this gives the probability that the event will occur a specific number of times. Example: A fast food drive-through gets 3 customers per minute. What's the probability they will get 4 customers in the next minute?
Although basic probabilities are based on discrete sets, the concept of probability can be extended to continuous sets by using concepts from calculus.
A point is marked at random on a unit line segment.
Find the expected value of the sum of the squares of the lengths of the two parts.
Statistics
Main Article: Statistics
A statistic is a number used to describe a set of data or a probability distribution. Statistics is widely used in many fields outside of mathematics, from biology to politics to sports. The power of statistics lies in taking a massive, varied set of data and making sense out of it. Furthermore, statistics has the power to quantify confidence in those findings. Of course, the usefulness of statistics is not without controversy, but an understanding of its theoretical underpinnings can help one avoid its misuse.
One major kind of statistic is a measure of central tendency. A measure of central tendency is a number which describes what a value of a probability distribution or data set will tend to. An expected value is the theoretical long-run average outcome of a probability experiment when it is performed many times.
A game costs $150 to play. In this game, you roll a fair six-sided die repeatedly until each of all the six numbers has been rolled at least once. You are then paid 10 times the number of rolls you made.
For example, if the rolls were 3, 5, 4, 3, 2, 5, 1, 4, 1, 3, 6, then you would get \((10)(11) = 110\) dollars.
Including the price to play, what is your expected value in this game?
Somewhat related to the expected value is the mean. The mean is the average value of a set of numerical data.
What is the mean of the first 100 positive integers?
Another major kind of statistic is a measure of variation. A measure of variation is a number which describes the distribution of a probability distribution or data set. The standard deviation of a probability distribution is a number that represents how much the outcomes differ from the expected value. Likewise, the standard deviation of a data set is a number that represents how much the elements of the set differ from the mean.
The elements of set \(S\) of real numbers with cardinality \(n\) form an arithmetic progression with common difference \(d\). Express the population standard deviation of set \(S\) in terms of \(n\) and \(d\).
An example of set \(S\) is \(\text{{2, 5, 8, 11, 14, 17}}\). It has cardinality 6, and its elements form an AP with common difference 3.
Although discrete statistics are based off of discrete events and probability distributions, these same concepts can be extended to continuous events and probability distributions using concepts from calculus.
Bijections
Main Article: Bijection, Injection, and Surjection
A bijection is a relationship between two sets such that each element in a set is paired with exactly one element in the other set, and vice versa. Bijections can be applied to problem solving by establishing a bijection between a set that is difficult to enumerate and a discrete stucture that is well understood. By establishing a bijection, one can take advantage of the known formulas and theorems that the discrete structure affords.
The three Molloy siblings, April, Bradley, and Clark, have integer ages that sum to 15. How many possible distribution of ages are there?
Note: It is possible that an age can be 0, which means that the child was just born.
One can establish a bijection between the set of distributions of ages and a set of combinations. Consider the arrangement of stars and bars below:
\[\star \star \mid \star \star \star \star \mid \star \star \star \star \star \star \star \star \star\]
This arrangement corresponds to the following distribution of ages: April - 2, Bradley - 4, Clark - 9. Note that there are 15 stars and 2 bars in the arrangement above. This gives a total of 17 objects, 2 of which are bars. Placing the bars in different spots among the 17 placements will give a new distribution of ages. Thus, a bijection can be established between the set of distributions of ages and the set of combinations of 2 objects out of 17.
The number of distributions of ages is
\[\binom{17}{2}=136.\ _\square\]
A parking lot has 10 empty spaces in a row.
6 cars arrive, each of which fills exactly 1 parking spot, chosen at random from among the available spaces. Robbie then arrives in his pick-up truck, which requires 2 empty adjacent spaces to park.
If the probability that Robbie will be able to park is \(\frac{a}{b},\) where \(a\) and \(b\) are coprime positive integers, then what is \(a+b?\)
Logic
Main Articles:
A proposition is a statement that can either be true or false. Propositional logic aims to outline the rules of how these statements can be altered and combined.
Which of the following statements are true and which are false, knowing that the entire set is uncontradictory?
S1. Statements 2 and 3 are either both true either both false.
S2. Exactly one of the statements 4 and 5 is true.
S3. Exactly one of the statements 4 and 6 is true.
S4. Exactly one of the statements 1 and 6 is true.
S5. Statements 1 and 3 are of the same type (both true or both false).
S6. Exactly one statement from statements 2 and 5 is true.
Write the answer as the concatenation of the digits 1 and 0 for the truth values of the statements (true and false) starting from S1 to S6, where for the value true corresponds 1 and for the value false corresponds 0. For example, if the first 2 statements would be true and the rest false, the answer would be 110000.
If the correct answer begins with some number of leading 0s, remove it from writing the answer. For example, if the answer is 001100, write 1100 anyway.
Similarly, Boolean algebra outlines the operations defined on variables that can take the values of true (1) or false (0). Boolean algebra is used to design computer circuits through logic gates, which take signal(s) as inputs and return a signal as an output.
The AND gates in the diagram will output a 1 if both inputs are also 1.
If A = 1, B = 1, and C = 0, what will the final output be?