Search   Memberlist   Usergroups
 Page 1 of 1 [5 Posts]
Author Message
Bill H
science forum beginner

Joined: 11 May 2006
Posts: 9

Posted: Wed May 31, 2006 3:21 pm    Post subject: boggled by counting problems

I'm just blown away by the difficulty of seemingly "easy" counting
problems. The difficult part is that there is no analytic method to go
about solving them, eg. take a derivative using some combination of the
power and chain rules. One just has to "see" the answer, maybe more
like doing a difficult integral. How does one get good at solving
these problems? Eg.

"Count the number of 7 letter words with exactly three A's. Give an
example of how the following is incorrect due to double counting:
7*6*5*(25^4) (fill first slot with an A, second slot with A, third slot
with A, then fill remaining four slots with non-A)"

I just sit and stare at the paper. Then start writing sequences of
7-letter words, hoping I will "see" the answer. I can figure out there
are 26^7 total words. But to count the number with exactly 3A is
difficult. Is there some method I am missing?
Michael Zedeler
science forum beginner

Joined: 29 Nov 2005
Posts: 17

Posted: Wed May 31, 2006 7:00 pm    Post subject: Re: boggled by counting problems

Bill H wrote:
 Quote: I'm just blown away by the difficulty of seemingly "easy" counting problems. The difficult part is that there is no analytic method to go about solving them, eg. take a derivative using some combination of the power and chain rules. One just has to "see" the answer, maybe more like doing a difficult integral. How does one get good at solving these problems? Eg. "Count the number of 7 letter words with exactly three A's. Give an example of how the following is incorrect due to double counting: 7*6*5*(25^4) (fill first slot with an A, second slot with A, third slot with A, then fill remaining four slots with non-A)"

Using the numbers above, you have 7 choices for the first A, 6 for the
second and 5 for the last A.

Now look at the two different choices:

Position 1, 2, 3. (Yields "AAA****".)
Position 1, 3, 2. (Yields "AAA****".)

You need to take into account that the sequence of choices can be
permuted freely, still resulting in the same word.

Regards,

Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
I am less likely to answer usenet postings by anonymous authors.
Bill H
science forum beginner

Joined: 11 May 2006
Posts: 9

Posted: Wed May 31, 2006 9:11 pm    Post subject: Re: boggled by counting problems

Michael Zedeler wrote:
 Quote: Bill H wrote: I'm just blown away by the difficulty of seemingly "easy" counting problems. The difficult part is that there is no analytic method to go about solving them, eg. take a derivative using some combination of the power and chain rules. One just has to "see" the answer, maybe more like doing a difficult integral. How does one get good at solving these problems? Eg. "Count the number of 7 letter words with exactly three A's. Give an example of how the following is incorrect due to double counting: 7*6*5*(25^4) (fill first slot with an A, second slot with A, third slot with A, then fill remaining four slots with non-A)" Using the numbers above, you have 7 choices for the first A, 6 for the second and 5 for the last A. Now look at the two different choices: Position 1, 2, 3. (Yields "AAA****".) Position 1, 3, 2. (Yields "AAA****".) You need to take into account that the sequence of choices can be permuted freely, still resulting in the same word. Regards, Michael. -- Which is more dangerous? TV guided missiles or TV guided families? I am less likely to answer usenet postings by anonymous authors. Visit my home page at http://michael.zedeler.dk/

Very good. The correct answer is (7 choose 3)*25^4, the number of
combinations of 3A in 7 slots times the choices of not-A for the
remaining four slots.

But my question is how did you realize that? Is it a matter of
deciding whether order matters or not, whether sampling is with
replacement or not? Following Carol Ash, this is one of her problems,
first I should realize that by symmetry, it doesn't matter in what
position the 3A occur. There are still the same number of combinations
whether they are in the 1, 2, 3 slots or the 1, 2, 7 slots. Then I
guess the next realization is that order does not matter because the 3A
are not distinguished. So I should use combinations instead of
permutations. Still a hard problem in my book.
Michael Zedeler
science forum beginner

Joined: 29 Nov 2005
Posts: 17

Posted: Thu Jun 01, 2006 1:30 pm    Post subject: Re: boggled by counting problems

Bill H wrote:
 Quote: Michael Zedeler wrote: Bill H wrote: I'm just blown away by the difficulty of seemingly "easy" counting problems. The difficult part is that there is no analytic method to go about solving them, eg. take a derivative using some combination of the power and chain rules. One just has to "see" the answer, maybe more like doing a difficult integral. How does one get good at solving these problems? Eg. "Count the number of 7 letter words with exactly three A's. Give an example of how the following is incorrect due to double counting: 7*6*5*(25^4) (fill first slot with an A, second slot with A, third slot with A, then fill remaining four slots with non-A)" Using the numbers above, you have 7 choices for the first A, 6 for the second and 5 for the last A. Now look at the two different choices: Position 1, 2, 3. (Yields "AAA****".) Position 1, 3, 2. (Yields "AAA****".) You need to take into account that the sequence of choices can be permuted freely, still resulting in the same word. Very good. The correct answer is (7 choose 3)*25^4, the number of combinations of 3A in 7 slots times the choices of not-A for the remaining four slots. But my question is how did you realize that?

By considering the process of writing a string with 7 chars one char at
a time as I did above. But not by actually writing examples. If you
write up a descision tree, it is possible to see what actually happens
when you factor out the permutations.

Another way to go is to select three relative positions, r1, r2, r3
obeying the constraints r1>1, r2>1, r3>1 and r1+r2+r3 <= 7 and the
calculate the positions of the As as p1=r1, p2=r1+r2, p3=r1+r2+r3. As
far as I can see, this is equivalent of the number of ways to partition
an ordered set with seven elements into four ordered, contiguous
non-empty subsets (http://mathworld.wolfram.com/Partition.html).

Using the relative positions leads to the correspondance that two tuples
of relative positions (a1,a2,a3) and (b1,b2,b3) are different iff the
choices of positions of As are also different.

Regards,

Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
I am less likely to answer usenet postings by anonymous authors.
Bill H
science forum beginner

Joined: 11 May 2006
Posts: 9

Posted: Thu Jun 01, 2006 4:06 pm    Post subject: Re: boggled by counting problems

Michael Zedeler wrote:
 Quote: Bill H wrote: Michael Zedeler wrote: Bill H wrote: I'm just blown away by the difficulty of seemingly "easy" counting problems. The difficult part is that there is no analytic method to go about solving them, eg. take a derivative using some combination of the power and chain rules. One just has to "see" the answer, maybe more like doing a difficult integral. How does one get good at solving these problems? Eg. "Count the number of 7 letter words with exactly three A's. Give an example of how the following is incorrect due to double counting: 7*6*5*(25^4) (fill first slot with an A, second slot with A, third slot with A, then fill remaining four slots with non-A)" Using the numbers above, you have 7 choices for the first A, 6 for the second and 5 for the last A. Now look at the two different choices: Position 1, 2, 3. (Yields "AAA****".) Position 1, 3, 2. (Yields "AAA****".) You need to take into account that the sequence of choices can be permuted freely, still resulting in the same word. Very good. The correct answer is (7 choose 3)*25^4, the number of combinations of 3A in 7 slots times the choices of not-A for the remaining four slots. But my question is how did you realize that? By considering the process of writing a string with 7 chars one char at a time as I did above. But not by actually writing examples. If you write up a descision tree, it is possible to see what actually happens when you factor out the permutations. Another way to go is to select three relative positions, r1, r2, r3 obeying the constraints r1>1, r2>1, r3>1 and r1+r2+r3 <= 7 and the calculate the positions of the As as p1=r1, p2=r1+r2, p3=r1+r2+r3. As far as I can see, this is equivalent of the number of ways to partition an ordered set with seven elements into four ordered, contiguous non-empty subsets (http://mathworld.wolfram.com/Partition.html). Using the relative positions leads to the correspondance that two tuples of relative positions (a1,a2,a3) and (b1,b2,b3) are different iff the choices of positions of As are also different. Regards, Michael. -- Which is more dangerous? TV guided missiles or TV guided families? I am less likely to answer usenet postings by anonymous authors. Visit my home page at http://michael.zedeler.dk/

That would be nice if formulas from partition theory could be used to
solve such problems. I've never seen that before.

Back to the examples, I have an easier time with the deck of card
problems because I can visualize that 13 cards of the same suit are
actually 13 different cards, 4 face cards are different cards, etc.
With the word and string of letters problems, it is more difficult to
visualize because all the A's seem the same. I think it helps to
mentally number them according to the slots as in A_slot1, A_slot2,
A_slot3, etc.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [5 Posts]
 The time now is Thu Aug 16, 2018 5:04 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics approximating infinite linear programming problems diegotorquemada@yahoo.com Math 0 Mon Jul 17, 2006 10:29 am Three practice algebra qual problems Snis Pilbor Math 4 Sat Jul 15, 2006 11:12 pm -Word Problems- Alex111 Undergraduate 8 Wed Jul 12, 2006 9:05 pm Seeking Beautiful Single-Variable Calculus Problems Karl M. Bunday Math 8 Wed Jul 12, 2006 4:02 am Consecutive prime gap problems Tapio Math 9 Thu Jul 06, 2006 5:10 pm