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 nonA)"
I just sit and stare at the paper. Then start writing sequences of
7letter 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? 

Back to top 


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 nonA)"

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/ 

Back to top 


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 nonA)"
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 notA 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. 

Back to top 


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 nonA)"
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 notA 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
nonempty 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/ 

Back to top 


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 nonA)"
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 notA 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
nonempty 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. 

Back to top 


Google


Back to top 



The time now is Fri Sep 21, 2018 3:41 am  All times are GMT

