Chapter Summary

Chapter Summary

Investigation

Suppose you have a huge box of animal crackers containing plenty of each of 10 different animals. For the counting questions below, carefully examine their similarities and differences, and then give an answer. The answers are all one of the following: \[P(10,6),\quad {10 \choose 6},\quad 10^6,\quad {15 \choose 9}.\]

1. How many animal parades containing 6 crackers can you line up?

2. How many animal parades of 6 crackers can you line up so that the animals appear in alphabetical order?

3. How many ways could you line up 6 different animals in alphabetical order?

4. How many ways could you line up 6 different animals if they can come in any order?

5. How many ways could you give 6 children one animal cracker each?

6. How many ways could you give 6 children one animal cracker each so that no two kids get the same animal?

7. How many ways could you give out 6 giraffes to 10 kids?

8. Write a question about giving animal crackers to kids that has the answer \({10\choose 6}\).

With all the different counting techniques we have mastered in this last chapter, it might be difficult to know when to apply which technique. Indeed, it is very easy to get mixed up and use the wrong counting method for a given problem. You get better with practice. As you practice, you start to notice some trends that can help you distinguish between types of counting problems. Here are some suggestions that you might find helpful when deciding how to tackle a counting problem and checking whether your solution is correct.

• Remember that you are counting the number of items in some list of outcomes. Write down part of this list. Write down an element in the middle of the list how are you deciding whether your element really is in the list? Could you get this element more than once using your proposed answer?

• If generating an element on the list involves selecting something (for example, picking a letter or picking a position to put a letter, etc.), can the things you select be repeated? Remember, permutations and combinations select objects from a set without repeats.

• Does order matter? Be careful here, and be sure you know what your answer really means. We usually say that order matters when you get different outcomes when the same objects are selected in different orders. Combinations and sticks and stones are used when order does not matter.

• There are four possibilities when it comes to order and repeats. If order matters and repeats are allowed, the answer will look like \(n^k\). If order matters and repeats are not allowed, we have \(P(n,k)\). If order doesn't matter and repeats are allowed, use sticks and stones. If order doesn't matter and repeats are not allowed, use \({n\choose k}\). But be careful: this only applies when you are selecting things, and you should make sure you know exactly what you are selecting before determining which case you are in.

• Think about how you would represent your counting problem in terms of sets or functions. We know how to count different sorts of sets and different types of functions.

• As we saw with combinatorial proofs, you can often solve a counting problem in more than one way. Do that, and compare your numerical answers. If they don't match, something is amiss.

While we have covered many counting techniques, we have really only scratched the surface of the large subject of enumerative combinatorics. There are mathematicians doing original research in this area even as you read this. Counting can be really hard.

In the next chapter, we will approach counting questions from a very different direction, and in doing so, answer infinitely many counting questions at the same time. We will create sequences of answers to related questions.

이제 너 계산기는 이것을 해결하지 않지만, 그 조각은 계산 가능합니다. 아래의 하나를 시도하거나 자신의 것을 입력하십시오.

⌨ 종류 ✎ 그려

수학 문제

π 해결

연습 (3)

먼저 종이에 각각을 시도해 보세요. 확인하기 위해 답을 드러내세요. 확인된 답은 각 단계의 솔버에서 열 수 있습니다.

1. Give a counting question where the answer is \(8\cdot 3 \cdot 3 \cdot 5\). Give another question where the answer is \(8 + 3 + 3 + 5\).

   끝내주는 걸 힌트

   답을 드러내세요

   You own 8 purple bow ties, 3 red bow ties, 3 blue bow ties, and 5 green bow ties. How many ways can you select one of each color bow tie to take with you on a trip? \(8 \cdot 3 \cdot 3 \cdot 5\) ways. How many choices do you have for a single bow tie to wear tomorrow? \(8 + 3 + 3 + 5\) choices.

2. Explain using lattice paths why \(\sum_{k=0}^n {n \choose k} = 2^n\).

   끝내주는 걸 힌트

   답을 드러내세요

   \(2^n\) is the number of lattice paths which have length \(n\), since for each step you can go up or right. Such a path would end along the line \(x + y = n\). So you will end at \((0,n)\), or \((1,n-1)\) or \((2, n-2)\) or or \((n,0)\). Counting the paths to each of these points separately, give \({n \choose 0}\), \({n \choose 1}\), \({n \choose 2}\), , \({n \choose n}\) (each time choosing which of the \(n\) steps to be to the right). These two methods count the same quantity, and so are equal.

3. For which of the parts of the previous problem ( ) does it make sense to interpret the counting question as counting some number of functions? Say what the domain and codomain should be, and whether you are counting all functions, injections, surjections, or something else.

   끝내주는 걸 힌트

   답을 드러내세요

   1. You are giving your professor 4 types of cookies coming from 10 different types of cookies. This does not lend itself well to a function interpretation. We could say that the domain contains the 4 types you will give your professor and the codomain contains the 10 you can choose from, but then counting injections would be too much (it doesn't matter if you pick type 3 first and type 2 second, or the other way around, just that you pick those two types).

   2. We want to consider injective functions from the set \(\{\) most, second most, second least, least \(\) to the set of 10 cookie types. We want injections because we cannot pick the same type of cookie to give most and least of (for example).

   3. This is not a good problem to interpret as a function. The problem is that the domain would have to be the 12 cookies you bake, but these elements are indistinguishable (there is not a first cookie, second cookie, etc.).

   4. The domain should be the 12 shapes, the codomain the 10 types of cookies. Since we can use the same type for different shapes, we are interested in counting all functions here.

   5. Here we insist that each type of cookie be given at least once, so now we are asking for the number of surjections of those functions counted in the previous part.

자신의 작업을 유지

무료 계정은 모든 수업에 노트를 추가, 당신이 완료 한 기록, 당신이 해결 한 문제를 한 곳에, 그리고 당신이이 페이지에 대해 물어 수업 지도자. 수학 자체는 모두에게 열려 있습니다, 로그인 여부.

가입하기 로그인

여기서 사용된 기호

기호를 탭하면 전체 정의, 이미지 및 각 문자의 의미를 확인할 수 있습니다.

\sum_{k=1}^{n} a_ksummation
Add a_k for k = 1 up to n.P(A)probability, conditional probability
Chance of A; chance of A given that B happened.n!factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.\binom{n}{k}binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).\prod_{k=1}^{n} a_kproduct
Multiply a_k for k = 1 up to n.\emptysetempty set, cardinality
The set with no elements; the number of elements of A.

사람들이 묻는 질문

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

이 페이지의 일부는 다음에서 변경되었습니다. Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). 여기서 압축하고 다시 설명; 오류는 우리의.

에 더 Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs