+ Reply to Thread
Results 1 to 5 of 5

Thread: Please explain logic behind a given solution

  1. #1
    Points: 177, Level: 3
    Level completed: 54%, Points required for next Level: 23

    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Please explain logic behind a given solution




    The following example is from Ryser's book Combinatorial Mathematics:

    "The number of 12-letter words that can be formed from 4 A's, 4 B's, 2 C's and 2 D's is 12!/(4!4!2!2!) = 207,900."

    I assume the reasoning behind this is that the 12 letters available can be permuted in 12! ways, but the 4 A's are indistinguishable as are the 4 B's, 2 C's and 2 D's, and that's why we divide by the product of 4!, 4!, 2!, and 2!.

    Right after that Ryser gives this example: "The number of 5-letter words that can be formed from the letters A, B, C in which A appears at most twice, B at most once, and C at most three times is

    5!/(2!0!3!) + 5!/(2!1!2!) + 5!/(1!1!3!) = 60."

    I don't understand Ryser's solution. I solve it following the logic of the first example given above. I reason:

    1) Since A appears at most twice, B at most once, and C at most three times, we're really asking: how many 5-letter words can we form from two A's, one B, and three C's = six letters?

    2) Thus we count the number of permutations of five letters taken from the six letters, which is 6!/( 65 )! = 6!

    3) But since the two A's are indistinguishable as are the three C's, we have to divide this by 2!3! to get

    6!/(2!3!) = 60.

    Can someone explain the reasoning that leads to Ryser's answer, which is a sum of three addends?

  2. #2
    TS Contributor
    Points: 22,410, Level: 93
    Level completed: 6%, Points required for next Level: 940

    Posts
    3,020
    Thanks
    12
    Thanked 565 Times in 537 Posts

    Re: Please explain logic behind a given solution

    1) Since A appears at most twice, B at most once, and C at most three times, we're really asking: how many 5-letter words can we form from two A's, one B, and three C's = six letters?
    Not really; The question is still asking for a 5 letter permutation. But now the question gives 1 extra letter of "freedom" so you have 3 possible scenarios

    \{(2,1,2), (2,0,3), (1,1,3)\}

    under the constraint a \leq 2, b \leq 1, c \leq 3, a + b + c = 5, a, b, c \in \mathbb{Z}^+\cup\{0\}

  3. #3
    Points: 177, Level: 3
    Level completed: 54%, Points required for next Level: 23

    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Re: Please explain logic behind a given solution

    Hi, BGM,

    The "not really" distinction you make is too subtle for my brain. Can you formulate a problem where Ryser's approach and mine would result in different answers?

    But thanks for the reply. I'd thought Ryser might be using multinomial coefficients, but couldn't quite work that out.

  4. #4
    Devorador de queso
    Points: 95,995, Level: 100
    Level completed: 0%, Points required for next Level: 0
    Awards:
    Posting AwardCommunity AwardDiscussion EnderFrequent Poster
    Dason's Avatar
    Location
    Tampa, FL
    Posts
    12,938
    Thanks
    307
    Thanked 2,630 Times in 2,246 Posts

    Re: Please explain logic behind a given solution

    Consider making a 2 letter word with at most 2 As, 1 B, and 1C.

    Your method says that we look at the number of permutations of 2 letters out of the 4: 4!/2! = 12 then divide by 2! since there are 2 As. So we get an answer of 6.

    But if you work through it the alternative way you get an answer of 7 and indeed these are the possibilities:
    "aa" "ac" "ca" "ab" "ba" "bc" "cb"
    I don't have emotions and sometimes that makes me very sad.

  5. The Following User Says Thank You to Dason For This Useful Post:

    X-man (12-10-2013)

  6. #5
    Points: 177, Level: 3
    Level completed: 54%, Points required for next Level: 23

    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Re: Please explain logic behind a given solution


    EXCELLENT, DASON! Your post will give me something to think about and work on over the eggnog!

+ Reply to Thread

           




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats