Binary samples

Section 8.2 Binary samples

Many counting problems resolve to counting the number of binary samples from a given set that are ordered or unordered, and do or do not allow for repetition. Loosely speaking, a binary sample is when we take a set of objects and partition them into two groups. (We will not attempt to define this formally.) It is useful to consider one set of “chosen,” or “on,” or “1” objects and the second set of “unchosen,” or “off,” or “0” objects. Binary samples can be further divided into four types:

A binary sample is ordered when the chosen objects can be distinguished between one another in the context of the sample. Being chosen first is different from being chosen second, etc. A binary sample is unordered when the chosen objects cannot be distinguished from one another in the context of the sample.
A binary sample allows replacement or allows repetition when an object may be chosen more than once. Otherwise, the sample does not allow replacement or repetition. (The context informs us whether “replacement” or “repetition” is the better word, but they are mathematically synonymous.)

So the four types of binary samples are ordered with replacement, ordered without replacement, unordered without replacement, and unordered with replacement. The list in the previous sentence was ordered based on how difficult that type of sample is to learn how to count.

It is my experience that students have difficulty deciding which of these categories a context falls into. So, what follows is an excruciatingly thorough list of examples of binary samples, and the type of each.

A word from an alphabet is an ordered sample with repetition. Take for instance the word doggie from our 26-letter case-insensitive alphabet. The letters d, o, g, i, and e were chosen. Because this is a different “word” from eggoid, the order in which the letters are chosen matters. (In discrete math and computer science a “word” need not have meaning.) Since g is chosen twice, we have repetition. (We say “repetition” this time because the letters repeat.)

In discrete math, “an alphabet” can be any set. Another example of a word is the bit string 001010101, which is a word from the alphabet \(\{0,1\}\text{.}\) Being able to count bit strings is very useful for being able to count more complicated types of objects.

Sometimes, for security reasons, we would rather a password not repeat characters (so that a less discerning user cannot set their password to be 111111). In this case, we consider ordered samples without repetition.
Let \(A=\{a_1, a_2, \ldots, a_m\}\) and \(B=\{b_1,b_2,\ldots,b_n\}\) be finite sets. Consider a function \(f:A\to B\) that assigns each element of \(A\) a unique element of \(B\text{.}\) How much functions are there from \(A\) to \(B\text{?}\) Well, note that we can view such a function as a word of \(m\) characters, where in each of the \(m\) positions we place one of the \(n\) elements of \(B\text{.}\) Therefore, there as many functions as there are \(m\)-letter words from the alphabet \(B\text{,}\) so functions too may be regarded as ordered samples with repetition.

The powerful counting technique on display here is correspondence. Suppose \(X\) and \(Y\) are two sets. If we know the number of elements of \(X\) and also know that each element of \(X\) (in this case, words) corresponds to exactly one element of \(Y\) (in this case, functions) and vice-versa, then we also know the number of elements of \(Y\text{.}\)
Suppose you have a deck of 52 cards and you intend to draw 5 of them. In the most common setting, this is an unordered sample without replacement, because typically in games you draw the cards without putting any back and the order of cards in your hand is unimportant. However, we can come up with a variety of unusual games where you put the cards back (or, replace them) or do remember the order in which they were drawn.
Speaking of decks of cards, the shuffling of a deck of cards represents an ordered sample without replacement. It is ordered because the order of cards in the deck affects the outcome of the game. It is a sample without replacement because no card appears in the deck twice.
Suppose we will create a team of a certain number of people from a fixed group of participants. Often discrete math texts call these “committees,” because faculty are obsessed with committees although students have likely never encountered one before. Regardless, a single individual cannot serve on a team of three people twice (otherwise it is just a team of two people), so these samples do not involve repetition. Depending on the context, they can be ordered or unordered. They are ordered if each person on the team has a different role. If each person on the team has the same role, they are unordered.
Suppose instead that we have a fixed group of participants, a desired number of teams to create, but want to decide how many participants each team will have. This is a deceptive problem, because our universe of objects shifts from the participants themselves to the teams. Consider that for each person, we are choosing a team; and that when multiple people are on a team, we are choosing the team more than once. So, this is an unordered sample with replacement. It is confusing that a example involving teams allows for replacement, so it is very important that you think about what set of objects is being sampled from. We call this set of objects the universe.
Consider a set \(X\) and the subsets of \(X\) that have a fixed cardinality \(r\text{.}\) When we write down a set, we do not care about the order in which we write down the objects, and we do not write down an object more than once. Therefore, a subset is an unordered sample without replacement, in the sense that we are choosing some objects to be in the subset and not choosing the others. (This is another critically important example for understanding combinatorics more broadly.)
You flip a coin a certain number of times. How many ways can you get \(r\) heads? Well, we are choosing some of the coin flips to be heads. Once a flip is heads, it cannot be heads again or tails, so there is no repetition. Furthermore, it does not matter which heads is the first heads or the second, we are just interested in the number of heads. So, this sample is unordered without replacement as well.
How many bit strings of fixed length have \(r\) 1's? We are choosing some of the digits to be 1's. Once a digit is a 1, it cannot be a 1 again or a 0, so there is no repetition. Furthermore, it does not matter which 1 is the first 1 or the second, we are just interested in the number of 1's. So, this sample is also unordered without replacement (and you should be experiencing a significant case of déjà vu).
Polynomials are very interesting counting objects. Consider the polynomial

\begin{equation*} (x_1+x_2+\cdots + x_k)^n. \end{equation*}

When we write down a term of this polynomial we must choose each of the terms a certain number of times. The terms can be repeat, and multiplication doesn't care about order. So, the number of terms is an unordered sample with replacement.

Even better, we can use counting techniques to derive each coefficient as well. If \(n=2\text{,}\) the coefficients count unordered binary samples without replacement. Otherwise, the samples are no longer binary; however, we can still arrive at their values by using binary sample methods.