# Some fundamental question in combinatorics

• MHB
• CStudent
In summary, the speaker did not understand why the formula works and what it is actually calculating.
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!

CStudent said:
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.

CStudent said:
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.

CStudent said:
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.

Evgeny.Makarov said:
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:

$\binom{9}{4,&space;3,&space;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?

Last edited:
CStudent said:
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.

Evgeny.Makarov said:
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?

CStudent said:
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.

Evgeny.Makarov said:
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!

## 1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting, arranging, and selecting objects or elements in a finite or discrete manner. It involves studying patterns and structures in finite sets and using various counting techniques to solve problems.

## 2. What are some fundamental concepts in combinatorics?

Some fundamental concepts in combinatorics include permutations, combinations, and the binomial theorem. Permutations refer to the arrangements of objects or elements in a specific order, while combinations refer to the selection of objects or elements without considering their order. The binomial theorem is a formula used to expand binomials, which are expressions with two terms.

## 3. How is combinatorics used in real-life applications?

Combinatorics has many practical applications, such as in computer science, finance, and statistics. It is used in data compression algorithms, cryptography, and analyzing stock market trends. It also plays a crucial role in probability and statistics, which are essential in various fields such as medicine and social sciences.

## 4. What are some common problems in combinatorics?

Some common problems in combinatorics include finding the number of possible combinations or permutations, solving counting problems with restrictions or conditions, and determining the probability of certain outcomes. These problems often involve applying different counting techniques, such as the multiplication principle, combinations formula, and inclusion-exclusion principle.

## 5. How can one improve their skills in combinatorics?

To improve skills in combinatorics, one can practice solving various problems and familiarize themselves with different counting techniques and formulas. It is also helpful to study and understand mathematical proofs related to combinatorics and to seek guidance from experienced mathematicians or attend workshops and seminars on the subject.

Replies
3
Views
2K
Replies
3
Views
2K
Replies
6
Views
2K
Replies
25
Views
5K
Replies
7
Views
1K
Replies
1
Views
1K
Replies
14
Views
1K
Replies
5
Views
2K
Replies
1
Views
914
Replies
2
Views
848