Discrete math library homework

Question

I am working on a homework question and I am not sure if I am going about the correct way of getting to the correct answer. I feel as this is a trick question. Here is the question:

In order to keep track of circulation numbers, the library asks you to note on a form, when you leave the library, which combinations of $15$ subject areas and of $8$ types of material (books, current journals, databases, bound journals, videotapes, microfilm, microfiche, DVDs) you used. How many possible ways are there to fill in a line on the form?

I was thinking of multiplying $15 \cdot 8 = 120$. But for some reason that did not seem correct. I was also thinking of doing $15^8$. But that number seemed too large.

Answer 1

As I said in a comment, the problem statement is a tad bit unclear for my taste. I'll assume, however, that a typical way to fill out the form might be something like "English, History, Math; book, database, microfiche, DVD." That is, you specify which subjects you came for and the types of materials you used, but without going into detail as to which type of material went with which subject. In that case the number of ways to fill out the form is either $(2^{15}-1)(2^8-1)+1$ or just $(2^{15}-1)(2^8-1)$, depending one whether you do or don't include forms for people who did nothing while at the library.

Answer 2

For each area you have either 1,2,3,...,8 number of materials: $$ \binom{8}{1} + \binom{8}{2} + ... + \binom{8}{8} = 2^8 - 1 $$ You can choose 1,2,3,...,15 subjects (applying same reasoning) : $ 2^{15} - 1$

When choosing a number of subjcets you always have the same amount of ways of choosing materials so:

$$ \therefore (2^{15}-1)(2^8-1) $$

Answer 3

As already correctly stated in the comments and in the preceding answer, this problem has not an univocal interpretation. However, maybe some considerations could be helpful to indicate the probable interpretation that who conceived the problem had in mind.

First, after some search, I found that this question is reported in the book "Discrete Mathematics with Ducks". In particular, the problem is cited in the first section of the book, entitled "Counting and proofs" , which deals with very basic preliminaries of mathematics. This might suggest that the solution is basic as well.

Second, the problem in the book has two additional parts. In the first of these, it is stated: "(Still about the library) Of course, not every combination is realistically possible, as the library does not hold materials in every type for every discipline. If the library has six types of material for each discipline, how many possible ways are there to fill in a line on the form?". In the second of these it is stated: " (And more about the library) More realistically, some disciplines use materials in more differing forms than others. Let's look at just a few disciplines. The Dance holdings are in videotape, DVD, current journals, bound journals, and books. The Math holdings are in books, current journals, databases, bound journals, videotapes, and microfilm. The Computer Science holdings are in books, databases, and DVDs. Ancient Studies holdings are just bound journals, videotapes, microfilm, and microfiche. How many possible ways are there to fill in a line?". Both these additional parts clearly refer to the simple combination between material and discipline. This seems to exclude interpretations where the two variables are considered "isolated", i.e. without considering which type of material is coupled with which discipline.

Lastly, this first section of the book cites several times the "product principle", explained as follows: "The number of elements in the Cartesian product of a finite number of finite sets $A×B×...×N$ is the product of their sizes $|A| \cdot |B| \cdot... \cdot |N|$". This is the classical rule of product, a fundamental principle of counting that is described in the book together with other basic counting principles (e.g. the rule of sum, the inclusion-exclusion principle, and the pigeonhole principle), and that hinges on the simple multiplication between two sizes. Accordingly, many other problems in the same section of the book that contains the OP are based on a single multiplication. For instance, few words before the OP, the book reports this other problem: " The Supreme Bruno is any patty-with-a-vegetable burger plus a condiment (choose from Worcestershire sauce, wasabi sauce, or mustard); you can also have cheese, or not. How many Supreme Brunos could be ordered?".

With these considerations in mind, it seems reasonable to hypothesize that the question described in the OP was created to have a very basic solution corresponding to the simplest interpretation, i.e. $15 \cdot 8 =120$ combinations.

Answer 4

Subject areas and types of material are in principle independent of each other, so the total number of possibilities is the product of the number of possibilities for filling out the first part of the form, times the possibilities for filling out the second part.

So if you must always choose exactly one subject area and exactly one type, the answer is indeed $15\cdot 8 = 120$. But what if that's not true? Maybe for a book with a DVD in the back you must check two types, for example. And maybe a book can belong to multiple subject areas. In that case, you have to calculate in how many ways the "subject area" section can be completed, and in how many ways the type section can be completed, and multiply the two numbers.

If the rule is that you must choose one or more subject areas, there will be $2^{15} - 1$ ways to complete this section: Every subject area can either be chosen or not, giving $2^{15}$ possibilities; but we exclude the case where nothing was selected.