Solutions for AEP 6

--- tags: mth225 --- # Solutions for AEP 6 ## Problem 1 >Suppose we have an ordered array of ten memory cells in a computer, labelled $c_1, c_2, \dots, c_{10}$; and suppose we have a list of seven data items labelled $d_1, d_2, \dots, d_7$ to be put into the cells. Assume that the data items are all different, and each will be stored only once. In how many ways can all seven data items be assigned to the ten memory cells, assuming each cell can hold only one item? Use this as a visual for the memory cells in each part: | $c_1$ | $c_2$ | $c_3$ | $c_4$ | $c_5$ | $c_6$ | $c_7$ | $c_8$ | $c_9$ | $c_{10}$ | | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | -------- | | | | | | | | | | | | **Solution:** Think about storing each data item one at a time. The first one, $d_1$, can be put in any of the 10 cells. The second one $d_2$ can be put in any of the *remaining* 9 cells. Likewise there are 8 choices for where to put $d_8$, 7 choices for $d_7$, etc. We are making a sequence of choices, so we multiply the number of outcomes of each choice together to get $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 604800$ possible choices. (This is the same as $P(10,7)$.) ## Problem 2 >Now assume that each memory cell can hold any number of the data items. That is, suppose we have seven data items to be stored and ten cells in which to store them, where each of the cells can store any number of the items. Assume that the order of items *within* each cell is not significant. How many ways are there of assigning the seven data items to the ten memory cells? **Solution:** Again think about storing each data item one at a time. This time there are no restrictions on where data items can be stored, so there are 10 options for $d_1$, 10 options for $d_2$, etc. So the number of assignments is $10^7 = 10000000$. ## Problem 3 >Suppose we again have of ten memory cells $c_1, c_2, \dots, c_{10}$ and seven data items labelled $d_1, d_2, \dots, d_7$ to be stored in the cells. But now suppose that we want the data items to be stored in *ascending order* in the cells. For example if item $d_3$ is stored in cell $c_8$, then item $d_4$ must be stored either in $c_9$ or $c_{10}$. How many different ways can the seven data items be assigned to the ten cells subject to this constraint? **Solution:** Once again, think about storing each data item one at a time but this time, keep track of where each item is stored and the order in which the storage takes place, using a 7-element ordered list. For example if we put $d_1$ in $c_1$, $d_2$ and $d_3$ in $c_2$, $d_4$ in $c_3$, $d_5$ in $c_6$, $d_7$ in $c_9$, and $d_7$ in $c_{10}$ (which is a valid arrangement since the data items are stored in increasing order), this would give the list $[c_1, c_2, c_2, c_3, c_6, c_9, c_{10}]$. In more general terms, if $L$ is the list, then $L[i]$ is the cell in which $d_i$ is stored (with index starting at 1). Constructing the list in this way ensures that we preserve the increasing ordering of the data items. The question now becomes, how many lists of this form can be made? Map this onto a *stars and bars* situation as follows. + For each instance of a cell in the list, assign a star. + For each switch between cells, assign a bar. So the list $[c_1, c_2, c_2, c_3, c_6, c_9, c_{10}]$ for example would correspond to the stars-and-bars diagram: $$\star | \star \star | \star | | | \star | | | \star | \star$$ In this way, *every possible assignment of data items to cells corresponds to a diagram, and vice versa*. So we need only use our class techniques for counting these stars-and-bars diagrams. In each one, there are seven stars (one for each data item being assigned) and nine bars (one for each space in between the memory cells), so there are 16 total objects and 9 of them are bars. This means that the total count is: $$\binom{16}{9} = 11440.$$ ## How this was graded + An E for correct work and explanations on all three problems + An M for correct work and explanations on two problems and decent start on the third + An R for a good-faith effort on each part but not meeting the requirements for an M + An N otherwise.