Results 1 to 2 of 2

Math Help - Combinatorics

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    21

    Combinatorics

    Suppose that 1 is less than or equal to k which is less than n. Prove that the part k occurs a total of (n-k+3)2^(n-k-2) times among all the 2^(n-1) compositions of n.

    The teacher gave a hint to use the balls and walls technique, fix a part of size 2 and then count the number of ways to complete the composition. Then use this to prove the general k case.

    I'm confused as how to get the number of compositions from the balls and walls technique and then how to go on for the general case. Any help would be appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by bethh View Post
    Suppose that 1 is less than or equal to k which is less than n. Prove that the part k occurs a total of (n-k+3)2^(n-k-2) times among all the 2^(n-1) compositions of n.

    The teacher gave a hint to use the balls and walls technique, fix a part of size 2 and then count the number of ways to complete the composition. Then use this to prove the general k case.

    I'm confused as how to get the number of compositions from the balls and walls technique and then how to go on for the general case. Any help would be appreciated. Thanks.
    I see balls and walls is another name for stars and bars.

    I think the fact that we're counting "how many times k appears" rather than "in how many compositions k appears" helps us out, because it frees us from worrying about duplicate counting.

    Consider n=5, k=2.

    *|*|*|*|*

    We want to fix **. There are 4 ways to do this

    **|*|*|*
    *|**|*|*
    *|*|**|*
    *|*|*|**

    In red are marked the bars that must be in place in order for the part of size 2 to be intact. The bars in black can be either on or off.

    So it can be seen that the count is 2^2 + 2 + 2 + 2^2 = 12, which is correct and matches with the formula given.

    I haven't tried to generalize, but if your professor says that it will work out, it probably will. Try it and see what happens.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 03:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 09:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 06:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 11:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 07:03 AM

Search Tags


/mathhelpforum @mathhelpforum