Solving Problems: Combinations and Permutations

In summary: The inc-exc principle, short for "inclusion-exclusion principle," is a counting technique used in combinatorics and probability. It states that the number of elements in the union of two or more sets is equal to the sum of the number of elements in each set, minus the number of elements in the intersection of the sets. This is because when we add up the elements in each set, we are counting the elements in the intersection multiple times, so we need to subtract it to avoid overcounting. In summary, the conversation discusses two different math problems: one involving selecting books from a bookshelf with m different books and n copies of each, and the other involving posting four letters in four envelopes so that no one receives the correct
  • #1
xt
10
0
I got this two problems, I can't figure them out...

A bookshelf contains m different books and n copies of each. How many different selections can be made from them?

and

In how many different ways can four letters be posted in four envelopes so that no one receives the correct letter?
 
Physics news on Phys.org
  • #2
xt said:
I got this two problems, I can't figure them out...

A bookshelf contains m different books and n copies of each. How many different selections can be made from them?

and

In how many different ways can four letters be posted in four envelopes so that no one receives the correct letter?
for the first question maybe it is:
m*(m+n)

but i only checked it for two specific cases.


edit:
after checking again i think the answer should be:
if m>n than S=m*(n+m)
if m<n than S=n*(n+m)
 
Last edited:
  • #3
If n=1, then the answer ought to be 2^m, so which examples did you check?
 
  • #4
1. For each book, you can take 0 of that book, or 1 of that book, ..., or n of that book. That is (n+1) possibilities. Since we have m books, the formula is (n+1)(n+1)(n+1)...(n+1) m times, or (n+1)^m.

One of the possibilities is that we select 0 of every book, so if "none of the books" is not a valid selection, then it is (n+1)^m - 1.
 
Last edited:
  • #5
matt grime said:
If n=1, then the answer ought to be 2^m, so which examples did you check?
i didnt try it for n=1.
the cases are:
m=2 n=3
and m=2 n=4
perhaps the flaw is i should have put in the second case m different than 2.
bougar :frown:
 
  • #6
matt grime said:
If n=1, then the answer ought to be 2^m, so which examples did you check?
i tried with n=1 and m=2 and here are the combinations i got:
(1,1)
(1,0)
(0,1)
if you put it in your formula it equals to 2^2=4 which is one combination more than in reality.

(unless you include (0,0) a selection which i haven't included in my two examples).
 
  • #7
The empty selection is always a selection.

pig's answer is correct assuming that the wording implies that picking anyone of the n copies is the same event as picking any of the other of the n copies.


The second question follows from the inc-exc principle.

Let V_n be the event that the nth person gets the right letter, U_n the even they don't

Then doing the event you want is the intersection of the V_i which is the complement of the union of the U_i, which can be found using inclusion exclusion
 
Last edited:
  • #8
matt grime said:
The empty selection is always a selection.
whats the logics behind this? why do you assume its a selection first then after the solution is done minus it off and say its not a valid selection?

matt grime said:
inc-exc principle.
what is that? where can i learn this stuff from? elementary probability?
 

1. What is the difference between combinations and permutations?

Combinations and permutations both involve selecting a set of elements from a larger group. However, combinations are unordered selections while permutations are ordered selections. For example, if we have the letters A, B, and C, a combination of 2 letters would be AB, AC, or BC, while a permutation of 2 letters would be AB, BA, AC, CA, BC, or CB.

2. How do I calculate the number of combinations or permutations?

To calculate the number of combinations, use the formula nCr = n! / (r! * (n-r)!), where n is the total number of elements and r is the number of elements being selected. For permutations, use the formula nPr = n! / (n-r)!, where n is the total number of elements and r is the number of elements being selected in a specific order.

3. Can combinations and permutations be used to solve real-world problems?

Yes, combinations and permutations can be used to solve a variety of real-world problems, such as calculating the number of possible outcomes in a game or determining the number of ways to arrange objects in a space.

4. What is the difference between with and without replacement in combinations and permutations?

In combinations and permutations, "with replacement" means that an element can be selected more than once, while "without replacement" means that an element can only be selected once. For example, in a combination with replacement, selecting a letter from a set of A, B, and C multiple times is allowed, while in a combination without replacement, each letter can only be selected once.

5. Are there any common mistakes when solving problems using combinations and permutations?

One common mistake is confusing combinations and permutations, as they have different formulas and yield different results. Another mistake is not properly understanding the problem and using the wrong formula or approach. It is important to carefully read and understand the problem before choosing a method to solve it.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
876
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
734
  • Set Theory, Logic, Probability, Statistics
Replies
31
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
411
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
  • General Math
Replies
1
Views
694
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Back
Top