\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section7.3Excursion: Partitions
Whenever we subdivide a set into categories, we are using a partition of sets. For example, we might subdivide students at a university into three categories: full-time student, part-time student, or students who are not currently enrolled. Partitions are useful in counting because they give non-overlapping cases. For example, the total number of students at a university is the sum of the number of full-time students, the number of part-time students, and the number of students who are not currently enrolled.
In this section, we define the partition of a set and a related concept– the partition of a natural number. Partitions of natural numbers come up frequently in number theory and because listing or counting partitions is difficult, it is common in advanced computer science classes to work with algorithms to generate partitions.
Given a set, we might want to categorize its elements in such a way that each element of the set is in exactly one category. Let’s make this concept formal.
A partition of a set \(S\) is a collection of nonempty subsets \(T_1, T_2, \ldots, T_k\) such that each element of \(S\) is in exactly one of the subsets \(T_i\text{.}\) Notice that a partition satisfies two properties:
\(\displaystyle S = T_1 \cup T_2 \cup \cdots \cup T_k\)
One partition is just the set \(\{a,b,c\}\text{.}\) If we group the elements into two sets we get three more partitions: \(\{a,b\} \cup \{c\}\text{,}\)\(\{a,c\} \cup \{b\}\text{,}\) and \(\{a\} \cup \{b,c\}\text{.}\) There is one final partition: \(\{a\} \cup \{b\} \cup \{c\}\text{.}\)
At times, we are only interested in the sizes of the sets in a partition. For example, in Definition 7.3.1 our set \(S\) had six elements and the subsets had two, three, and one element. Note that \(6 = 2 + 3 + 1\text{.}\) This example motivates our next definition.
A partition is a formal sum of positive integers listed in non-increasing order. For example, \(5+3+3+2\) is a partition since \(5 \ge 3 \ge 3 \ge 2\text{.}\)
The parts of a partition are the numbers being added. For example, the partition \(5+3+3+2\) has four parts: 5, 3, 3, and 2. Notice that repeats are counted. A partition can have only one part. For example, the partition 13 has only one part: 13.
For any positive integer \(n\text{,}\) a partition of the integer \(n\) is any partition where the sum of the positive integers in the partition is \(n\text{.}\) For example, \(5+3+3+2\) is a partition of 13 because \(5+3+3+2=13\) and 13 is also a partition of 13.
The (Young) diagram of the partition \(a_1+ a_2+a_3+\ldots +a_m\) of the integer \(n\) is a drawing of \(n\) squares with \(a_1\) squares in the first row, \(a_2\) squares in the second row, through \(a_m\) squares in the \(m\)th row where the squares are drawn justified to the left. For example, the partition \(5+3+3+2\) has the diagram shown in Figure 7.3.4 which has five squares in the first row, three squares in the second row, three squares in the third row, and two squares in the fourth row.
Figure7.3.4.The diagram of the partition \(5+3+3+2\) of the integer 13.
If \(T_1 \cup T_2 \cup \cdots \cup T_k\) is a partition of a set \(S\) having \(n\) elements and if we order the sets \(T_i\) such that the number of elements in each set are nonincreasing, then \(|T_1|+|T_2|+ \ldots +|T_k|\) is a partition of \(n\text{.}\)
We often look at all of the partitions of a particular integer. For example, there are three partitions of the integer three: \(3\text{,}\)\(2+1\text{,}\) and \(1+1+1\text{.}\) The corresponding diagrams are drawn in Figure 7.3.7.
Let \(\mathbb{P}_{10}\) be the set of all partitions of the integer 10. The function \(\fn{maxpart}:\mathbb{P}_{10} \to \mathbb{N}\) is defined by \(\fn{maxpart}(\alpha)\) is the first part of \(\alpha\text{.}\)
Identify the domain and codomain of \(\fn{maxpart}\text{.}\)Solution.
The domain is \(\mathbb{P}_{10}\) and the codomain is \(\mathbb{N}\text{.}\)
Give an example of a partition \(\alpha\) of the integer 10 such that \(\fn{maxpart}(\alpha)=2\text{.}\) Is it unique?
Solution.
Note that \(2+2+2+2+2\) is a partition of 10 and \(\fn{maxpart}(2+2+2+2+2)=2\text{.}\) It is not unique because, for example, \(\fn{maxpart}(2+2+2+2+1+1)=2\) as well.
It can be difficult to know if you have found all partitions of an integer and there is no explicit formula for the number of partitions of an integer. One tool that can help check any list is the idea of conjugate partitions.
The conjugate of the partition \(\alpha\) is the partition \(\beta = b_1+b_2+ \ldots +b_k\) where \(b_1\) is the number of squares in the first column of the diagram for \(\alpha\text{,}\)\(b_2\) is the number of squares in the second column of the diagram for \(\alpha\text{,}\) and so on through \(b_k\) is the number of squares in the \(k^{\text{ th } }\) column of the diagram for \(\alpha\) and where \(k\) is the number of columns in the diagram for \(\alpha\text{.}\) For example, the conjugate of the partition \(3+1\) is the partition \(2+1+1\) as we see in Example 7.3.10.
The diagram has two squares in the first column, one square in the second column, and one square in the third column. Therefore, the conjugate of \(3+1\) is the partition \(2+1+1\) shown on the right in Figure 7.3.11.
Given the diagram of a partition, when can reflect the squares across the line of slope -1 (\(\backslash\)) through the upper level corner of the diagram to get the diagram of the conjugate.
Find the conjugate of each partition of three and draw a double-headed arrow from each partition to its conjugate or a loop from a partition to itself if the partition is self-conjugate.
A classmate conjectures that for any odd integer \(n\text{,}\) there exists a unique (only one) self-conjugate partition of \(n\text{.}\) Do you agree? Justify your answer.
Example7.3.16Conjugation function on partitions of an integer.
Let \(\mathbb{P}_4\) be the set of partitions of the integer four. Define the function \(\fn{conj}: \mathbb{P}_4 \to \mathbb{P}_4\) by \(\fn{conj}(\alpha) =\) the conjugate of \(\alpha\text{.}\)
Calculate \(\fn{conj}(3+1)\) and \(\fn{conj}(2+2)\text{.}\)Solution.
In this notation, \(\fn{conj}(3+1)=2+1+1\) and \(\fn{conj}(2+2)=2+2\text{.}\)
Use the function \(\fn{conj}\) to describe self-conjugate partitions.
Solution.
A self-conjugate partition is precisely a partition \(\alpha\) such that \(\fn{conj}(\alpha)=\alpha\text{.}\) That is, a self-conjugate partition is a fixed point of the function \(\str{conj}\text{.}\)
Take some coins and arrange them into piles. You may have any number of piles and any number of coins in each pile. A pile may have as few as one coin in it. Order them largest to smallest (in nonincreasing order). This ordered arrangement of coins in piles is a state of the system.
From that starting state, collect the top coin off each pile and make one new pile out of those collected coins. Notice that any pile that had just a single coin was eliminated. Again, order the piles in nonincreasing order by size. You now have a new state.
Repeat this process on the new state — collect the top coin from each new pile, make one new pile out of those collected coins, and arrange the piles in order. Keep repeating the process. Although we can repeat this process forever, we stop if we get back to a state that we had visited before.
If you have five coins and you start with one pile of two coins and three piles of one coin each, then we denote that state \(2+1+1+1\text{.}\) Write down \(2+1+1+1\text{,}\) perform the process, and write down the resulting state. Then keep repeating the process, writing down each state each time, until you get to a state that you have visited before.
Start with six coins in two piles of three, which is denoted \(3+3\text{.}\) Perform the process, write down the resulting state, and then repeat until you get to a state that you have visited before.
Start with seven coins in piles of four, two, and one, which is denoted \(4+2+1\text{.}\) Perform the process, write down the resulting state, and then repeat until you get to a state that you have visited before.
A state is a fixed point of the system if when we apply one step of the process to that state we get that state immediately again. Give an example of a fixed point that you have found and find another example.
Thus far, we have been looking at one state at a time. For a given number of coins, \(n\text{,}\) we can visualize the entire system by drawing the directed state graph \(G_n\text{.}\) The vertices are all possible states and there is an arrow from each state to the state that follows from one step of the process. The state graph \(G_5\) is drawn in Figure 7.3.18. Draw the state graphs \(G_1\) (one coin) \(G_2\) (two coins), \(G_3\) (three coins), and \(G_4\) (four coins).
Figure7.3.18.The directed state graph \(G_5\) on five coins.
Now draw the state graph \(G_6\) (six coins). Be sure that you have all possible states. Hint: Start with the state \(1+1+1+1+1+1\) and perform the process until you get a repeat. Then, find a state that is not yet included in your graph. Repeat this process until all eleven possible states in your graph.
Let \(\mathbb{P}_n\) denote the partitions of the integer \(n\text{,}\) as defined in Definition 7.3.3. For a fixed positive integer \(n\text{,}\) the process introduced in Activity 7.3.C defines a function \(\beta:\mathbb{P}_n \to \mathbb{P}_n\text{.}\) When we repeat this process, we are iterating the function \(\beta\text{.}\) That is, we are calculating
where \(\beta^k\) is the \(k\)th iterate of the function \(\beta\text{,}\) as defined in Definition 6.4.20.
A state is cyclic if when we start at that state we eventually return to that state. That is, \(s\) is cyclic if \(\beta^k(s) = s\) for some positive integer \(k\text{.}\) For example, with five coins the cyclic states are \(3+2\text{,}\)\(2+2+1\text{,}\) and \(3+1+1\text{.}\)
where \(\beta^k(s) = s\text{.}\) The length of the cycle is \(k\text{.}\) For example, the three cyclic states in \(G_5\) form a 3-cycle. As another example, any fixed points are 1-cycles.
List all of the partitions of the set \(\{1,2,3,4\}\text{.}\) Hint: Organize your work by listing the partitions of the set corresponding to each partition of the integer four. For example, under \(2+2\) you would include the partitions \(\{1,2\} \cup \{3,4\}\text{,}\)\(\{1,3\} \cup \{2,4\}\text{,}\) and \(\{1,4\} \cup \{2,3\}\text{.}\)
Let \(\mathbb{P}_{10}\) be the set of all partitions of the integer 10. The function \(\fn{countparts}:\mathbb{P}_{10} \to \mathbb{N}\) is defined by \(\fn{countparts}(\alpha)\) is the the number of parts of \(\alpha\text{.}\)
Identify the domain and codomain of \(\fn{countparts}\text{.}\)
Let \(\mathbb{P}_{10}\) be the set of all partitions of the integer 10. The function \(\fn{evenparts}:\mathbb{P}_{10} \to \mathbb{N}\) is defined by \(\fn{evenparts}(\alpha)\) is the the number of parts of \(\alpha\) that are even numbers.
Identify the domain and codomain of \(\fn{evenparts}\text{.}\)
Identify the image of \(\fn{evenparts}\text{.}\) Hint: What is the largest number of even parts that a partition of 10 can have? Is \(\fn{evenparts}\) onto?
Let \(\mathbb{P}_{10}\) be the set of all partitions of the integer 10. The function \(\fn{oneparts}:\mathbb{P}_{10} \to \mathbb{N}\) is defined by \(\fn{oneparts}(\alpha)\) is the the number of parts of size one in \(\alpha\text{.}\)
Identify the domain and codomain of \(\fn{oneparts}\text{.}\)
Let \(\mathbb{P}_{k}\) be the set of all partitions of the integer \(k\text{.}\) The function \(f: \mathbb{P}_{10} \to \mathbb{P}_9\) is defined by \(f(\alpha)=\) the partition obtained from \(\alpha\) by subtracting one from \(\alpha\)’s smallest part (and ignoring any zeros.) Notice that this subtraction preserves the nonincreasing order so we do get a partition.
Is there always a self-conjugate partition of \(n\) when \(n>2\) is even? Justify your answer. Hint: can you find a pattern in your answers to Exercise 11?
Hint: The answer is yes. Make sure that you know how to build self-conjugate partitions when \(n\) is odd as in Activity 7.3.B(f). Then use the fact that an even is just one more than an odd.
Read the wikipedia entry for Partition Function (number theory). According to the article, what’s \(p(100)\text{?}\) Is there a closed-form expression (explicit formula) for \(p\text{?}\)
Start with some arrangement of ten coins into piles in nonincreasing order. Record that state (as a partition). Repeat the process, recording each state as you go, until you get to a state that you have visited before.
Now pick a new state with ten coins. Record that state (as a partition). Repeat the process, recording each state as you go, until you get to a state that you have visited before, which could be from 16.(a).
Hint: Your conjecture should be that for some special numbers of coins, like 10, that all states end in the same state. Some other special numbers of coins are 1, 3, and 6.
Prove your conjecture from Activity 7.3.C(e) about fixed points. Be sure to show that these states are fixed points and that any fixed point is one of these states.
(For readers who have completed Exercise 16, Exercise 17, Exercise 19, Exercise 21.) Conjecture which states are cyclic states for \(n\) coins. Hint: Draw the diagrams for the cyclic states you found earlier.
