# Thread: Some fundamental question in combinatorics

1. ## 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!

2. ## Re: Some fundamental question in combinatorics

Originally Posted by CStudent
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.
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.

3. ## 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.

4. ## Re: Some fundamental question in combinatorics

Originally Posted by Plato
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.
Originally Posted by Debsta
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?

5. ## Re: Some fundamental question in combinatorics

Originally Posted by CStudent
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.

6. ## Re: Some fundamental question in combinatorics

Now it's clear, thanks!