We've updated our
Privacy Policy effective December 15. Please read our updated Privacy Policy and tap

Guias de estudo > Boundless Algebra

Combinatorics

Counting Rules and Techniques

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Learning Objectives

Describe the different rules and properties for combinatorics

Key Takeaways

Key Points

  • The rule of sum (addition rule), rule of product (multiplication rule), and inclusion-exclusion principle are often used for enumerative purposes.
  • Bijective proofs are utilized to demonstrate that two sets have the same number of elements.
  • Double counting is a technique used to demonstrate that two expressions are equal. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in a discrete context.
  • Generating functions and recurrence relations are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations.
  • Double counting is a technique used to demonstrate that two expressions are equal.

Key Terms

  • polynomial: An expression consisting of a sum of a finite number of terms: each term being the product of a constant coefficient and one or more variables raised to a non-negative integer power.
  • combinatorics: A branch of mathematics that studies (usually finite) collections of objects that satisfy specified criteria.
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Combinatorial techniques are applicable to many areas of mathematics, and a knowledge of combinatorics is necessary to build a solid command of statistics. It involves the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties. Aspects of combinatorics include: counting the structures of a given kind and size, deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria. Aspects also include finding "largest," "smallest," or "optimal" objects, studying combinatorial structures arising in an algebraic context, or applying algebraic techniques to combinatorial problems.

Combinatorial Rules and Techniques

Several useful combinatorial rules or combinatorial principles are commonly recognized and used. Each of these principles is used for a specific purpose. The rule of sum (addition rule), rule of product (multiplication rule), and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets have the same number of elements. Double counting is a method of showing that two expressions are equal. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in a discrete context. Generating functions and recurrence relations are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations. Each of these techniques is described in greater detail below.

Rule of Sum

The rule of sum is an intuitive principle stating that if there are [latex]a[/latex] possible ways to do something, and [latex]b[/latex] possible ways to do another thing, and the two things can't both be done, then there are [latex]a + b[/latex] total possible ways to do one of the things. More formally, the sum of the sizes of two disjoint sets is equal to the size of the union of these sets.

Rule of Product

The rule of product is another intuitive principle stating that if there are [latex]a[/latex] ways to do something and [latex]b[/latex] ways to do another thing, then there are [latex]a \cdot b[/latex] ways to do both things.

Inclusion-Exclusion Principle

The inclusion-exclusion principle is a counting technique that is used to obtain the number of elements in a union of multiple sets. This counting method ensures that elements that are present in more than one set in the union are not counted more than once. It considers the size of each set and the size of the intersections of the sets. The smallest example is when there are two sets: the number of elements in the union of [latex]A[/latex] and [latex]B[/latex] is equal to the sum of the number of elements in [latex]A[/latex] and [latex]B[/latex], minus the number of elements in their intersection. See the diagram below for an example with three sets.

Bijective Proof

A bijective proof is a proof technique that finds a bijective function [latex]f: A \rightarrow B[/latex] between two finite sets [latex]A[/latex] and [latex]B[/latex], which proves that they have the same number of elements, [latex]|A| = |B|[/latex]. A bijective function is one in which there is a one-to-one correspondence between the elements of two sets. In other words, each element in set [latex]B[/latex] is paired with exactly one element in set [latex]A[/latex]. This technique is useful if we wish to know the size of [latex]A[/latex], but can find no direct way of counting its elements. If [latex]B[/latex] is more easily countable, establishing a bijection from [latex]A[/latex] to [latex]B[/latex] solves the problem.

Double Counting

Double counting is a combinatorial proof technique for showing that two expressions are equal. This is done by demonstrating that the two expressions are two different ways of counting the size of one set. In this technique, a finite set [latex]X[/latex] is described from two perspectives, leading to two distinct expressions for the size of the set. Since both expressions equal the size of the same set, they equal each other.

Pigeonhole Principle

The pigeonhole principle states that if [latex]a[/latex] items are each put into one of [latex]b[/latex] boxes, where [latex]a>b[/latex], then at least one of the boxes contains more than one item. This principle allows one to demonstrate the existence of some element in a set with some specific properties. For example, consider a set of three gloves. In such a set, there must be either two left gloves or two right gloves (or three of left or right). This is an application of the pigeonhole principle that yields information about the properties of the gloves in the set.

Generating Function

Generating functions can be thought of as polynomials with infinitely many terms whose coefficients correspond to the terms of a sequence. The (ordinary) generating function of a sequence [latex]a_n[/latex] is given by: [latex]\displaystyle f(x) = \sum_{n=0}^{\infty} a_{n}x^{n}[/latex] whose coefficients give the sequence [latex]\left \{ a_{0}, a_{1}, a_{2},... \right \}[/latex].

Recurrence Relation

A recurrence relation defines each term of a sequence in terms of the preceding terms. In other words, once one or more initial terms are given, each of the following terms of the sequence is a function of the preceding terms. The Fibonacci sequence is one example of a recurrence relation. Each term of the Fibonacci sequence is given by [latex]F_{n} = F_{n-1} + F_{n-2}[/latex], with initial values [latex]F_{0}=0[/latex] and [latex]F_{1}=1[/latex]. Thus, the sequence of Fibonacci numbers begins: [latex]\displaystyle 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...[/latex]

Permutations

A permutation of a set of objects is an arrangement of those objects in a particular order; the number of permutations can be counted.

Learning Objectives

Calculate the number of arrangements of ordered objects using permutations

Key Takeaways

Key Points

  • Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. For example, there are six permutations of the set [latex]{1,2,3}[/latex], namely [latex](1,2,3)[/latex], [latex](1,3,2)[/latex],[latex](2,1,3)[/latex], [latex](2,3,1)[/latex], [latex](3,1,2)[/latex], and [latex](3,2,1)[/latex].
  • The number of permutations of [latex]n[/latex] distinct objects is [latex]n \cdot (n − 1) \cdot (n − 2) \cdots 2 \cdot 1[/latex]. This is called [latex]n[/latex] factorial, and written [latex]n![/latex].
  • When deciding permutations of a subset from a larger set, it is often useful to divide one factorial by another to determine the number of permutations possible. For example, the first six cards from a deck of cards would have [latex]\frac {52!}{46! }[/latex] permutations possible, or about 14.7 billion.

Key Terms

  • factorial: The result of multiplying a given number of consecutive integers from [latex]1[/latex] to the given number. In equations, it is symbolized by an exclamation mark ([latex]![/latex]). For example, [latex]5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120[/latex].
  • permutation: An ordering of a finite set of distinct elements.

Permutations

A permutation of a set of objects is an arrangement of those objects into a particular order. For example, there are six permutations of the set [latex]{1,2,3}[/latex]: [latex](1,2,3)[/latex], [latex](1,3,2)[/latex], [latex](2,1,3)[/latex], [latex](2,3,1)[/latex], [latex](3,1,2)[/latex], and [latex](3,2,1)[/latex]. One might define an anagram of a word as a permutation of its letters.
image The 6 permutations of 3 balls: If one has three different colored balls, there are six distinct ways to order them, as shown. These six distinct orderings are as follows: red-green-blue, red-blue-green, green-red-blue, green-blue-red, blue-red-green, and blue-green-red.

The number of permutations of [latex]n[/latex] distinct objects is given by:

[latex]\displaystyle n \cdot (n − 1) \cdot (n − 2) \cdots 2 \cdot 1[/latex] This is called [latex]n[/latex] factorial and is written [latex]n![/latex]. In other words, a factorial is to multiply all the numbers from [latex]1[/latex] up to this number. So [latex]5![/latex] means [latex]1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120[/latex]. Thus, [latex]120[/latex] is the number of permutations possible for a set of five distinct objects.

Example

In the game of Solitaire, seven cards are dealt out at the beginning: one face-up, and the other six face-down. A complete card deck has [latex]52[/latex] cards. Assuming that the only card that is seen is the [latex]7[/latex] of spades, how many possible "hands" (the other six cards) can be underneath? What makes this a permutation problem is that the order matters: if an ace is hiding somewhere in those six cards, it makes a difference whether the ace is on the first position, the second, etc. Permutation problems can always be addressed as an example of the multiplication rule, with one small twist.
image One stack of cards in a game of solitaire: To find out how many possible combinations of cards there are below the seven of spades, we use the concept of permutations to calculate the possible arrangements of cards.

How many cards might be in the first position, directly under the showing [latex]7[/latex]? The answer is 51. That card can be anything except the [latex]7[/latex] of spades.

If any given card is in the first position, how many cards might be in second position? The answer is [latex]50[/latex]. The seven of spades and the next card have both been dealt. So there are possible cards left for the second position. So how many possibilities are there for the first two positions combined? The answer is [latex]51 \cdot 50[/latex]. How many possibilities are there for all six positions? The answer is [latex]51 \cdot 50 \cdot 49 \cdot 48 \cdot 47 \cdot 46[/latex], or approximately [latex]1.3 \cdot 10^{10}[/latex]; about [latex]13[/latex] billion possibilities! This result can be expressed more concisely by using factorials. Note that [latex]\frac {7!}{5! }[/latex] can also be written as [latex]\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}{1\cdot 2\cdot 3\cdot 4\cdot 5}[/latex]. Most of the terms cancel, leaving only [latex]6×7=42[/latex]. Consider another example, [latex]\frac {51!}{45! }[/latex]. If all of the terms are written out, the first [latex]45[/latex] terms cancel, leaving [latex]46 \cdot 47 \cdot 48 \cdot 49 \cdot 50 \cdot 51[/latex] in the numerator. Instead of typing into a calculator six numbers to multiply, or sixty numbers or six hundred depending on the problem, the answer to a permutation problem can be found by dividing two factorials. In many calculators, the factorial option is located under the "probability" menu for this reason.

General Considerations

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. The study of permutations generally belongs to the field of combinatorics. Permutations occur, in more or less prominent ways, in almost every 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 study of sorting algorithms in computer science.

Permutations of Distinguishable Objects

The number of permutations of distinct elements can be calculated when not all elements from a given set are used.

Learning Objectives

Calculate the number of permutations of [latex]n[/latex] objects taken [latex]k[/latex] at a time

Key Takeaways

Key Points

  • If all objects in consideration are distinct, they can be arranged in [latex]n![/latex] permutations, where [latex]n[/latex] represents the number of objects.
  • If not all the objects in a set of [latex]n[/latex] unique elements are chosen, the above formula can be modified to: [latex]\displaystyle \frac {n!}{(n-k)! }[/latex], where [latex]k[/latex] represents the number of selected elements.
  • When solving for quotients of factorials, the terms of the denominator can cancel with the terms of the numerator, thus eliminating perhaps the majority of terms to be multiplied.

Key Terms

  • factorial: The result of multiplying a given number of consecutive integers from [latex]1[/latex] to the given number. In equations, it is symbolized by an exclamation mark ([latex]![/latex]). For example, [latex]5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120[/latex].
  • permutation: An ordering of a finite set of distinct elements.
Recall that, if all objects in a set are distinct, then they can be arranged in [latex]n![/latex] possible permutations, where [latex]n[/latex] represents the number of objects. The quantity [latex]n![/latex] is given by: [latex]\displaystyle n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1[/latex] It is easy enough to use this formula to count the number of possible permutations of a set of distinct objects; for example, the number of permutations of three differently-colored balls. However, consider a situation where not all of the elements in a set of distinct objects are used in each permutation. For example, what if [latex]7[/latex] cards are chosen from among a full deck of [latex]52[/latex]? In this case, not all of the cards from the deck are chosen for each possible permutation. There exists a formula for solving permutation problems such as this one, which would otherwise be nearly impossible to determine.

Permutations of a Partial Set

If not all of the objects in a set of unique elements are chosen, the following formula is used. This formula determines the number of possible permutations of [latex]k[/latex] elements selected from the set of [latex]n[/latex] elements: [latex]\displaystyle \frac {n!}{(n-k)! }[/latex] To understand the application of this concept, consider a race in which [latex]3[/latex] different prizes are awarded to the top [latex]3[/latex] fastest competitors. If [latex]25[/latex] competitors participate in the race, in how many distinct orders could the [latex]3[/latex] prizes be awarded? To solve this problem, we want to evaluate the number of possible permutations of  [latex]3[/latex]elements from the set of [latex]25[/latex] elements; in other words, [latex]k = 3[/latex] and [latex]n=25[/latex]. Plugging these values into the formula, we have: [latex]\displaystyle \frac {25!}{(25-3)! } = \frac {25!}{22!} [/latex] Remember that both [latex]25![/latex] and [latex]22![/latex] contain the terms [latex]22 \cdot 21 \cdots 2 \cdot 1[/latex]. Thus, these values cancel from the numerator and denominator, and the equation can be simplified: [latex-display][/latex-display] [latex] \displaystyle \begin{align} \frac{25!}{22!} &= \frac{25 \cdot 24 \cdot 23 \cdot 22 \cdot 21 \cdots 2 \cdot 1}{22 \cdot 21 \cdots 2 \cdot 1} \\ &= 25 \cdot 24 \cdot 23 \\ &= 13,800 \end{align}[/latex] There are [latex]13,800[/latex] possible permutations in which the [latex]3[/latex] top prizes may be awarded to the [latex]25[/latex] race competitors.

General Considerations

It is worth noting that this formula does not exclude what we might call 'duplicate' permutations. In other words, the order of the elements selected does matter. Consider [latex]3[/latex] cards drawn from a pack: an ace of spades, a [latex]10[/latex] of diamonds, and a [latex]3[/latex] of clubs. The hand is exactly the same as the following: a [latex]10[/latex] of diamonds, an ace of spaces and a [latex]3[/latex] of clubs. If you are playing a game in which the order of your cards does not matter, you will only want to count each permutation of cards once. The formula introduced here does not apply to such situations. [latex-display][/latex-display]

Permutations of Nondistinguishable Objects

The expression revealing the number of permutations of distinct items can be modified if not all items in the set are distinct.

Learning Objectives

Calculate the number of permutations of a given set of objects, some being non distinguishable

Key Takeaways

Key Points

  • Some sets include repetitions of certain elements. In these cases, the number of possible permutations of the items cannot be expressed by [latex]n![/latex], where [latex]n[/latex] represents the number of elements, because this calculation would include a multiplicity of possible states.
  • To correct for the multiplicity of certain permutations, divide the factorial of the total number of elements by the product of the factorials of the number of each repeated element.
  • The expression for number of permutations with repeated elements is: [latex]\frac {n!}{n_1!n_2!n_3!... }[/latex] where [latex]n[/latex] is the total number of terms in a sequence and [latex]n_1[/latex], [latex]n_2[/latex], and [latex]n_3[/latex] are the number of repetitions of different elements.

Key Terms

  • multiplicity: The number of values for which a given condition holds.
  • permutation: An ordering of a finite set of distinct elements.
Recall that the number of possible permutations of a set of [latex]n[/latex] distinct elements is given by [latex]n![/latex]: [latex]\displaystyle n \cdot (n-1) \cdot(n-2) \cdots 2 \cdot 1[/latex] This can be easily tested. The number [latex]1[/latex] can be arranged in just one [latex]1![/latex] way. The numbers [latex]1[/latex] and [latex]2[/latex] can be arranged in two [latex]2![/latex] ways: [latex](1,2)[/latex] and [latex](2,1)[/latex]. The numbers [latex]1[/latex], [latex]2[/latex], and [latex]3[/latex] can be arranged in [latex]3![/latex] ways: [latex](1,2,3)[/latex], [latex](1,3,2)[/latex], [latex](2,1,3)[/latex], [latex](2,3,1)[/latex], [latex](3,1,2)[/latex], and [latex](3,2,1)[/latex]. This rule holds true for sets of any size, so long as the elements are all distinct. But what if some elements are repeated? Repetition of some elements complicates the calculation of permutations, because it allows for there to be multiple ways in which a specific order of elements can be arranged. For example, given the numbers [latex]1[/latex], [latex]3[/latex], and [latex]3[/latex] in a set, there are 2 ways to obtain the order [latex](3,1,3)[/latex]. To correct for the "multiplicity" of certain permutations, we must divide the factorial of the total number of elements by the product of the factorials of the number of each repeated element. This can generally be represented as: [latex]\displaystyle \frac {n!}{n_1!n_2!n_3!... }[/latex] Where [latex]n[/latex] is the total number of terms in a sequence, and [latex]n_1[/latex], [latex]n_2[/latex], and [latex]n_3[/latex] represent the number of repetitions of different elements. To understand why we would divide by the number of repetitions, consider that [latex]2[/latex]elements can be arranged in a total of [latex]2![/latex] distinct ways, [latex]3[/latex] elements can be arranged in a total of [latex]3![/latex] distinct ways, and so on. When we encounter multiplicity in a permutation, we must account for it by dividing these possible arrangements out of the total number of permutations that would be possible if all of the elements were distinct.

Example: Consider the set of numbers:

[latex]\displaystyle (15, 17, 24, 24, 28)[/latex] There are five terms, so [latex]n=5[/latex]. However, two of the terms are the same; their value is [latex]24[/latex]. Thus, the number of possible distinct permutations in the set is: [latex-display]\displaystyle{\frac {5!}{2! }=60}[/latex-display] The same logic can apply to more complicated systems.

Example: Consider the set:

[latex]\displaystyle (0, 0, 0, 2, 4, 4, 7, 7, 7, 7, 7, 8, 8)[/latex] In total, there are [latex]13[/latex] elements. These include many repetitions: [latex]0[/latex] is seen 3 times, [latex]4[/latex]and [latex]8[/latex] each are observed twice, and there are [latex]5[/latex] instances of the number [latex]7[/latex]. Thus, the number of possible distinct permutations can be calculated by: [latex]\displaystyle \frac {13! }{2!\cdot 2!\cdot 3!\cdot 5! }= 2,162,160[/latex] This logic can be applied to problems involving anagrams of given words.

Example: Consider how many distinct ways you can order the letters of the word "waterfall."

The word waterfall consists of [latex]9[/latex] letters in total, so [latex]n=9[/latex]. The letter "a" appears twice, giving a value of [latex]2[/latex] for [latex]n_{1}[/latex]. Similarly, the letter "l" appears twice, yielding [latex]n_{2} = 2[/latex]. Thus, the number of distinct permutations for the letters in "waterfall" can be calculated as: [latex]\displaystyle \frac {9! }{2!\cdot 2!}= 90,720[/latex]

Combinations

A combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter.

Learning Objectives

Calculate the number of ways of selecting several things out of a larger group (where order doesn't matter) using combinations

Key Takeaways

Key Points

  • A combination is a mathematical concept where one counts the number of ways one can select several elements out of a larger group.
  • Unlike a permutation, when determining the number of combinations, order does not matter.
  • Formally, a [latex]k[/latex]-combination of a set [latex]S[/latex] is a subset of [latex]k[/latex] distinct elements of [latex]S[/latex]. If the set has [latex]n[/latex] elements the number of [latex]k[/latex]-combinations is equal to the binomial coefficient: [latex]\begin{pmatrix} n\\ k \end{pmatrix} = \frac {n(n-1)...(n-k+1)}{k(k-1)...1}[/latex], which can be written using factorials as [latex]\frac {n!}{k!(n-k)! }[/latex] whenever [latex]k \le n[/latex] and which is zero when [latex]k > n[/latex].

Key Terms

  • combination: A way of selecting elements from a set, where order does not matter.
  • binomial coefficient: A coefficient of any of the terms in the expansion of the binomial power [latex](1+x)^n[/latex].
In mathematics, a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter. In smaller cases, it is possible to count the number of combinations. For example, given [latex]3[/latex] pieces of fruit: an apple, an orange and a pear. There are [latex]3[/latex] combinations of [latex]2[/latex] that can be drawn from this set: an apple and a pear, an apple and an orange, or a pear and an orange. Combinations can refer to the combination of [latex]n[/latex] things taken [latex]k[/latex] at a time with or without repetition. In the above example, repetition was not allowed. If, however, it was possible to have [latex]2[/latex] of any [latex]1[/latex] kind of fruit there would be [latex]3[/latex] more combinations: [latex]2[/latex] apples, [latex]2[/latex] oranges, and [latex]2[/latex] pears. To understand the difference between a permutation and combination, consider a deck of [latex]52[/latex] cards, from which a poker hand ([latex]5[/latex] cards) is dealt. How many possible poker hands are there? At first glance, this may seem like a permutation question, where one might consider how many distinct ways there are to make a stack of cards. However, there is one important difference: order does not matter in this problem. When dealt a poker hand during a game, order does not matter so you will have the same hand regardless of the order in which the cards are dealt. Combination problems involve such scenarios. To approach such a question, begin with the permutations: how many possible poker hands are there, if order does matter? Recall the permutation formula: [latex]\displaystyle{\frac{n!}{(n-k)!}}[/latex], where [latex]n[/latex] is the number of distinct objects in the set, and [latex]k[/latex] is the number of objects selected. In this case, we can calculate the number of permutations as: [latex][/latex] [latex]\displaystyle \begin{align} \frac{52!}{(52-5)!}&=\frac{52!}{47!}\\ &=52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \end{align}[/latex] This yields approximately [latex]311.9[/latex] million possible poker hands. However, one has to count every possible hand many different times in this calculation. How many different times is one counting each distinct hand? The key insight is that this second question—"How many different times is one counting each distinct hand?" is itself a permutation question. It is the same as the question "How many different ways can these five cards be rearranged in a hand?" There are [latex]5[/latex] possibilities for the first card, [latex]4[/latex] for the second, and so on. The answer is [latex]5![/latex], which is [latex]120[/latex]. So, since every possible hand has been counted [latex]120[/latex] times, divide our earlier result by [latex]120[/latex] to find that there are [latex]\frac {52!}{(47!)(5! )}[/latex], or about [latex]2.6[/latex] million possible poker hands. Combinations turn out to have a surprisingly large number of applications. Consider the following questions:
  • A school offers [latex]50[/latex] classes. Each student must choose [latex]6[/latex] of them to fill out a schedule. How many possible schedules can be made?
  • A basketball team has [latex]12[/latex] players, but only [latex]5[/latex] will start. How many possible starting teams can they field?
  • Your computer contains [latex]300[/latex] videos, but you can only fit [latex]10[/latex] of them on your phone. How many possible ways can you load your phone?
Each of these is a combinations question, and can be answered exactly like the card scenario. Since this type of question comes up in so many different contexts, it is given a special name and symbol. The last question would be referred to as "[latex]300[/latex] choose [latex]10[/latex]" and written [latex]\begin{pmatrix} 300\\ 10 \end{pmatrix}[/latex]. It is calculated as [latex]\frac {300!}{(290!)(10! )}[/latex], for reasons explained above. Each possible combination of [latex]k[/latex] distinct elements of a set [latex]S[/latex] is known as a [latex]k[/latex]-combination. If the set has [latex]n[/latex] elements, the number of [latex]k[/latex]-combinations is equal to [latex-display]\begin{pmatrix} n\\ k \end{pmatrix} = \dfrac {n(n-1)...(n-k+1)}{k(k-1)...1}[/latex-display] Which can be written using factorials as [latex-display]\dfrac {n!}{k!(n-k)! }[/latex-display] Whenever [latex]k \leq n[/latex], and which is zero when [latex]k > n[/latex]. The set of all [latex]k[/latex]-combinations of a set [latex]S[/latex] is often denoted by [latex]\begin{pmatrix} S \\ k \end{pmatrix}[/latex], which is read as "[latex]S[/latex] choose [latex]k[/latex]," such as in the phone example above. The set of [latex]k[/latex]-combinations may also be denoted in certain texts by [latex]C(n,k)[/latex], or by a variation such as [latex]C_k^n[/latex], [latex]_nC_k[/latex], or [latex]^nC_k[/latex].

General Considerations

The number of [latex]k[/latex]-combinations, or [latex]\begin{pmatrix} S \\ k \end{pmatrix}[/latex], is also known as the binomial coefficient, because it occurs as a coefficient in the binomial formula. The binomial coefficient is the coefficient of the [latex]x^k[/latex] term in the polynomial expansion of [latex](1+x)^n[/latex]. [latex][/latex]

Licenses & Attributions

CC licensed content, Shared previously

CC licensed content, Specific attribution