Combinatorial modelling
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Combinatorial modelling is the process which lets us identify a suitable mathematical model to reformulate a problem. These combinatorial models will provide, through the combinatorics theory, the operations needed to solve the problem.
Combinatorial modelling is the process which lets us identify a suitable mathematical model to reformulate a problem. These combinatorial models will provide, through the combinatorics theory, the operations needed to solve the problem. What we need to do is calculate the number of all possible pairs of party guests, which means, a sample of 2 people out of the 50 guests, so k=2 and n=50 . A pair will be the same no matter the order of the two people. A handshake must be carried out by two different people (no repetition).
So, it is required to select an unordered sample of 2 elements out of a set of 50 elements, in which repetition is not allowed. That is all we need to know to choose the right operation, and the result is: C_{50,2}=\frac{50!}{2!\cdot(50-2)!}=1225 2.- Unfortunately, you can't remember the code for your four-digit lock. You only know that you didn't use any digit more than once. How many different ways do you have to try? We need to choose a sample of 4 digits out of the set of 10 digits (base 10), so k=4 and n=10 .
The digits must be ordered in a certain way to get the correct number, so we want to select an ordered sample. As the statement says, no digit was chosen more than once, so our sample will not have repeated digits. So, it is required to select an ordered sample of 4 elements out of a set of 10 elements, in which repetition is not allowed. That is all we need to know to choose the right operation, and the result is: V_{10,4}=\frac{10!}{(10-4)!}=5040 3.- A boy wants to buy 20 invitation cards to give to their friends for his birthday party.
There are 3 types of cards in the store, and he likes them all. In how many ways can he buy the 20 cards? It is required to choose a sample of 20 invitation cards out of the set of 3 types of cards, so k=20 and n=3 . The order in which you choose the different types of invitations does not matter. As a type of card must be selected more than once, there will be repetitions in our invitation cards. So, we want to select a non ordered sample of 20 elements ( k=20 ) out of a set of 3 elements ( n=3 ), in which repetition is allowed.
That is all we need to know to choose the right operation, and the result is: CR_{3,20}=C_{22,20}=\frac{22!}{20!\cdot(22-20)!}=231 Bijective distribution: every box must exactly 1 object ( k=n ) Distribution with no restrictions The following table shows the operations that the model provides to get the number of different ways of distributing the objects for each of the distributions: S(k,n)=\left\{ {k \atop n} \right\}: Stirling numbers of the second kind P(k,n): Number of partitions of the integer k into n parts L(k,n): Lah numbers (Stirling numbers of the third kind) Let's consider the 3 studentships are objects that have to be distributed into 7 boxes, which are the students.
As the objects are identical studentships, they are indistinguishable. The boxes are distinguishable, as they are different students. Every studentship must be given to a different student, so every box must have at most 1 object. Furthermore, the order in which the objects are placed in a boxes does not matter, because there cannot be more than one on each box. So, it is a non ordered injective distribution of 3 indistinguishable objects ( k=3 ) into 7 distinguishable boxes ( n=7 ).
That is all we need to know to choose the right operation, and the result is: C_{7,3}=\frac{7!}{3!\cdot(7-3)!}=35 2.- A group of 8 friends rent a 5-room cottage to spend their holidays. If the rooms are identical and no one can be empty, in how many ways can they be distributed in the cottage? Let's consider the friends are objects that have to be distributed into 5 boxes, which are the rooms. As the objects are different people, they are distinguishable. The boxes are indistinguishable, as they are identical rooms.
We can consider it as a non ordered distribution, because the ordered in which everyone is placed in the rooms does not matter. No room can be empty, so every box must have at least 1 object. So, it is a non ordered surjective distribution of 8 distinguishable objects ( k=8 ) into 5 indistinguishable boxes ( n=5 ).
That is all we need to know to choose the right operation, and the result is: S(8,5)= \left\{{8 \atop 5}\right\} =\frac {1}{5!}\sum _{i=0}^5(-1)^i \binom {5}{i}(5-i)^8 = 1050 3.- 12 people are done shopping in a supermarket where 4 cashiers are working at the moment. In how many different ways can they be distributed into the checkouts? Let's consider the people are objects that have to be distributed into boxes, which are the check-outs. As the people and the checkouts are different, the objects and the boxes are distinguishable.
The order in which the objects are placed in the boxes matter, because they are people getting into queues. The statement does not mention any restriction. So, it is an ordered distribution with no restrictions of 12 distinguishable objects ( k=12 ) into 4 distinguishable boxes ( n=4 ). That is all we need to know to choose the right operation, and the result is: 12!\cdot CR_{4,12}=12!\cdot C_{15,12}=12!\cdot\frac{15!}{12!\cdot(15-12)!}=217945728000 We need to divide the set of 8 topics into 3 subsets.
These subsets will be the topics that each of the students will work on. The elements in the set (topics) are distinguishable. The partitions must be ordered because each one will correspond to a different student, but the topics inside every subset do not have to be ordered because each student can decide which order to follow when working on the thesis. The statement does not mention any restriction of the subsets. So, it is required to divide a set of 8 elements ( k=8 ) into 3 ordered subsets ( n=3 ) of non ordered elements.
That is all we need to know to choose the right operation, and the result is: VR_{3,8}=3^8=6561
See also
Twelvefold way
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370033569 under CC BY-SA 4.0; modifications have been made.