- Anyone?
Contents
Counting
What I've found most confusing is knowing when to subtract repetitions of things, like in problem 44 on the homework, where we're asked to find how many strings there are with five consecutive 0s or five consecutive 1s. What's a good method for knowing or deciding how to count something like that?
Suggestion
The goal is to count each thing exactly once. Counting everything a certain number of times is almost as good, as you can just divide by that number.
If you know how many times individual elements were counted, that is the next best thing. You count how many elements of that type exist, and divide by that number. For example, you may have counted everything with 7 ones like 1111111000, 0111111100 and 1011111110 (and so on) 3 times (for 3 different sets of '11111'), and thus just count these separately and divide by 3.
What may be less work than this is just to devise a method that actually only counts exactly once instead of a different number of times. It may take a little more thought, but I think it's worth it in the end.
--Norlow 14:43, 10 September 2008 (UTC)
Counting
I also have the most trouble with counting. I know what I need to do, but I never know how to set the problem up. For example, problem 38 in section 5.1 asks: How many subsets of a set with 100 elements have more than one element? I know I need to take the total number of possible subsets of a set of 100 elements and subtract 100 (the total number of subsets that contain 1 element). The problem is finding the total number of possible subsets. Any suggestions?
I thought of #38 as a sum of combinations. I have $ \sum_{r=2}^{100} \left(\!\!\! \begin{array}{c} 100 \\ r \end{array} \!\!\!\right) $. This should count all possible subsets and exclude those containing only 1 element. I don't know how to simplify this, and I'm thinking there's a better way to do it. But it's a start.
Suggestion
The problem is finding the total number of possible subsets.
The total number of subsets is $ 2^n $. I don't remember the way Uli explained it in class (sorry about that), but the way I learned it before 375 was for each element, you can either put it in the set, or take it out. (2 choices) You can make this choice for every element, so 2*2*2*2... = $ 2^n $. (You multiply, since the choices for one element don't affect any other element)
Here's an example. If the elements are A, B, C, then you can either put A in, or leave A out. You can do the same with B and C. If you decide to leave A out, then you would have () (B) (C) (BC), depending on if you put B and C in or left them out. If you decided to put A in, you would have (A) (AB) (AC) (ABC by similar reasoning.
(Also don't forget to subtract out the 1 set of 0 elements at the end. The total sum goes from 0 to 100.)
