Skip to main content
Engineering LibreTexts

7.2: Permutations and Combinations

  • Page ID
    1635
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Learning Objectives
    • Discusses the basics of combinations and permutations, and how to calculate the probability of certain events, such as n-bit errors in a codeword.

    The lottery "game" consists of picking

    Answering such questions occurs in many applications beyond games. In digital communications, for example, you might ask how many possible double-bit errors can occur in a codeword. Numbering the bit positions from 1 to N, the answer is the same as the lottery problem with k=6. Solving these kind of problems amounts to understanding permutations - the number of ways of choosing things when order matters as in baseball lineups - and combinations - the number of ways of choosing things when order does not matter as in lotteries and bit errors.

    Calculating permutations is the easiest. If we are to pick k numbers from a pool of n, we have n choices for the first one. For the second choice, we have n-1. The number of length-two ordered sequences is therefore be n(n-1). Continuing to choose until we make k choices means the number of permutations is

    \[n(n-1)(n-2)...(n-k+1) \nonumber \]

    This result can be written in terms of factorials as

    \[\frac{n!}{(n-k)!} \nonumber \]

    with

    \[n!=n(n-1)(n-2)...1 \nonumber \]

    For mathematical convenience, we define 0!=1.

    When order does not matter, the number of combinations equals the number of permutations divided by the number of orderings. The number of ways a pool of k things can be ordered equals k!. Thus, once we choose the nine starters for our baseball game, we have

    \[9!=362,880 \nonumber \]

    different lineups! The symbol for the combination of k things drawn from a pool of n is

    \[\binom{n}{k} \nonumber \]

    and equals

    \[\frac{n!}{(n-k)!k!} \nonumber \]

    Exercise \(\PageIndex{1}\)

    What are the chances of winning the lottery? Assume you pick 6 numbers from the numbers 1-60.

    Solution

    \[\binom{60}{6}=\frac{60!}{54!6!}=50,063,860 \nonumber \]

    Combinatorials occur in interesting places. For example, Newton derived that the n-th power of a sum obeyed the formula

    \[(x+y)^{n}=\binom{n}{0}x^{n}+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^{2}+...+\binom{n}{n}y^{n} \nonumber \]

    Exercise \(\PageIndex{1}\)

    What does the sum of binomial coefficients equal? In other words, what is

    \[\sum_{k=0}^{n}\binom{n}{k} \nonumber \]

    Solution

    Because of Newton's binomial theorem, the sum equals

    \[(1+1)^{n}=2^{n} \nonumber \]

    A related problem is calculating the probability that any two bits are in error in a length-

    \[p^{2}(1-p)^{n-2} \nonumber \]

    The probability of a two-bit error occurring anywhere equals this probability times the number of combinations:

    \[\binom{n}{2}p^{2}(1-p)^{n-2} \nonumber \]

    Note that the probability that zero or one or two, etc. errors occurring must be one; in other words, something must happen to the codeword! That means that we must have

    \[\binom{n}{0}(1-p)^{n}+\binom{n}{1}(1-p)^{n-1}+\binom{n}{2}p^{2}(1-p)^{n-2}+...+\binom{n}{n}p^{n}=1 \nonumber \]

    Can you prove this?


    This page titled 7.2: Permutations and Combinations is shared under a CC BY 1.0 license and was authored, remixed, and/or curated by Don H. Johnson via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?