FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Probability
boggled by counting problems
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Bill H
science forum beginner


Joined: 11 May 2006
Posts: 9

PostPosted: Wed May 31, 2006 3:21 pm    Post subject: boggled by counting problems Reply with 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)"

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?
Back to top
Michael Zedeler
science forum beginner


Joined: 29 Nov 2005
Posts: 17

PostPosted: Wed May 31, 2006 7:00 pm    Post subject: Re: boggled by counting problems Reply with quote

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.
Visit my home page at http://michael.zedeler.dk/
Back to top
Bill H
science forum beginner


Joined: 11 May 2006
Posts: 9

PostPosted: Wed May 31, 2006 9:11 pm    Post subject: Re: boggled by counting problems Reply with quote

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.
Back to top
Michael Zedeler
science forum beginner


Joined: 29 Nov 2005
Posts: 17

PostPosted: Thu Jun 01, 2006 1:30 pm    Post subject: Re: boggled by counting problems Reply with quote

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.
Visit my home page at http://michael.zedeler.dk/
Back to top
Bill H
science forum beginner


Joined: 11 May 2006
Posts: 9

PostPosted: Thu Jun 01, 2006 4:06 pm    Post subject: Re: boggled by counting problems Reply with quote

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.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Mon Aug 21, 2017 8:20 am | All times are GMT
Forum index » Science and Technology » Math » Probability
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0282s ][ Queries: 16 (0.0096s) ][ GZIP on - Debug on ]