Results 1 to 6 of 6
Like Tree4Thanks
  • 2 Post By Plato
  • 1 Post By Debsta
  • 1 Post By Plato

Thread: Some fundamental question in combinatorics

  1. #1
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Some fundamental question in combinatorics

    Hey.

    We started to study all this subject of combinatorics integrated with the subject of functions.

    1. I don't actually understand how to integrate between combinatorics and function, those functions which represent our possibilities and etc...
    And why at all we need to represent our combinatoric problem with an answer integrating functions?

    2. Secondly, we get this formula to calculate some sorts of possibilities:
    $\frac {n!} {(n-k)!}$
    It's not clear to me why is this really correct, what is posed behind it?

    3. For the Newton's binom - the lecturer has presented the proof for it but I don't understand it well, he also used the formula from above (2) to present the proof.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Some fundamental question in combinatorics

    Quote Originally Posted by CStudent View Post
    1. I don't actually understand how to integrate between combinatorics and function, those functions which represent our possibilities and etc... And why at all we need to represent our combinatoric problem with an answer integrating functions?

    2. Secondly, we get this formula to calculate some sorts of possibilities:
    $\frac {n!} {(n-k)!}$
    It's not clear to me why is this really correct, what is posed behind it?

    3. For the Newton's binom - the lecturer has presented the proof for it but I don't understand it well, he also used the formula from above (2) to present the proof.
    Your instructor expects that you know about permutations & combinations.
    If you study the two webpages I listed above then you will how those are related to counting problems.
    $_n\mathcal{P}_k=\dfrac{n!}{(n-k)!}$ permutations are about order in arrangements.

    $_n\mathcal{C}_k=\dbinom{n}{k}=\dfrac{n!}{(k!)(n-k)!}$ combinations are about content of arrangements.

    There are twenty-six letters in the English alphabet. How many ten letter "words" have all letters different.
    Well that is about order: $_{26}\mathcal{P}_{10}=\dfrac{26!}{(26-10)!}=19275223968000$

    How many ten letter subsets are there? Well that's about content" $_{26}\mathcal{C}_{10}=\dbinom{26}{10}=\dfrac{26!} {(10!)(16)!}=5311735$

    For the Newton's binom: $\displaystyle {(a + b)^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right){a^{n - k}}{b^k}} $

    Using above if $a=1~\&~b=1$ we get the really interesting result: $\displaystyle {2^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right)} $ which happens to be the number of subsets on any set containing $n$ elements.
    Thus there are a total of $2^{26}$ subsets of the English alphabet.
    Thanks from romsek and CStudent
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    1,074
    Thanks
    317

    Re: Some fundamental question in combinatorics

    Following on from the previous response and using a similar version to Plato's example:

    "How many four letter "words" have all letters different?"

    Another way of looking at it is by using the multiplication principle of counting to fill the four places:

    __ __ __ __

    Since there are 26 letters to choose from, the first space can be filled by any of the 26.

    So there will be 26x25x24x23 = 358800 permutations (where order is important eg ABCD is a different permutation to BACD, CBDA, etc)

    Now 26x25x24x23 = $\displaystyle \frac{26!}{(26-4)!} = \frac{26*25*24*23*22*21* …..*3*2*1}{22*21*…*3*2*1}$

    So you can see from this example that $\displaystyle _nP_k = \frac{n!}{(n-k)!}$

    Now for combinations of 4 letters (without repetition):

    Consider the 358 800 permutations.

    This figure counts ABCD, ACBD, CABD etc as different. With combinations we only want to count them once.

    Now, how many ways are there to arrange these 4 letters? 4 choices for the first space, 3 for the second, 2 for the third and 1 for the last.

    So the number of permutations of ABCD is 4x3x2x1 = 4! = 24

    So in the 358 800 permutations of 4 letters from 26, there are sets of 24 elements which should only be counted once (for combinations).

    So the number of combinations is $\displaystyle \frac{358800}{24} = 14950$

    Now this is $\displaystyle \frac{26!}{(26-4)!}$ divided by $\displaystyle 4!$.

    Same as the formula $\displaystyle _nC_k = \frac{n!}{(n-k)!k!}$


    Hope that helps you understand what's going on behind the scenes.
    Last edited by Debsta; Nov 18th 2018 at 03:48 PM.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Some fundamental question in combinatorics

    Quote Originally Posted by Plato View Post
    Your instructor expects that you know about permutations & combinations.
    If you study the two webpages I listed above then you will how those are related to counting problems.
    $_n\mathcal{P}_k=\dfrac{n!}{(n-k)!}$ permutations are about order in arrangements.

    $_n\mathcal{C}_k=\dbinom{n}{k}=\dfrac{n!}{(k!)(n-k)!}$ combinations are about content of arrangements.

    There are twenty-six letters in the English alphabet. How many ten letter "words" have all letters different.
    Well that is about order: $_{26}\mathcal{P}_{10}=\dfrac{26!}{(26-10)!}=19275223968000$

    How many ten letter subsets are there? Well that's about content" $_{26}\mathcal{C}_{10}=\dbinom{26}{10}=\dfrac{26!} {(10!)(16)!}=5311735$

    For the Newton's binom: $\displaystyle {(a + b)^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right){a^{n - k}}{b^k}} $

    Using above if $a=1~\&~b=1$ we get the really interesting result: $\displaystyle {2^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right)} $ which happens to be the number of subsets on any set containing $n$ elements.
    Thus there are a total of $2^{26}$ subsets of the English alphabet.
    Quote Originally Posted by Debsta View Post
    Following on from the previous response and using a similar version to Plato's example:

    "How many four letter "words" have all letters different?"

    Another way of looking at it is by using the multiplication principle of counting to fill the four places:

    __ __ __ __

    Since there are 26 letters to choose from, the first space can be filled by any of the 26.

    So there will be 26x25x24x23 = 358800 permutations (where order is important eg ABCD is a different permutation to BACD, CBDA, etc)

    Now 26x25x24x23 = $\displaystyle \frac{26!}{(26-4)!} = \frac{26*25*24*23*22*21* ..*3*2*1}{22*21**3*2*1}$

    So you can see from this example that $\displaystyle _nP_k = \frac{n!}{(n-k)!}$

    Now for combinations of 4 letters (without repetition):

    Consider the 358 800 permutations.

    This figure counts ABCD, ACBD, CABD etc as different. With combinations we only want to count them once.

    Now, how many ways are there to arrange these 4 letters? 4 choices for the first space, 3 for the second, 2 for the third and 1 for the last.

    So the number of permutations of ABCD is 4x3x2x1 = 4! = 24

    So in the 358 800 permutations of 4 letters from 26, there are sets of 24 elements which should only be counted once (for combinations).

    So the number of combinations is $\displaystyle \frac{358800}{24} = 14950$

    Now this is $\displaystyle \frac{26!}{(26-4)!}$ divided by $\displaystyle 4!$.

    Same as the formula $\displaystyle _nC_k = \frac{n!}{(n-k)!k!}$


    Hope that helps you understand what's going on behind the scenes.
    Thanks! I think I understand.

    Here is some concrete related example of misunderstanding of Multinomial Theorem:
    * How many 9-letter words can we compose from 3 letters of A, 2 letters of B and 4 letters of C?

    The answer is: $\binom{9}{4, 3, 2}$

    But I don't understand the logic of this calculating, why does it give us the required answer?
    What is behind the scenes of this multinomial formula?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,150
    Thanks
    3042
    Awards
    1

    Re: Some fundamental question in combinatorics

    Quote Originally Posted by CStudent View Post
    Here is some concrete related example of misunderstanding of Multinomial Theorem:
    * How many 9-letter words can we compose from 3 letters of A, 2 letters of B and 4 letters of C?
    The answer is: $\binom{9}{4, 3, 2}$
    But I don't understand the logic of this calculating, why does it give us the required answer?
    What is behind the scenes of this multinomial formula?
    The string $\mathbf{I}=AAABBCCCC$ is of length nine. However the number of ways to rearrange the is less than $9!$ due the the identical objects.
    This string $\mathbf{N}=A_1A_2A_3B_1B_2C_1C_2C_3C_4$ string contains no identical objects.
    The string $\mathbf{N}$ can be rearanged in $9!=362880$.
    Now the string $123$ can be rearanged in $3!=6$ ways.
    Thus if we remove the subscripts from the $A's$ we would have $6$ identical strings out of the $362880$.
    So divide $\dfrac{9!}{3!}=60480$, meaning that there are $60480$ to rearrange the string $AAAAB_1B_2C_1C_2C_3C_4$
    The further care for the $B's~\&~C's$ we divide: $\dfrac{9!}{3!\cdot 2!\cdot 4!}= 1260$

    Hope this clears away any confusion.
    Last edited by Plato; Nov 23rd 2018 at 11:29 AM.
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Some fundamental question in combinatorics

    Now it's clear, thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A fundamental question
    Posted in the Algebra Forum
    Replies: 12
    Last Post: Sep 29th 2014, 06:57 AM
  2. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 17th 2011, 04:56 PM
  3. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 28th 2009, 10:55 AM
  4. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 27th 2009, 09:53 PM
  5. combinatorics question -- please help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 31st 2009, 12:10 AM

/mathhelpforum @mathhelpforum