3 Generating Functions
4 Systems of Distinct Representatives
5 Graph Theory
6 Pólya–Redfield Counting
We turn first to counting. While this sounds simple, perhaps toosimple to study, it is not. When we speak of counting, it is shorthandfor determining the size of a set, or more often, the sizes of manysets, all with something in common, but different sizes depending onone or more parameters. For example: how many outcomes are possiblewhen a die is rolled? Two dice? $n$ dice? As stated, this isambiguous: what do we mean by "outcome""? Suppose we roll two dice,say a red die and a green die. Is "red two, green three"" a differentoutcome than "red three, green two""? If yes, we are counting thenumber of possible "physical"" outcomes, namely 36. If no, there are 21. We might even be interested simply in the possible totals, inwhich case there are 11 outcomes.
You are watching: How many ways can you roll a 7 with two dice
Even the quite simple first interpretation relies on some degree ofknowledge about counting; we first make two simple facts explicit. Interms of set sizes, suppose we know that set $A$ has size $m$ and set$B$ has size $n$. What is the size of $A$ and $B$ together, that is,the size of $Acup B$? If we know that $A$ and $B$ have no elements incommon, then the size $Acup B$ is $m+n$; if they do have elements incommon, we need more information. A simple but typical problem of thistype: if we roll two dice, how many ways are there to get either 7 or11? Since there are 6 ways to get 7 and two ways to get 11, theanswer is $6+2=8$. Though this principle is simple, it is easy toforget the requirement that the two sets be disjoint, and hence to useit when the circumstances are otherwise. This principle is oftencalled the addition principle.
This principle can be generalized: if sets$A_1$ through $A_n$ are pairwise disjoint and have sizes $m_1,ldotsm_n$, then the size of $A_1cupcdotscup A_n=sum_i=1^n m_i$. Thiscan be proved by a simple induction argument.
Why do we know, without listing them all, that there are 36 outcomeswhen two dice are rolled? We can view the outcomes as two separateoutcomes, that is, the outcome of rolling die number one and theoutcome of rolling die number two. For each of 6 outcomes for thefirst die the second die may have any of 6 outcomes, so the total is$6+6+6+6+6+6=36$, or more compactly, $6cdot6=36$. Note that we arereally using the addition principle here: set $A_1$ is all pairs$(1,x)$, set $A_2$ is all pairs $(2,x)$, and so on. This is somewhatmore subtle than is first apparent. In this simple example, theoutcomes of die number two have nothing to do with the outcomes of dienumber one. Here"s a slightly more complicated example: how many waysare there to roll two dice so that the two dice don"t match? That is,we rule out 1-1, 2-2, and so on. Here for each possible value on dienumber one, there are five possible values for die number two, butthey are a different five values for each value on die numberone. Still, because all are the same, the result is $5+5+5+5+5+5=30$,or $6cdot 5=30$. In general, then, if there are $m$ possibilities forone event, and $n$ for a second event, the number of possible outcomesfor both events together is $mcdot n$. This is often called themultiplication principle.
In general,if $n$ events have $m_i$ possible outcomes, for $i=1,ldots,n$, whereeach $m_i$ is unaffected by the outcomes of other events, then thenumber of possible outcomes overall is $prod_i=1^n m_i$. This toocan be proved by induction.
Example 1.2.1 How many outcomes are possible when three dice are rolled, ifno two of them may be the same? The first two dice together have$6cdot 5=30$ possible outcomes, from above. For each of these 30outcomes, there are four possible outcomes for the third die, so thetotal number of outcomes is $30cdot 4=6cdot 5cdot 4=120$.(Note that we consider the dice to be distinguishable, that is, a rollof 6, 4, 1 is different than 4, 6, 1, because the first and seconddice are different in the two rolls, even though the numbers as a setare the same.)$square$
Example 1.2.2 Suppose blocks numbered 1 through $n$ are in a barrel; wepull out $k$ of them, placing them in a line as we do. How manyoutcomes are possible? That is, how many different arrangements of $k$blocks might we see?
This is essentially the same as the previous example: there are $k$ "spots""to be filled by blocks. Any of the $n$ blocks might appear first inthe line; then any of the remaining $n-1$ might appear next, and soon. The number of outcomes is thus $n(n-1)(n-2)cdots(n-k+1)$, by themultiplication principle. In theprevious example, the first "spot"" was die number one, the secondspot was die number two, the third spot die number three, and$6cdot5cdot4=6(6-1)(6-2)$; notice that $6-2=6-3+1$.$square$
Definition 1.2.3 The number of permutations of $n$things taken $k$ at a time is$$P(n,k)=n(n-1)(n-2)cdots(n-k+1)=n!over (n-k)!.$$$square$
A permutation of some objects is a particular linear ordering of the objects; $P(n,k)$ in effect counts two things simultaneously: thenumber of ways to choose and order $k$ out of $n$ objects. A usefulspecial case is $k=n$, in which we are simply counting the numberof ways to order all $n$ objects. This is$n(n-1)cdots(n-n+1)=n!$. Note that the second form of $P(n,k)$ fromthe definition gives $$n!over (n-n)!=n!over 0!.$$This is correct only if $0!=1$, so we adopt the standard conventionthat this is true, that is, we define $0!$ to be $1$.
Suppose we want to count only the number of ways to choose $k$ itemsout of $n$, that is, we don"t care about order. In example 1.2.1, we counted the number ofrolls of three dice with different numbers showing. The dice weredistinguishable, or in a particular order: a first die, a second, anda third. Now we want to count simply how many combinations of numbersthere are, with 6, 4, 1 now counting as the same combination as 4, 6, 1.
Example 1.2.4 Suppose we were to list all 120 possibilities in example 1.2.1. The list would containmany outcomes that we now wish to count as a single outcome; 6, 4, 1 and 4, 6, 1 would be on the list, but should not be countedseparately. How many times will a single outcome appear on the list?This is a permutation problem: there are $3!$ orders in which 1, 4, 6can appear, and all 6 of these will be on the list. In fact everyoutcome will appear on the list 6 times, since every outcome canappear in $3!$ orders. Hence, the list is too big by a factor of 6;the correct count for the new problem is $120/6=20$.$square$
Following the same reasoningin general, if we have $n$ objects, the number of ways to choose $k$of them is $P(n,k)/k!$, as each collection of $k$ objects will becounted $k!$ times by $P(n,k)$.
Definition 1.2.5 The number of subsets of size $k$ of a set of size $n$ (alsocalled an $n$-set) is$$C(n,k)=P(n,k)over k!=n!over k!(n-k)!=nchoose k.$$The notation $C(n,k)$ is rarely used; instead we use $nchoose k$, pronounced "$n$ choose $k$"".$square$
Example 1.2.6 Consider $n=0,1,2,3$. It is easy to list thesubsets of a small $n$-set; a typical $n$-set is$a_1,a_2,ldots,a_n$. A $0$-set, namely the empty set, hasone subset, the empty set; a $1$-set has two subsets, the empty setand $a_1$; a $2$-subset has four subsets, $emptyset$, $a_1$,$a_2$, $a_1,a_2$; and a $3$-subset has eight:$emptyset$, $a_1$, $a_2$, $a_3$, $a_1,a_2$,$a_1,a_3$, $a_2,a_3$, $a_1,a_2,a_3$.From these lists it is then easy to compute $nchoose k$:$$displaylinescrmatrix& laplower 3pthbox$Rule65pt0pt0.5pt$cr&0crn&1cr&2cr&3crleftvertmatrix0&lower 3.5pthbox lapsmash aise 1.5em hbox$k$1&2&3cr1cr1&1cr1&2&1cr1&3&3&1cr ight.cr$$$square$
You probably recognize these numbers: this is the beginning of Pascal"s Triangle. Each entry inPascal"s triangle is generated by adding two entries from the previousrow: the one directly above, and the one above and to the left. Thissuggests that $nchoose k=n-1choose k-1+n-1choose k$, andindeed this is true. To make this work out neatly, we adopt theconvention that $nchoose k=0$ when $kn$.
Proof.A typical $n$-set is $A=a_1,ldots,a_n$. We consider two types ofsubsets: those that contain $a_n$ and those that do not. If a$k$-subset of $A$ does not contain $a_n$, then it is a $k$-subset of $a_1,…,a_n-1$, and there are $n-1choose k$ of these. If itdoes contain $a_n$, then it consists of $a_n$ and $k-1$ elements of$a_1,…,a_n-1$; since there are $n-1choose k-1$ of these,there are $n-1choose k-1$ subsets of this type. Thus the total numberof $k$-subsets of $A$ is $n-1choose k-1+n-1choose k$.
Note that when $k=0$, $n-1choose k-1=n-1choose -1=0$, and when$k=n$, $n-1choose k=n-1choose n=0$, so that $nchoose 0=n-1choose 0$ and $nchoose n=n-1choose n-1$. These values are the boundary ones in Pascal"s Triangle.$qed$
Many counting problems rely on the sort of reasoning we haveseen. Here are a few variations on the theme.
Example 1.2.8 Six people are to sit at a round table; how many seatingarrangements are there?
It is not clear exactly what we mean to count here. If there is a"special seat"", for example, it may matter who ends up in thatseat. If this doesn"t matter, we only care about the relative positionof each person. Then it may or may not matter whether a certain personis on the left or right of another. So this question can beinterpreted in (at least) three ways. Let"s answer them all.
First, if the actual chairs occupied by people matter, then this isexactly the same as lining six people up in a row: 6 choices for seatnumber one, 5 for seat two, and so on, for a total of $6!$. If thechairs don"t matter, then $6!$ counts the same arrangement too manytimes, once for each person who might be in seat one. So the total inthis case is $6!/6=5!$. Another approach to this: since the actualseats don"t matter, just put one of the six people in a chair. Then weneed to arrange the remaining 5 people in a row, which can be done in$5!$ ways. Finally, suppose all we care about is who is next to whom,ignoring right and left. Then the previous answer counts eacharrangement twice, once for the counterclockwise order and once forclockwise. So the total is $5!/2=P(5,3)$.$square$
We have twice seen a general principle at work: if we can overcountthe desired set in such a way that every item gets counted the samenumber of times, we can get the desired count just by dividing by thecommon overcount factor. This will continue to be a useful idea. Avariation on this theme is to overcount and then subtract theamount of overcount.
See more: How Many Ounces In A Quart Of Paint ? Standard Paint Can Sizes (With Drawings)
Example 1.2.9 How many ways are there to line up six people so that aparticular pair of people are not adjacent?
Denote the people $A$ and $B$.The total number of orders is $6!$, but this counts those orders with $A$ and $B$ next to each other. How many of these are there? Think ofthese two people as a unit; how many ways are there to line up the$AB$ unit with the other 4 people? We have 5 items, so the answer is$5!$. Each of these orders corresponds to two different orders inwhich $A$ and $B$ are adjacent, depending on whether $A$ or $B$ isfirst. So the $6!$ count is too high by $2cdot5!$ and the count weseek is $6!-2cdot 5!=4cdot5!$.$square$
Ex 1.2.1How many positive factors does$2cdot3^4cdot7^3cdot11^2cdot47^5$ have?How many does $p_1^e_1p_2^e_2cdots p_n^e_n$ have, where the$p_i$ are distinct primes?
Ex 1.2.2A poker hand consists of five cards from a standard 52 carddeck with four suits and thirteen values in each suit; the order ofthe cards in a hand is irrelevant. How many hands consist of2 cards with one value and 3 cards of another value (a full house)?How many consist of 5 cards from the same suit (a flush)?
Ex 1.2.3Six men and six women are to be seated around a table, withmen and women alternating. The chairs don"t matter, only who is nextto whom, but right and left are different. How many seatingarrangements are possible?
Ex 1.2.4Eight people are to be seated around a table; the chairsdon"t matter, only who is next to whom, but right and left aredifferent. Two people, X and Y, cannot be seated next to each other.How many seating arrangements are possible?
Ex 1.2.5In chess, a rook attacks any piece in the same row or columnas the rook, provided no other piece is between them. In how many wayscan eight indistinguishable rooks be placed on a chess board so thatno two attack each other? What about eight indistinguishable rooks ona $10 imes 10$ board?
Ex 1.2.6Suppose that we want to place 8 non-attacking rooks on achessboard. In how many ways can we do this if the 16 most`northwest" squares must be empty? How about if only the 4 most`northwest" squares must be empty?
Ex 1.2.7A "legal"" sequence of parentheses is one in which the parenthesescan be properly matched, like $()(())$. It"s not hard to see that thisis possible precisely when the number of left and right parentheses isthe same, and every initial segment of the sequence has at least asmany left parentheses as right. For example, $())ldots$ cannotpossibly be extended to a legal sequence. Show that the number oflegal sequences of length $2n$ is $C_n=2nchoose n-2nchoose n+1$.The numbers $C_n$ are called the Catalan numbers.