The Central Idea
The same collection of objects can be organized in fundamentally different ways.
If order matters, we have an arrangement.
If we choose objects without caring about their order, we have a selection.
If we divide an entire collection into nonoverlapping groups, we have a partition.
The central question is therefore:
What information distinguishes one outcome from another?
Starting with a Finite Set
Let
\[ A=\{a,b,c\}. \]From these three elements, we might form an ordered arrangement such as
\[ (a,c,b), \]select a subset such as
\[ \{a,c\}, \]or partition the set as
\[ \big\{\{a,b\},\{c\}\big\}. \]Each construction uses the same original elements but records different structure.
What Is an Arrangement?
An arrangement places chosen objects into specified positions or an order.
For example,
\[ (a,b,c) \]and
\[ (b,a,c) \]are different arrangements because the first two positions are exchanged.
Arrangements are naturally represented by tuples, lists, strings, or sequences.
Order Matters in an Arrangement
Suppose three runners finish a race.
The outcome
\[ (\text{Ada},\text{Ben},\text{Cara}) \]means Ada finishes first, Ben second, and Cara third.
The outcome
\[ (\text{Ben},\text{Ada},\text{Cara}) \]is different.
The same people appear, but their positions have changed.
Arrangements of All Available Objects
An arrangement may use every available object.
For
\[ A=\{a,b,c\}, \]the complete arrangements are
\[ (a,b,c),\ (a,c,b),\ (b,a,c),\ (b,c,a),\ (c,a,b),\ (c,b,a). \]There are six.
Later lessons will develop the factorial notation that summarizes this pattern efficiently.
Partial Arrangements
An arrangement does not have to use every available object.
From
\[ A=\{a,b,c,d\}, \]a two-position arrangement could be
\[ (a,c). \]Another is
\[ (c,a). \]These are different because order matters.
Arrangements without Repetition
In some arrangements, an object may be used at most once.
For example, if three distinct books are placed on a shelf, the same physical book cannot occupy two positions simultaneously.
An arrangement such as
\[ (a,b,c) \]is allowed, while
\[ (a,a,c) \]is not if each symbol represents one distinct available object.
Arrangements with Repetition
Other arrangements allow the same symbol or option to be chosen repeatedly.
A four-digit binary string may be
\[ 1011. \]The symbol \(1\) appears three times.
Repetition is permitted because each position independently chooses from the alphabet
\[ \{0,1\}. \]Repeated Values versus Repeated Objects
It is important to distinguish repeated values from repeated physical or labeled objects.
Suppose two cards both display the number \(5\). If the cards are distinct, they may still be treated as different objects even though their printed values match.
In a string, however, repeated symbols usually mean the same symbol may be chosen again.
The model determines what counts as distinct.
What Is a Selection?
A selection chooses some objects from an available collection.
If order does not matter, a selection is naturally represented as a subset.
From
\[ A=\{a,b,c,d\}, \]choosing \(a\) and \(c\) gives
\[ \{a,c\}. \]Order Does Not Matter in an Unordered Selection
The selections
\[ \{a,c\} \]and
\[ \{c,a\} \]are the same set.
Thus an unordered selection records which elements were chosen, not the order in which they were chosen.
Selection versus Arrangement
Suppose we choose two people from
\[ \{\text{Ana},\text{Bo},\text{Cy}\}. \]If both people receive the same role, then
\[ \{\text{Ana},\text{Bo}\} \]is one selection.
If one person must be president and the other vice president, then
\[ (\text{Ana},\text{Bo}) \]and
\[ (\text{Bo},\text{Ana}) \]are different arrangements.
Roles Create Order
A problem may not literally mention positions such as first and second, yet distinct roles can create the same effect.
Choosing a chair and secretary from a group produces an ordered pair
\[ (\text{chair},\text{secretary}). \]Swapping the people changes who has which role.
Therefore the outcome is order-sensitive.
Selections of Fixed Size
A selection problem often specifies how many elements must be chosen.
For example, from
\[ A=\{a,b,c,d\}, \]the two-element selections are
\[ \{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}. \]There are six distinct selections.
Selections of Any Size
Sometimes every subset is allowed.
For
\[ A=\{a,b\}, \]the possible selections are
\[ \varnothing,\quad\{a\},\quad\{b\},\quad\{a,b\}. \]These form the power set of \(A\).
The power set records all unordered selections from the original set.
Selections without Replacement
In a selection without replacement, an object cannot be chosen again after it has been selected.
Choosing two different books from a shelf is a typical example.
If
\[ A=\{a,b,c\}, \]then a two-element subset such as
\[ \{a,b\} \]contains two distinct elements.
Selections with Replacement
In a selection with replacement, a selected option remains available for later choices.
For example, drawing a colored token, recording its color, returning it, and drawing again permits the same color to appear repeatedly.
The resulting object may be represented as a list or multiset depending on whether order matters.
When Repetition Matters but Order Does Not
Suppose we choose three scoops of ice cream from the flavors
\[ \{\text{vanilla},\text{chocolate},\text{strawberry}\}. \]If two vanilla scoops and one chocolate scoop are allowed, repetition matters.
If the order of the scoops is irrelevant, then the outcome is not an ordinary set because vanilla appears twice.
Such structures are commonly modeled using multisets, which will appear more fully later.
What Is a Partition?
A partition of a set divides the set into nonempty, nonoverlapping subsets called blocks.
Every element of the original set must belong to exactly one block.
For
\[ A=\{a,b,c,d\}, \]one partition is
\[ \big\{\{a,b\},\{c,d\}\big\}. \]The Three Partition Conditions
A collection of subsets
\[ B_1,B_2,\ldots,B_k \]forms a partition of \(A\) when three conditions hold.
- Every block \(B_i\) is nonempty.
- Different blocks do not overlap.
- The union of all blocks is the entire set \(A\).
Symbolically,
\[ B_i\ne\varnothing, \] \[ B_i\cap B_j=\varnothing\quad\text{for }i\ne j, \]and
\[ \bigcup_{i=1}^{k}B_i=A. \]Example of a Valid Partition
Let
\[ A=\{1,2,3,4,5\}. \]Then
\[ \mathcal{P} = \big\{\{1,4\},\{2\},\{3,5\}\big\} \]is a partition.
Every block is nonempty, no element occurs in two blocks, and every element of \(A\) appears somewhere.
Example of an Invalid Partition: Overlap
Consider
\[ \big\{\{1,2\},\{2,3\}\big\}. \]The element \(2\) belongs to both blocks.
Therefore,
\[ \{1,2\}\cap\{2,3\}=\{2\}\ne\varnothing. \]The blocks overlap, so this is not a partition.
Example of an Invalid Partition: Missing Elements
Let
\[ A=\{1,2,3,4\}. \]The collection
\[ \big\{\{1,2\},\{3\}\big\} \]is not a partition of \(A\) because the element \(4\) is missing.
A partition must cover the entire original set.
Example of an Invalid Partition: Empty Block
A partition does not include empty blocks.
For example,
\[ \big\{\{1,2\},\{3\},\varnothing\big\} \]is not treated as a partition with three blocks.
The empty set contributes no elements and is excluded from the block structure.
Partitions Use Every Element
A selection may leave some elements unused.
A partition does not.
If
\[ A=\{a,b,c,d\}, \]then choosing
\[ \{a,c\} \]is a selection.
A partition must place \(a,b,c,d\) into blocks so that each appears exactly once.
Blocks Are Usually Unordered
In an ordinary set partition,
\[ \big\{\{a,b\},\{c,d\}\big\} \]and
\[ \big\{\{c,d\},\{a,b\}\big\} \]represent the same partition.
The blocks themselves form a set, so their written order does not matter.
Order within a Block Usually Does Not Matter
Because each block is a set,
\[ \{a,b\}=\{b,a\}. \]Therefore
\[ \big\{\{a,b\},\{c,d\}\big\} \]does not change if the elements inside a block are written in another order.
Labeled Groups
Sometimes groups have distinct labels or roles.
Suppose people are assigned to
\[ \text{Team A} \]and
\[ \text{Team B}. \]Swapping the membership of Team A and Team B generally creates a different assignment because the group labels matter.
This differs from an ordinary unlabeled set partition.
Unlabeled Groups
If a problem merely divides people into two groups without naming the groups, then
\[ \big\{\{a,b\},\{c,d\}\big\} \]is the same grouping regardless of which block is written first.
Recognizing whether groups are labeled prevents accidental double counting.
Partition by a Property
A set can be partitioned according to a shared property.
For example, the integers may be divided into the even and odd integers:
\[ 2\mathbb{Z} \]and
\[ 2\mathbb{Z}+1. \]Every integer belongs to exactly one of these two classes.
Thus parity partitions \(\mathbb{Z}\) into two blocks.
Partitions and Equivalence Classes
Partitions are closely related to equivalence relations.
When an equivalence relation groups together objects considered equivalent, its equivalence classes form a partition of the underlying set.
Conversely, a partition can define an equivalence relation by declaring two elements equivalent when they belong to the same block.
This connection will be developed more fully in the lesson on equivalence classes.
Arrangements as Functions from Positions
An arrangement can be modeled as a function from a set of positions to a set of available objects.
For a three-position arrangement,
\[ f:\{1,2,3\}\to A. \]If repetition is forbidden, the function must be injective.
If repetition is allowed, the same object may be assigned to multiple positions.
Selections as Indicator Decisions
An unordered selection from a finite set can be described by deciding, for each element, whether it is included.
For
\[ A=\{a,b,c\}, \]the selection
\[ \{a,c\} \]corresponds to the inclusion pattern
\[ (1,0,1), \]where \(1\) means selected and \(0\) means not selected.
This gives an important bridge between subsets and binary strings.
Every Subset Corresponds to a Binary String
Suppose
\[ A=\{a_1,a_2,\ldots,a_n\}. \]Any subset \(S\subseteq A\) can be represented by a binary string
\[ b_1b_2\cdots b_n \]where
\[ b_i= \begin{cases} 1,& a_i\in S,\\ 0,& a_i\notin S. \end{cases} \]This correspondence explains why an \(n\)-element set has
\[ 2^n \]subsets.
Example: Three Elements and Eight Selections
Let
\[ A=\{a,b,c\}. \]Each element may be either included or excluded.
The eight subsets are
\[ \varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}. \]This matches
\[ 2^3=8. \]Arrangement Decisions Are Sequential
Suppose three distinct positions must be filled from four distinct objects without repetition.
The first position has four possible choices.
After one object is used, the second position has three choices.
The third position then has two choices.
This creates the product
\[ 4\cdot3\cdot2. \]Later lessons will formalize this reasoning with the product principle and permutation notation.
Selection Decisions Remove Ordering
Suppose we select two elements from
\[ \{a,b,c\}. \]If we first count ordered outcomes, we obtain
\[ (a,b),(b,a),(a,c),(c,a),(b,c),(c,b). \]But each unordered selection appears twice.
Therefore the distinct selections are only
\[ \{a,b\},\{a,c\},\{b,c\}. \]Ignoring order changes the count.
Partitions Remove Even More Ordering
Partition problems may ignore both the order of elements within blocks and the order of the blocks themselves.
For example,
\[ \big\{\{a,b\},\{c,d\}\big\} \]remains the same partition if we reverse either block or swap the two blocks.
This makes partition counting structurally different from ordinary arrangement counting.
Example: Assigning Seats
Suppose Ana, Bo, and Cy occupy three labeled seats.
The seats create positions:
\[ (\text{seat 1},\text{seat 2},\text{seat 3}). \]Therefore assigning the three people to the seats is an arrangement problem.
Changing who occupies seat \(1\) changes the outcome.
Example: Choosing a Committee
Suppose three people are chosen from a larger group to form a committee, and all committee members have the same role.
The committee
\[ \{\text{Ana},\text{Bo},\text{Cy}\} \]is unchanged if its members are listed in another order.
Therefore this is a selection problem.
Example: Dividing into Project Teams
Suppose six people are divided into three unlabeled pairs.
Every person must belong to exactly one pair.
The pairs do not overlap.
The order of the pairs does not matter.
Therefore the outcome is a partition into blocks of size \(2\).
Example: Distributing into Labeled Departments
Suppose employees are assigned to
\[ \text{Sales},\quad\text{Operations},\quad\text{Research}. \]These groups are labeled.
Moving a person from Sales to Research changes the assignment even if the same group sizes remain.
The problem therefore contains partition-like grouping together with labeled destinations.
Constraints Change the Structure
Real problems often impose restrictions.
An arrangement may require two objects to remain adjacent.
A selection may require at least one object from a particular category.
A partition may require blocks of equal size.
Before counting, identify both the underlying structure and every constraint.
Exact Size Constraints
A selection may require exactly \(r\) objects from \(n\) available objects.
A partition may require block sizes such as
\[ 2+2+3=7. \]An arrangement may require exactly \(r\) occupied positions.
Size constraints determine which outcomes belong to the state space.
At-Least and At-Most Constraints
Constraints may also be expressed with inequalities.
A committee may require at least \(2\) members from one category.
A group may contain at most \(5\) objects.
A string may permit no more than \(3\) occurrences of a symbol.
Such conditions filter the collection of otherwise possible structures.
Distinguishing Objects from Categories
Suppose four balls consist of two red and two blue balls.
If the individual balls are labeled,
\[ R_1,R_2,B_1,B_2, \]then all four are distinct objects.
If only color matters, then the two red balls may be indistinguishable and the two blue balls may be indistinguishable.
These models produce different arrangement and selection counts.
Distinguishable and Indistinguishable Objects
Distinguishable objects can be told apart within the model.
Indistinguishable objects are treated as identical.
For example, rearranging the letters in
\[ \text{BOOK} \]differs from rearranging four entirely distinct symbols because the two letters \(O\) are identical.
Later counting lessons will formalize how repeated objects affect the number of distinct arrangements.
Partitions of Integers versus Partitions of Sets
The word partition has more than one mathematical use.
A set partition divides a set into disjoint nonempty blocks.
An integer partition writes a positive integer as a sum of positive integers where order is ignored.
For example,
\[ 5=3+2=2+2+1=4+1. \]These are related discrete ideas but are not the same object.
Example: Integer Partitions of Four
The positive integer \(4\) has the partitions
\[ 4, \] \[ 3+1, \] \[ 2+2, \] \[ 2+1+1, \]and
\[ 1+1+1+1. \]The expressions
\[ 3+1 \]and
\[ 1+3 \]represent the same integer partition because order is ignored.
Arrangements, Selections, and State Spaces
Each structural choice creates a different set of possible states.
A password system may use ordered strings.
A committee problem may use subsets.
A clustering problem may use partitions.
Correctly defining the outcome space is essential before probability, optimization, or algorithmic search can begin.
Common Error: Counting Order When Order Does Not Matter
Suppose a two-person committee contains Ana and Bo.
Writing
\[ (\text{Ana},\text{Bo}) \]and
\[ (\text{Bo},\text{Ana}) \]as two different outcomes would double-count the same unordered committee.
If roles are identical, use an unordered selection.
Common Error: Ignoring Roles
Suppose one person is selected as chair and another as secretary.
The assignment
\[ (\text{Ana},\text{Bo}) \]is not the same as
\[ (\text{Bo},\text{Ana}). \]The roles create positional information, so order matters.
Common Error: Allowing Overlap in a Partition
A partition cannot place one element in multiple blocks.
Thus
\[ \big\{\{a,b\},\{b,c\}\big\} \]fails because \(b\) appears twice.
Every original element must belong to exactly one block.
Common Error: Leaving Elements Unassigned
Suppose
\[ A=\{a,b,c,d\}. \]The collection
\[ \big\{\{a,b\},\{c\}\big\} \]does not partition \(A\) because \(d\) is absent.
A partition must cover the entire set.
Common Error: Treating Labeled Groups as Unlabeled
If two teams are called Team A and Team B, then the assignment
\[ (\text{Team A}=\{a,b\},\text{Team B}=\{c,d\}) \]differs from
\[ (\text{Team A}=\{c,d\},\text{Team B}=\{a,b\}). \]Labels create distinguishable roles for the groups.
Common Error: Forgetting Whether Repetition Is Allowed
The rules for
\[ 111 \]depend on the model.
It is perfectly valid as a string over
\[ \{0,1\}, \]but it would be impossible as an arrangement of three distinct objects if only one object labeled \(1\) were available.
Always determine whether choices are made with or without repetition.
A Reliable Classification Procedure
- Identify the available objects or symbols.
- Determine whether all objects must be used or only some.
- Ask whether order or position matters.
- Ask whether roles or group labels make positions distinguishable.
- Determine whether repetition is allowed.
- If grouping occurs, check whether every element must be assigned.
- Check whether groups may overlap.
- Determine whether groups are labeled or unlabeled.
- Record any size or membership restrictions.
- Only then choose a counting method.
Example: Classifying Several Problems
Consider four scenarios.
- Assign gold, silver, and bronze medals to three different finalists: arrangement.
- Choose three finalists to receive identical certificates: selection.
- Divide all finalists into unlabeled discussion groups: partition.
- Assign every finalist to one of three named departments: labeled grouping or assignment.
The objects may be the same, but the structure of the outcome changes the mathematics.
Practice 1: Arrangement or Selection?
Three students are chosen from a class to receive identical participation awards.
Is this fundamentally an arrangement or a selection?
Practice 2: Roles Matter
Two students are chosen, one as president and one as treasurer.
Does order matter? Explain.
Practice 3: List the Selections
Let
\[ A=\{a,b,c\}. \]List all two-element selections from \(A\).
Practice 4: List the Arrangements
Let
\[ A=\{a,b,c\}. \]List all two-position arrangements without repetition.
Practice 5: Valid Partition?
Let
\[ A=\{1,2,3,4\}. \]Is
\[ \big\{\{1,3\},\{2,4\}\big\} \]a partition of \(A\)?
Practice 6: Invalid Partition?
Let
\[ A=\{1,2,3,4\}. \]Explain why
\[ \big\{\{1,2\},\{2,3\},\{4\}\big\} \]is not a partition.
Practice 7: Binary Selection Pattern
Let
\[ A=\{a,b,c,d\}. \]Using the order \(a,b,c,d\), what subset is represented by the binary pattern
\[ 1010? \]Practice 8: Number of Subsets
How many selections of any size are possible from a five-element set?
Practice 9: Labeled or Unlabeled?
Four people are divided into Team Red and Team Blue.
Are the two groups labeled or unlabeled?
Practice 10: Classify the Structure
A password contains six characters selected from an alphabet, and characters may repeat.
Is the password best modeled as an arrangement, selection, or partition?
Practice Answers
Practice 1
It is a selection. The awards are identical, so choosing Ana, Bo, and Cy gives the same outcome regardless of the order in which their names are listed.
Practice 2
Yes. The roles are distinct.
If Ana is president and Bo is treasurer, that differs from Bo being president and Ana being treasurer. The outcome is therefore arrangement-like.
Practice 3
\[ \boxed{\{a,b\},\{a,c\},\{b,c\}}. \]Practice 4
\[ \boxed{(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)}. \]Practice 5
Yes. Both blocks are nonempty, they do not overlap, and together they contain every element of \(A\).
Therefore,
\[ \boxed{\big\{\{1,3\},\{2,4\}\big\}\text{ is a partition of }A.} \]Practice 6
The element \(2\) appears in two blocks:
\[ 2\in\{1,2\} \]and
\[ 2\in\{2,3\}. \]Therefore the blocks overlap, so the collection is not a partition.
Practice 7
The first and third elements are selected:
\[ \boxed{\{a,c\}}. \]Practice 8
Each of five elements has two possibilities: included or excluded.
\[ \boxed{2^5=32}. \]Practice 9
They are labeled because Team Red and Team Blue have different names. Swapping the memberships changes the assignment.
Practice 10
It is an arrangement. Character positions matter, and repetition is allowed.
What to Remember
- An arrangement preserves order or positional roles.
- A selection records which objects are chosen when order is irrelevant.
- A partition divides an entire set into nonempty, disjoint blocks.
- Every element belongs to exactly one block of a partition.
- Labeled groups behave differently from unlabeled blocks.
- Repetition may be allowed or forbidden depending on the model.
- Distinguishable and indistinguishable objects lead to different structures.
- Every subset of an \(n\)-element set corresponds to a binary inclusion string.
- Constraints must be identified before a counting method is chosen.
The most important habit is: decide exactly what makes two outcomes different before you begin counting them.
Where We Go Next
Arrangements, selections, and partitions describe ways of organizing discrete objects. The next step is to describe how objects can be connected or assigned to one another.
The next lesson, Relations and Finite Mappings, develops ordered-pair relations, mappings between finite sets, and the structural patterns created by these connections.