Some fundamental question in combinatorics

[CStudent]

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!

 

[Evgeny.Makarov]

1. I don't actually understand how to integrate between combinatorics and function

It's hard to answer this. Your statement is similar to: "I don't understand operations on numbers". In contrast, a good question for a forum is: "When we perform long division of 123 by 14, why is the second digit of the result 7?"

Please give an example of a problem that involves both combinatorics and functions and describe what exactly you don't understand about it.

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?

Indeed, it shouldn't be clear why this formula is correct until you say precisely what "sorts of possibilities" are involved.

This formula gives the number of ordered sequences of length $k$ whose elements come from a set of cardinality $n$. We can put any of $n$ elements in the first place, any of the remaining $n-1$ elements in the second place and so on. The numbers $n, n-1, \ldots,n-(k-1)$ have to be multiplied to get the total number of sequences according to the rule of product.

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.

Please write the part of the proof that you don't understand. There is a good Wikipedia article about the binomial theorem. If you have questions, feel free to point to a specific place that is not clear.

The only legitimate question in mathematics is when one presents a precise statement and asks, "Why is it true?" For example, you may point at a particular equality in long chain and say, "I understand the transitions before and after that, but I don't understand according to which law the author rewrote the left-hand side here". It is mostly the responsibility of the question author to come up with all definitions so that the statement in question is complete and precise.

To be honest, sometimes it is legitimate to ask, "Why is this concept interesting?" or "Are there any other ways to solve this?". But I still would recommend rewriting your questions to give more context and to make them more precise.

 

[CStudent]

It's hard to answer this. Your statement is similar to: "I don't understand operations on numbers". In contrast, a good question for a forum is: "When we perform long division of 123 by 14, why is the second digit of the result 7?"

Please give an example of a problem that involves both combinatorics and functions and describe what exactly you don't understand about it.

Indeed, it shouldn't be clear why this formula is correct until you say precisely what "sorts of possibilities" are involved.

This formula gives the number of ordered sequences of length $k$ whose elements come from a set of cardinality $n$. We can put any of $n$ elements in the first place, any of the remaining $n-1$ elements in the second place and so on. The numbers $n, n-1, \ldots,n-(k-1)$ have to be multiplied to get the total number of sequences according to the rule of product.

Please write the part of the proof that you don't understand. There is a good Wikipedia article about the binomial theorem. If you have questions, feel free to point to a specific place that is not clear.

The only legitimate question in mathematics is when one presents a precise statement and asks, "Why is it true?" For example, you may point at a particular equality in long chain and say, "I understand the transitions before and after that, but I don't understand according to which law the author rewrote the left-hand side here". It is mostly the responsibility of the question author to come up with all definitions so that the statement in question is complete and precise.

To be honest, sometimes it is legitimate to ask, "Why is this concept interesting?" or "Are there any other ways to solve this?". But I still would recommend rewriting your questions to give more context and to make them more precise.

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:

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?

 

[Evgeny.Makarov]

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:
\(\displaystyle \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?

Let's start with the definition. The coefficient \(\displaystyle \binom{n}{n_1,\ldots,n_k}\) where \(\displaystyle n_1+\dots+n_k=n\) can be defined as \(\displaystyle \frac{n!}{n_1!\dots n_k!}\). An equivalent definition is the number of ordered partitions of a set $A$ with $n$ elements into $k$ (disjoint) sets $A_1,\ldots,A_k$ with $n_1,\ldots,n_k$ elements, respectively. Note that $A_i$'s are distinct and possibly empty, and their order matters. The number of partitions can be computed in this way: $A_1$ can be chosen in \(\displaystyle \binom{n}{n_1}\) ways; after that, $A_2$ can be chosen in \(\displaystyle \binom{n-n_1}{n_2}\) ways; then $A_3$ can be chosen in \(\displaystyle \binom{n-n_1-n_2}{n_3}\) ways and so on. To find the number of partitions these numbers have to be multiplied. Then many factorials cancel and one is left with \(\displaystyle \binom{n}{n_1,\ldots,n_k}\).

Now suppose there is a word of length $n$ consisting of $k$ different letters. The first letter is used $n_1$ times, the second letter is used $n_2$ times and so on; thus, $n_1+\dots+n_k=n$. Let $A$ be the set of places: $A=\{1,\ldots,n\}$. Let $A_i$ be the set of places occupied by the $i$th letter. Then $A_1,\ldots,A_k$ form an ordered partition of $A$. Now this is an important fact: there is a one-to-one correspondence between such partitions and words. Therefore the number of words is also computed using multinomial coefficients.

 

[CStudent]

Let's start with the definition. The coefficient \(\displaystyle \binom{n}{n_1,\ldots,n_k}\) where \(\displaystyle n_1+\dots+n_k=n\) can be defined as \(\displaystyle \frac{n!}{n_1!\dots n_k!}\). An equivalent definition is the number of ordered partitions of a set $A$ with $n$ elements into $k$ (disjoint) sets $A_1,\ldots,A_k$ with $n_1,\ldots,n_k$ elements, respectively. Note that $A_i$'s are distinct and possibly empty, and their order matters. The number of partitions can be computed in this way: $A_1$ can be chosen in \(\displaystyle \binom{n}{n_1}\) ways; after that, $A_2$ can be chosen in \(\displaystyle \binom{n-n_1}{n_2}\) ways; then $A_3$ can be chosen in \(\displaystyle \binom{n-n_1-n_2}{n_3}\) ways and so on. To find the number of partitions these numbers have to be multiplied. Then many factorials cancel and one is left with \(\displaystyle \binom{n}{n_1,\ldots,n_k}\).

Now suppose there is a word of length $n$ consisting of $k$ different letters. The first letter is used $n_1$ times, the second letter is used $n_2$ times and so on; thus, $n_1+\dots+n_k=n$. Let $A$ be the set of places: $A=\{1,\ldots,n\}$. Let $A_i$ be the set of places occupied by the $i$th letter. Then $A_1,\ldots,A_k$ form an ordered partition of $A$. Now this is an important fact: there is a one-to-one correspondence between such partitions and words. Therefore the number of words is also computed using multinomial coefficients.

Thank you!
Why is there one-to-one correspondence between such partitions and words?

 

[Evgeny.Makarov]

Why is there one-to-one correspondence between such partitions and words?

For example, consider the word "mathematics". Its length is 11. Its letters, listed in alphabetical order, occupy the following positions:

a: {2, 7}
c: {10}
e: {5}
h: {4}
i: {9}
m: {1, 6}
s: {11}
t: {3, 8}

The sequence P = ({2, 7}, {10}, {5}, {4}, {9}, {1, 6}, {11}, {3, 8}) is an ordered partition of the set {1, ..., 11}. We constructed it from the original word and the alphabetical list of its letters "acehimst". Conversely, a partition together with the list of unique letters gives rise to a word. For example, the 6th element of P is {1, 6}, and the 6th element of "acehimst" is "m". Therefore, "m" occupies 1st and 6th places in the word that is being reconstructed. That is, you are given all letters of the word: "acehimst", and for each letter you are given where this letter is located in the final word. So partitions and words can be uniquely reconstructed from each other provided the list of unique letters is given.

 

[CStudent]

For example, consider the word "mathematics". Its length is 11. Its letters, listed in alphabetical order, occupy the following positions:

a: {2, 7}
c: {10}
e: {5}
h: {4}
i: {9}
m: {1, 6}
s: {11}
t: {3, 8}

The sequence P = ({2, 7}, {10}, {5}, {4}, {9}, {1, 6}, {11}, {3, 8}) is an ordered partition of the set {1, ..., 11}. We constructed it from the original word and the alphabetical list of its letters "acehimst". Conversely, a partition together with the list of unique letters gives rise to a word. For example, the 6th element of P is {1, 6}, and the 6th element of "acehimst" is "m". Therefore, "m" occupies 1st and 6th places in the word that is being reconstructed. That is, you are given all letters of the word: "acehimst", and for each letter you are given where this letter is located in the final word. So partitions and words can be uniquely reconstructed from each other provided the list of unique letters is given.

Beautiful, thanks!