Results 1 to 5 of 5

Math Help - combinations of permutations?

  1. #1
    Member billym's Avatar
    Joined
    Feb 2008
    Posts
    183

    combinations of permutations?

    I have a string of length 14 made up of 0s, 1s, and 2s. I'm trying to find the number of strings with an odd number of 2s.

    So I want to sum the number of strings I can make for each odd value k between 1 and 14.

    I can't figure out if for each odd number of 2s, i should use P(12,k) or C(12,k) multiplied by 2^{12-k}.

    I think I should use C since I am just looking for the number of possible combinations of size k, i.e. the places where the 2's will be...

    (EDIT: I meant "arghh... are these combinations or permutations?)
    Last edited by billym; November 9th 2009 at 05:33 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,318
    Thanks
    1292
    Quote Originally Posted by billym View Post
    I have a string of length 14 made up of 0s, 1s, and 2s. I'm trying to find the number of strings with an odd number of 2s.

    So I want to sum the number of strings I can make for each odd value k between 1 and 14.

    I can't figure out if for each odd number of 2s, i should use P(12,k) or C(12,k) multiplied by 2^{12-k}.

    I think I should use C since I am just looking for the number of possible combinations of size k, i.e. the places where the 2's will be...
    Yes, these are "combinations" since you are treating all "2"s as the same.

    And, of course, the distinction between "0" and "1" is irrelevant. The number of ways you can have a string of 1 "2" and 13 "other" is \left(\begin{array}{c}14 \\ 1\end{array}\right)= 14. The number of ways you can have 3 "2"s and 11 "other" is \left(\begin{array}{c}14 \\ 3\end{array}\right) = \frac{14!}{3!11!}= \frac{14(13)(12)}{6}= 364, etc. The number of ways you can write and odd number of "2"s and fill out the remaining places with "other" is \sum_{n= 0}^6 \left(\begin{array}{c}14 \\ 2n+1\end{array}\right).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member billym's Avatar
    Joined
    Feb 2008
    Posts
    183
    I can see how the "other" spaces are irrelevant when you are finding the combinations of 2s, but aren't they relevant when you are calculating the number of... uh... "tales"?

    For example, since 21111111111111 and 20000000000000 are different strings, shouldn't this work:

    \sum_{n= 1,3,5,...}^{13} \left(\begin{array}{c}14 \\ n\end{array}\right)2^{14-n}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by billym View Post
    I can see how the "other" spaces are irrelevant when you are finding the combinations of 2s, but aren't they relevant when you are calculating the number of... uh... "tales"?

    For example, since 21111111111111 and 20000000000000 are different strings, shouldn't this work:

    \sum_{n= 1,3,5,...}^{13} \left(\begin{array}{c}14 \\ n\end{array}\right)2^{14-n}
    Yes that works.
    However, I think most of us would prefer this summation:
    \sum\limits_{n = 0}^6 {\binom{14}{2n+1} 2^{13 - 2n} }
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by billym View Post
    I have a string of length 14 made up of 0s, 1s, and 2s. I'm trying to find the number of strings with an odd number of 2s.

    So I want to sum the number of strings I can make for each odd value k between 1 and 14.

    I can't figure out if for each odd number of 2s, i should use P(12,k) or C(12,k) multiplied by 2^{12-k}.

    I think I should use C since I am just looking for the number of possible combinations of size k, i.e. the places where the 2's will be...

    (EDIT: I meant "arghh... are these combinations or permutations?)
    Here is an alternative approach via generating functions which is interesting because it gives the answer in a different form.

    Let a_r be the number of strings of length r composed of 0s, 1s, and 2s with an odd number of 2s, and let f be the exponential generating function (EGF) of a_r, i.e.
    f(x) = \sum_{r=0}^{\infty}\frac{1}{r!} a_r x^r.

    Then
    f(x) = (1 + x + \frac{1}{2!} x^2 + \frac{1}{3!} x^3 + \dots)^2 \; (x + \frac{1}{3!} x^3 + \frac{1}{5!} x^5 + \dots)
    = (e^x)^2 \; (1/2) \; (e^x - e^{-x})
    = (1/2) \; (e^{3x} - e^x)

    The answer to our problem is the coefficient of \frac{1}{14!} x^{14} in f(x), which is
    (1/2) \; (3^{14} - 1).

    More generally, the number of strings of length r is
    a_r = (1/2) \; (3^r - 1).

    The simplicity of this result suggests that there should be a simple combinatorial method of obtaining it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. DNA permutations and combinations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 8th 2010, 02:45 PM
  2. combinations and permutations
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: June 1st 2010, 02:49 PM
  3. I need help in Permutations and Combinations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 23rd 2010, 03:04 PM
  4. Permutations and Combinations
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 12th 2008, 10:07 AM
  5. Combinations and permutations
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 18th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum