Mathematics
Permutations and Combinations
Permutations and combinations are mathematical techniques used to count the number of ways to arrange or select items from a set. Permutations refer to the arrangement of items in a specific order, while combinations refer to the selection of items without considering the order. These concepts are fundamental in probability, statistics, and combinatorics.
Written by Perlego with AI-assistance
Related key terms
1 of 5
9 Key excerpts on "Permutations and Combinations"
eBook - PDF- Paul Zeitz(Author)
- 2016(Publication Date)
- Wiley(Publisher)
6 Combinatorics 6.1 Introduction to Counting Combinatorics is the study of counting. That sounds rather babyish, but in fact counting problems can be quite deep and interesting and have many connections to other branches of mathematics. For example, consider the following problem. Example 6.1.1 (Czech and Slovak 1995) Decide whether there exist 10,000 10-digit numbers divisible by 7, all of which can be obtained from one another by a reordering of their digits. On the surface, it looks like a number theory problem. But it is actually just a question of carefully counting the correct things. We will solve this problem soon, on page 204, but first we need to develop some basic skills. Our first goal is a good understanding of the ideas leading up to binomial theorem. We assume that you have studied this subject a little bit before, but intend to review it and expand upon it now. Many of the concepts will be presented as a sequence of statements for you to verify before moving on. Please do not rush; make sure that you really understand each statement! In particular, pay attention to the tiniest of arithmetical details: Good combinatorial reasoning is largely a matter of knowing exactly when to add, multiply, subtract, or divide. Permutations and Combinations Items 6.1.2–6.1.12 introduce the concepts of Permutations and Combinations, and use only addition, multiplication, and division. 6.1.2 Simple Addition. If there are varieties of soup and varieties of salad, then there are + possible ways to order a meal of soup or salad (but not both soup and salad). 6.1.3 Simple Multiplication. If there are varieties of soup and varieties of salad, then there are possible ways to order a meal of soup and salad. 6.1.4 Let and be finite sets that are disjoint ( ∩ = ∅). Then 6.1.2 is equivalent to the statement | ∪ | = || + ||.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- College Publishing House(Publisher)
The act of permuting can also refer to substitution of symbols, for instance when saying that Y 3 Z + Z 2 X +7 is obtained from X 3 Y + Y 2 Z +7 by a (cyclic) permutation of the variables X , Y , Z . These statements can be given a precise meaning by considering an appropriate symmetric group action. In combinatorics the second sense of permutation is sometimes broadened. In elementary combinatorics, the name Permutations and Combinations refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for k -permutations the order of selection is taken into account, but for k -combinations it is ignored. In fact counting k -permutations is used as a step towards counting the number of k -combinations, and also towards computing the number n ! of permutations of the set (in either of the two meanings mentioned above). However k -permutations do not correspond to such permutations unless k = n , that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S , with a finite multiset M in which some ________________________ WORLD TECHNOLOGIES ________________________ values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M . Thus for M =[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M , but [3,1,2,1,2,3,1] is not. Permutations occur, in more or less prominent ways, in almost any domain of mat-hematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science.
eBook - ePub- Bhavanari Satyanarayana, T.V. Pradeep Kumar, Shaik Mohiddin Shaw(Authors)
- 2019(Publication Date)
- CRC Press(Publisher)
HAPTER - 13Permutations and Combinations
LEARNING OBJECTIVES♦ to know the Basic Counting Principles♦ to understand the concepts: Permutations, Combinations♦ to identify different types: Circular Permutations♦ to understand Restricted Permutations, Restricted Combinations♦ to develop the problem solving skills related to Permutations, CombinationsFor most applications of computer problems, one normally needs to know, at least approximately, how much storage will be required and about how many operations are necessary. The basic idea of this lesson is to give the brief idea about the concepts of basic counting principles, Permutations and Combinations.For a set A, the number of elements in A is denoted by |A|. If A = {1, 2, 3, 4}, then |A| = (the number of elements in A) = 4. There are mainly two elementary or basic principles in counting problems. They are13.1 Basic Counting Principles
(i) Sum Rule(ii) Product Rule13.1.1 Sum Rule
If A is any set which is the union of disjoint non-empty subsets, say A1 , A2 , … An , then |A| = |A1 | + |A2 | + |A3 | + …|An |.Observe the above sum rule. There is no element common in the subsets A1 , A2 , …, An of A. Since A = A1 ∪A2 ∪… ∪ An . So each element of A appears in exactly one of the subsets A1 , A2 , …, An . In other words A1 , A2 , …, An is a partition of A.Example 13.1Suppose there are 15 boys and 10 girls in a class and we wish to select one of these students (either boy or girl) as a class representative. The number of ways selecting a boy is 15 and the number of ways selecting a girl is 10. Therefore the number of ways of selecting a student either boy or girl is 15 + 10 = 25.
No longer available |Learn moreComputational Discrete Mathematics
Combinatorics and Graph Theory
- (Author)
- 2014(Publication Date)
- Orange Apple(Publisher)
The act of permuting can also refer to substitution of symbols, for instance when saying that Y 3 Z + Z 2 X +7 is obtained from X 3 Y + Y 2 Z +7 by a (cyclic) permutation of the variables X , Y , Z . These statements can be given a precise meaning by considering an appropriate symmetric group action. In combinatorics the second sense of permutation is sometimes broadened. In elementary combinatorics, the name Permutations and Combinations refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for k -permutations the order of selection is taken into account, but for k -combinations it is ignored. In fact counting k -permutations is used as a step towards counting the number of k -combinations, and also towards computing the number n ! of permutations of the set (in either of the two meanings mentioned above). However k -permutations do not correspond to such permutations unless k = n , that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S , with a finite multiset M in which some values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M . Thus for M =[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M , but [3,1,2,1,2,3,1] is not. Permutations occur, in more or less prominent ways, in almost any domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the ________________________ WORLD TECHNOLOGIES ________________________ study of sorting algorithms in computer science.
eBook - PDF- Charalambos A. Charalambides(Author)
- 2018(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 2 Permutations and Combinations 2.1 INTRODUCTION 2.2 PERMUTATIONS DEFINITION 2.1 Let , a finite set of n elements. An ordered k-tuple , with , , is called k-permutation of the set or simply k-permutation of n. Example 2.1 (a) The 2-permutations of the set , of 4 elements, are the following: Note that, in any 2-permutation of the set , the first element can be selected from the set , of 4 elements, while, after the selection of the first element, the second element , which must be different from , can be selected from the set , of 3 elements. Thus, according to the multiplication principle, the number of 2-permutations of 4 equals . A simple counting of these permutations verifies this result. (b) The permutations of the set , of 3 elements, are the following: the number of which, according to the multiplication principle, is equal to . Example 2.2 The 2-permutations of the set , with repetition, are the following: Note that, in any 2-permutation of the set with repetition, the first element as well as the second element can be chosen from the set of 4 elements. Hence, according to the multiplication principle, the number of 2-permutations of 4, with repetition, equals . Example 2.3 The permutations of the set , of two kinds of elements with elements and element are the following: Let us pretend that we do not know the total number of these permutations. The problem of enumerating them may be transformed to an equivalent counting prob-lem, which can be solved by applying basic counting principles. In this particular case, a suitable transformation is carried out in two consecutive actions. Firstly, the two like elements are transformed to distinct, by assigning to each a second in-dex, , . Secondly, in each permutation the distinct elements and are permuted in all possible ways. Since 2 elements are permuted in only 2 ways, from each permutation 2 new permutations are constructed.
eBook - PDFHow to Count
An Introduction to Combinatorics, Second Edition
- R.B.J.T. Allenby, Alan Slomson(Authors)
- 2010(Publication Date)
- Chapman and Hall/CRC(Publisher)
17 2 C H A P T E R Permutations and Combinations 2.1 THE COMBINATORIAL APPROACH In Chapter 1 we gave examples of counting problems that we hope convinced you of their interest and importance. In this chapter we introduce two of the most basic ideas, counting permutations and counting combinations. These occur over and over again throughout this book. You may have already met these ideas in algebra in connection with the binomial theorem, but the combinatorial approach may be new to you. It can be hard to relearn a topic you are already familiar with but using a different approach. However, we encourage you to adopt the combinatorial approach, which gives more importance to counting meth-ods than to algebraic manipulation, as this is the key to much of the rest of this book. 2.2 PERMUTATIONS We begin with some problems that are very simple, but the ideas behind their solutions are of fundamental importance in many counting problems. PROBLEM 2.1 Cayley’s Café has the following menu: Cayley’s Café Starters Tomato Soup Fruit Juice Mains Lamb Chops Battered Cod Nut Bake Desserts Apple Pie Strawberry Ice How many different three-course meals could you have? 18 ◾ How to Count: An Introduction to Combinatorics, Second Edition Solution You have two choices for your starter, and, whichever choice you make, you have three choices for your main course. This makes 2 × 3 = 6 choices for the first two courses. Soup Soup Soup Juice Juice Juice | | | | | | Chops Cod Bake Chops Cod Bake In each of these six cases you have two choices for your dessert, making 6 × 2 = 12 possibilities altogether. We can set them out in Figure 2.1, which makes it clear why the number of cases multiplies at each stage and why the final answer is the product of the number of choices at each stage. So we obtain 2 × 3 × 2 = 12 as the total number of possible meals.
eBook - PDF- Thomas Koshy(Author)
- 2004(Publication Date)
- Academic Press(Publisher)
Permutations • An r -permutation of a set of n distinct elements is an ordered arrange-ment of r elements of the set. The number of r -permutations of a set of size n is denoted by P ( n , r ) (page 352). • P ( n , r ) = n ! ( n − r ) ! (page 000); P ( n , n ) = n ! (page 353). • A cyclic permutation is a circular arrangement. The number of cyclic permutations of n distinct items is ( n − 1) ! (page 355). • P ( n , r ) = P ( n − 1, r ) + rP ( n − 1, r − 1) (page 356). Derangements • A derangement is a permutation of n distinct items a 1 , a 2 , . . . , a n such that no item a i occupies position i , where 1 ≤ i ≤ n (page 360). 428 Chapter 6 Combinatorics and Discrete Probability • The number of derangements D n of n items satisfies two recurrence relations: D n = ( n − 1)( D n − 1 + D n − 2 ), n ≥ 2 where D 0 = 1 and D 1 = 0 (page 362) D n = nD n − 1 + ( − 1) n , n ≥ 1 where D 0 = 1 (page 363) • D n = n ! 1 − 1 1 ! + 1 2 ! · · · + ( − 1) n n ! , n ≥ 0 (page 363). Combinations • An r -combination of a set of n elements is a subset with size r , where 0 ≤ r ≤ n . The number of r -combinations is denoted by C ( n , r ) or n r (page 366). • C ( n , r ) = n ! r ! ( n − r ! ) (page 366) C ( n , r ) = C ( n , n − r ) (page 369) • Pascal’s identity C ( n , r ) = C ( n − 1, r − 1) + C ( n − 1, r ) (page 370). • Permutations with Repetitions The number of permutations of n items where n 1 are alike, n 2 are alike, . . . , and n k are alike, is given by n ! n 1 ! n 2 ! · · · n k ! (page 376). • Combinations with Repetitions The number of r -combinations with repetitions from a set with size n is C ( n + r − 1, r ) (page 380). • Let x 1 , x 2 , . . . , x n be n nonnegative integer variables. The equation x 1 + x 2 + · · · + x n = r has C ( n + r − 1, r ) integer solutions (page 381). • The binomial theorem Let x and y be real variables and n any nonnegative integer.
eBook - PDFMathematics
A Practical Odyssey
- David Johnson, , Thomas Mowry, , David Johnson, Thomas Mowry(Authors)
- 2015(Publication Date)
- Cengage Learning EMEA(Publisher)
Once you have selected a specific person (say, Lauren), you do not put her back into the pool of choices. When selecting items without replacement, depending on whether the order of selection is important, permutations or combinations are used to determine the total number of possible outcomes. n Permutations When more than one item is selected (without replacement) from a single cat-egory, and the order of selection is important, the various possible outcomes are called permutations . For example, when the rankings (first, second, and third place) in a talent contest are announced, the order of selection is impor-tant; Monte in first, Lynn in second, and Ginny in third place is different from Ginny in first, Monte in second, and Lynn in third. “Monte, Lynn, Ginny” and “Ginny, Monte, Lynn” are different permutations of the contestants. Naturally, these selections are made without replacement; we cannot select Monte for first place and reselect him for second place. FINDING THE NUMBER OF PERMUTATIONS Six local bands have volunteered to perform at a benefit concert, but there is enough time for only four bands to play. There is also some concern over the order in which the cho-sen bands will perform. How many different lineups are possible? EXAMPLE 1 We must select four of the six bands and put them in a specific order. The bands are selected without replacement; a band cannot be selected to play and then be reselected to play again. Because we must make four decisions, we draw four boxes and put the number of choices for each decision in each ap-propriate box. There are six choices for the opening band. Naturally, the open-ing band could not be the follow-up act, so there are only five choices for the SOLUTION Copyright 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
eBook - PDF- Richard Aufmann, Joanne Lockwood, Richard Nation, Daniel K. Clegg(Authors)
- 2017(Publication Date)
- Cengage Learning EMEA(Publisher)
Solving this problem is critical to enabling computers to interpret human speech. MATH MATTERS A standard deck of playing cards Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 700 CHAPTER 12 | Combinatorics and Probability Applying Several Counting Techniques The permutation formula is derived from the counting principle. This formula is a conve- nient way of expressing the number of ways in which the items in an ordered list can be arranged. Both the permutation formula and the counting principle are needed to solve some counting problems. EXAMPLE 4 Counting Using Several Methods Five women and four men are to be seated in a row of nine chairs. How many different seating arrangements are possible if a. there are no restrictions on the seating arrangements? b. the women sit together and the men sit together? Solution Because seating arrangements have a definite order, they are permutations. a. If there are no restrictions on the seating arrangements, then the number of seating arrangements is P( 9, 9). P( 9, 9) = 9! ( 9 − 9)! = 9! 0! = 9! = 362,880 There are 362,880 seating arrangements. b. This is a multi-stage experiment, so both the permutation formula and the counting principle will be used. There are 5! ways to arrange the women and 4! ways to arrange the men. We must also consider that either the women or the men could be seated at the beginning of the row. There are two ways to do this. By the counting principle, there are 2 ? 5! ? 4! ways to seat the women together and the men together.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
