3.4: Distribution Problems (Exercises)
- Page ID
- 6108
\( \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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)1. Answer each of the following questions with \(n^{k}, k^{n}, n!, k!, \binom{n}{k}, \binom{k}{n}, n^{\underline{k}}, k^{\underline{n}}, n^{\bar{k}}, k^{\bar{n}}, \binom{n+k-1}{k}, \binom{n+k-1}{n}, \binom{n-1}{k-1}, \binom{k-1}{n-1}\), or “none of the above.”
- In how many ways may we pass out \(k\) identical pieces of candy to \(n\) children?
- In how many ways may we pass out \(k\) distinct pieces of candy to \(n\) children?
- In how many ways may we pass out \(k\) identical pieces of candy to \(n\) children so that each gets at most one? (Assume \(k \leq n\).)
- In how many ways may we pass out \(k\) distinct pieces of candy to \(n\) children so that each gets at most one? (Assume \(k \leq n\).)
- In how many ways may we pass out \(k\) distinct pieces of candy to \(n\) children so that each gets at least one? (Assume \(k \geq n\).)
- In how many ways may we pass out \(k\) identical pieces of candy to \(n\) children so that each gets at least one? (Assume \(k \geq n\).)
2. The neighborhood betterment committee has been given \(r\) trees to distribute to \(s\) families living along one side of a street. Unless otherwise specified, it doesn’t matter where a family plants the trees it gets.
- In how many ways can they distribute all of them if the trees are distinct, there are more families than trees, and each family can get at most one?
- In how many ways can they distribute all of them if the trees are distinct and any family can get any number?
- In how many ways can they distribute all the trees if the trees are identical, there are no more trees than families, and any family receives at most one?
- In how many ways can they distribute them if the trees are distinct, there are more trees than families, and each family receives at most one (so there could be some leftover trees)?
- In how many ways can they distribute all the trees if they are identical and anyone may receive any number of trees?
- In how many ways can all the trees be distributed and planted if the trees are distinct, any family can get any number, and a family must plant its trees in an evenly spaced row along the road?
- Answer the question in Part 2f assuming that every family must get a tree.
- Answer the question in Part 2e assuming that each family must get at least one tree.
3. In how many ways can \(n\) identical chemistry books, \(r\) identical mathematics books, \(s\) identical physics books, and \(t\) identical astronomy books be arranged on three bookshelves? (Assume there is no limit on the number of books per shelf.)
\(\rightarrow\) 4. One formula for the Lah numbers is
\[L(k,n) = \binom{k}{n}(k-1)^{\underline{k-n}}\]
Find a proof that explains this product.
5. What is the number of partitions of \(n\) into two parts?
6. What is the number of partitions of \(k\) into \(k − 2\) parts?
7. Show that the number of partitions of \(k\) into \(n\) parts of size at most \(m\) equals the number of partitions of \(mn − k\) into no more than \(n\) parts of size at most \(m − 1\).
8. Show that the number of partitions of \(k\) into parts of size at most \(m\) is equal to the number of partitions of \(k + m\) into \(m\) parts.
9. You can say something pretty specific about self-conjugate partitions of \(k\) into distinct parts. Figure out what it is and prove it. With that, you should be able to find a relationship between these partitions and partitions whose parts are consecutive integers, starting with \(1\). What is that relationship?
10. What is \(s(k, 1)\)?
11. Show that the Stirling numbers of the second kind satisfy the recurrence
\[S(k,n) = \sum^{k}_{i=1} S(k-i,n-1)\binom{k-1}{i-1}\].
\(\rightarrow\) 12. Let \(c(k, n)\) be the number of ways for \(k\) children to hold hands to form \(n\) circles, where one child clasping his or her hands together and holding them out to form a circle is considered a circle. (Having Mary hold Sam’s right hand is different from having Mary hold Sam’s left hand.) Find a recurrence for \(c(k, n)\). Is the family of numbers \(c(k, n)\) related to any of the other families of numbers we have studied? If so, how?
\(\rightarrow\) 13. How many labeled trees on \(n\) vertices have exactly four vertices of degree \(1\)?
\(\rightarrow\) 14. The degree sequence of a graph is a list of the degrees of the vertices in non-increasing order. For example, the degree sequence of the first graph in Figure 2.3.3 is \((4, 3, 2, 2, 1)\). For a graph with vertices labeled \(1\) through \(n\), the ordered degree sequence of the graph is the sequence \(d_{1}, d_{2}, . . . d_{n}\) in which \(d_{i}\) is the degree of vertex \(i\). For example, the ordered degree sequence of the first graph in Figure 2.3.1 is \((1, 2, 3, 3, 1, 1, 2, 1)\).
- How many labeled trees are there on \(n\) vertices with ordered degree sequence \(d_{1}, d_{2}, . . . ,d_{n}\)?
- How many labeled trees are there on \(n\) vertices with the degree sequence in which the degree \(d\) appears \(i_{d}\) times?