Permutations and Ordered Arrangements | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 5.4 Free with a free account

Permutations and Ordered Arrangements

Discrete Mathematics · Chapter 5: Counting Methods and Basic ProbabilitySection 5.4 · lesson 30 of 879 min · free with a free account

← The Pigeonhole PrincipleNext lesson: Probability of Permutation Events →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Counting arrangements in which order matters.

  • Use factorial notation to count full orderings
  • Derive and apply the permutation formula
  • Adjust the count when some items are identical
  • Choose the right formula for a scenario

Transcript

Everything said in the video, section by section (1,275 words). Read along, or search it.

Counting Methods and Basic Probability

Permutations and Ordered Arrangements

This section counts arrangements in which order matters. They're called permutations. We'll build factorial notation, then a general formula for arranging some of a collection, and then the adjustment needed when some items can't be told apart. Everything here is about the counts themselves. Turning counts into probabilities comes in section five point five.

The Opening Problem

Every Ordering, or Just the Top 3?

A continuous integration pipeline queues up six independent verification checks, with no dependencies between them. The order they run in shows up in the build log. How many distinct run orders are possible, for all six checks? A related but different question comes from a hackathon. It awards distinct first, second, and third place prizes among nine teams. How many ways can just those three placements be handed out, in order, without accounting for every other team's position? The first question asks for every ordering of a whole collection. The second asks for ordered ways to pick out and arrange only part of it. Both are answered by permutations. Counts of arrangements, in which order matters.

Factorial Notation

Counting All Possible Orderings

Start with arranging all n items of a group of distinct items, every check in some order, with none left out. Fill the sequence one position at a time, using the multiplication rule from section five point two. There are n choices for the first position. Once that's made, n minus one items remain for the second. Then n minus two for the third, and so on, down to one choice for the last. The product of all those counts is called n factorial, written n with an exclamation mark. It's the number of orderings of n distinct items. By convention, zero factorial is one. There's exactly one way to arrange zero items. The empty arrangement. So the six pipeline checks have six factorial run orders. Six times five times four times three times two times one, which is seven hundred twenty.

Ordering a Subset

Stop After r Positions

The hackathon question is different in kind. Only three placements are filled, out of nine teams. The six teams outside the top three don't appear in the count at all. Filling just r positions out of n distinct items works the same way. n choices for the first position, n minus one for the second, and so on, stopping after r positions. The r-th position has n minus r plus one choices left. So the product has exactly r consecutive descending terms. Now multiply and divide that product by n minus r factorial, the product of everything from n minus r down to one. That doesn't change the value. But the top now runs all the way down to one, so it's n factorial. The result is n factorial over n minus r factorial.

Theorem

The Permutation Formula

That's the permutation formula. The number of ordered arrangements of r items, chosen from n distinct items, is written n P r. It equals n factorial, over n minus r factorial, for r from zero up to n. When r equals n, it gives n factorial over zero factorial, which is n factorial over one. That's just n factorial, consistent with before. And that's exactly why zero factorial is defined to be one, rather than left undefined. Without that convention, the formula would break down right at the boundary case, r equals n.

Worked Example 2

3 Ordered Prizes Among 9 Teams

Now the hackathon. Here n is nine and r is three. Nine P three is nine factorial over six factorial. Everything from six down cancels, leaving nine times eight times seven, which is five hundred four. So there are five hundred four distinct ways to award the three placements. The same picture works with eight teams. Eight choices for first place, seven remaining for second, and six for third. And the other five teams play no role in the count at all. Setting r equal to n would fill every position, and reduce the formula to plain n factorial.

Checking in Code

Factorial and Permutation, Built In

Python's built-in functions confirm both hand computations. The factorial of six prints seven hundred twenty, the number of run orders for all six checks. The perm function, with nine and three, prints five hundred four, the ordered placements of three of nine teams. And computing nine factorial divided by six factorial directly gives five hundred four as well, matching the perm function.

Repeated Objects

When Items Aren't All Distinguishable

Both the factorial count and the permutation formula assume every item is distinguishable from every other. Swapping any two always gives a visibly different sequence. That assumption fails when a collection has duplicates. Suppose a queue of six tasks has two identical lint tasks, three identical test tasks, and one unique deploy task. Treat all six as temporarily distinguishable, by mentally labeling the duplicates. Lint one, lint two, test one, test two, test three. That gives six factorial, seven hundred twenty labeled orderings. But many of those look identical once the invented labels are dropped. Swapping lint one and lint two changes nothing that's actually visible in the queue. For a fixed visible arrangement, the two lint tasks can be relabeled in two factorial ways. And independently, the three test tasks in three factorial ways. So every visible arrangement was counted two factorial times three factorial, which is twelve times over.

Figure 2

2 Labelings, 1 Visible Queue

This picture shows the collapse for one visible queue. The top two rows are labeled orderings. They differ only in which lint task comes first, highlighted in gold. Drop the labels, and both become the same visible queue at the bottom. Lint, test, lint, deploy, test, test. Count all the relabelings, two factorial for the lint tasks and three factorial for the test tasks, and twelve labeled orderings collapse onto each visible one.

Theorem and Worked Example 3

Permutations of a Multiset

That gives the formula for permutations of a multiset. Take n items made of k groups of identical items, with sizes n one through n k, adding up to n. The number of distinguishable orderings is n factorial, divided by the product of each group's factorial. Dividing by each group's factorial removes exactly the overcounting caused by treating that group's identical items as distinct. For the task queue, n is six, and the group sizes are two, three, and one. That's seven hundred twenty over two times six times one, which is seven hundred twenty over twelve, or sixty. So there are sixty distinguishable orderings. Far fewer than the seven hundred twenty counted by treating every task as distinct.

Summary Table

Choosing the Right Formula

This table sorts out which formula to use. If every item is used, and all are distinct, it's n factorial. If only r of the n distinct items are arranged, it's n P r, n factorial over n minus r factorial. And if every item is used, but there are groups of duplicates, divide n factorial by each group's factorial. These formulas count arrangements only. Turning a count into a probability is section five point five, and arranging items around a circle is section five point six.

Takeaways

Order Matters - and So Do Duplicates

To summarize. n factorial counts the orderings of n distinct items. And zero factorial is one, chosen so that later formulas stay consistent at their boundary cases. n P r counts ordered arrangements of r items out of n distinct items. It's the same position-by-position count, stopping after r positions. Setting r equal to n gives back n factorial. Both assume every item is distinguishable from every other one. When there are groups of identical items, treating them as distinct overcounts. Dividing by each group's factorial removes exactly that overcount. Here's something to think about. A student counts the task queue's orderings as six P six, which is seven hundred twenty. They reason that n P r counts ordered arrangements. Explain precisely why seven hundred twenty overcounts. Which assumption built into n P r does this scenario violate? And what should the correct count be?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Permutations and Ordered Arrangements

What is a permutation, and what does n factorial count?
A permutation is an ordered arrangement of items, where order matters. The number n! counts the orderings of all n distinct items, since there are n choices for the first spot, n-1 for the second, and so on down to 1. For example, six distinct checks can run in 6! = 720 orders. By convention, 0! = 1.
How do you derive and use the permutation formula _nP_r?
The formula _nP_r = \frac{n!}{(n-r)!} counts ordered arrangements of r items chosen from n distinct items. It comes from multiplying r descending choices, n(n-1)\cdots(n-r+1), then multiplying and dividing by (n-r)!. For 3 ordered prizes among 9 teams, _9P_3 = \frac{9!}{6!} = 9\cdot 8\cdot 7 = 504.
How do you count arrangements when some items are identical?
Divide n! by the factorial of each group's size: \frac{n!}{n_1!\,n_2!\cdots n_k!}. Treating identical items as distinct overcounts, and each group's factorial removes that overcount. For a queue of 6 tasks with 2 identical lint tasks, 3 identical test tasks, and 1 deploy task, the count is \frac{6!}{2!\,3!\,1!} = \frac{720}{12} = 60.
How do I decide whether to use n!, _nP_r, or the formula for identical items?
Match the formula to the scenario. If all n items are used and all are distinct, use n!. If only r of n distinct items are arranged, use \frac{n!}{(n-r)!}. If all items are used but some are identical, divide n! by each group's factorial. A common mistake is using _6P_6 = 720 for a queue with duplicates, which overcounts.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →