Solved

Permutation rules

Posted on 2016-10-27
8
37 Views
Last Modified: 2016-11-27
Dear experts,

I am going through Permutation and Combinations chapter from Magical Boo on Quicker Maths by M. Tyra. I have stumbled on the following points:

***
No. of selections of r things (r<=n) out of n identical things is 1

Total no. of selections of zero or more things from n identical thing = n+1

Total no. of selections of zero or more things from n different things = nC0 + nC1 + nC2 + nC3 +….nCn=(2)exp n

No. of ways to distribute (or divide) n identical things among r persons where any person may get any no of things = n+r-1Cr-1

Can anyone kindly refer me to a book on this subject or refer me to an article which can explain the above with an application or an example.

I am still in the process of going through this chapter for the second time, so most likely these are explained and I have not been able to associate these with the worked examples.

Kindly help
IMG_4035.JPG
0
Comment
Question by:Excellearner
8 Comments
 
LVL 27

Assisted Solution

by:BigRat
BigRat earned 150 total points (awarded by participants)
ID: 41868319
Well I'm not exactly happy about the degree of edactness in the book you are reading - that is to say providing your quotations are exact - for I don't want to upset the author but the very first statement needs qualifing
No. of selections of r things (r<=n) out of n identical things is 1

for it should read

No. of different selections of r things (r<=n) out of n identical things is 1

which is now perfectly true, for, there is no difference between the selections made. For if you line up 100 red identical balls and pick from the left numbers 1,3 and 5 or numbers 2,4 and 6 you will always have three identical red balls.

Now the next statement needs a similar qualification, for now you can pick only one ball, or two balls, or three balls and so on, and finally you can pick none at all. All of these selections are different - they differ by the number of balls from none to n and that makes n+1 selections in total.

Selections are usually termed permutations and the normal way of writing this nCk is using brackets containing the k below the n.

Now recommending a book is a bit difficult because I did all of this more than fifty years ago and in French. But you can Google the binomial theorem and Pascals Triangle like this one
http://www.mathsisfun.com/algebra/binomial-theorem.html

But don't hesitate to ask here.
0
 

Author Comment

by:Excellearner
ID: 41877486
Thank you Big.

I will respond tomorrow and close it as well. I have been away and hence could go through the response. Apologies.

Thank you
0
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 200 total points (awarded by participants)
ID: 41877527
>> Selections are usually termed permutations and the normal way of writing this nCk is using brackets containing the k below the n.
Did you mean combinations rather than permutations?
https://en.wikipedia.org/wiki/Combination
In mathematics, a combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. In smaller cases it is possible to count the number of combinations. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange.
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 27

Expert Comment

by:BigRat
ID: 41877551
Did you mean combinations rather than permutations?

I probably do. It's just that "combinasions" suits me better. LOL
0
 
LVL 32

Expert Comment

by:phoffric
ID: 41878077
The statements in your question are not definitions. I believe your difficulties may lie in your not understanding the definitions in your book.
>>  I have not been able to associate these with the worked examples.
By starting with the first example (hopefully an easy example), you should be able to begin to understand the definitions better.

If you would like, you can post the example(s) that you do understand (and explain it clearly to us), and then post the first example that you do not understand, and explain what part of the solution you do not understand.

In this subject of discrete math, it is a bad idea to read an entire chapter (let alone reading it twice) without understanding the worked out examples. STOP and ASK as soon as you come to the first worked out problem that you do not understand.

Finally, if you think you understand a worked out problem, then demonstrate to yourself that you know the problem by writing down the problem, close the book, do something else for a couple of hours, and then try to solve the problem yourself without the book. There is a big difference between understanding a problem, and knowing how to do a problem. Unless you follow these tips, then even if you understand all the worked out problems, there is a reasonable chance that you will not be able to continue on in the next chapter.

Knowing how to do a problem will help you understand the definitions.
0
 

Assisted Solution

by:Ed-SSA
Ed-SSA earned 150 total points (awarded by participants)
ID: 41879637
Two equivalent combinatorics problems can be expressed as:
1) How many ways can N-number of identical balls be distributed in M-number of identical buckets?   and
2) how many ways can N-number of stars be partitioned by M-number of bars?
Now impose identical constraints:
1) each bucket must contain at least 1 ball
2) any two bars must have at least 1 star between them.  

For me, the "stars and bars" is much easier to understand - it's graphical.
See:  https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Of course if you can (color) make the balls and/or buckets distinguishable, the stars and bars analogy is all but unusable, but if you google "combinatorics of buckets and balls" or "combinatorics of boxes and balls", you should find a few good references.

Your "Total no. of selections of zero or more things from n different things = nC0 + nC1 + nC2 + nC3 +….nCn=(2)exp n"
is Jacob Bernoulli's (1654 - 1705) binomial distribution. Jacob's brother Johann (math prof = student/slave labor) helped and documented Jacob's work. Gottfried Leibniz (co-inventor of calculus) a friend of Johann's, provided the manually operated calculator that he himself invented, circa 1685. Johann also wrote the first reference book on calculus for Gottfried.

If you have MS's Excel or Open Officer Calc, your playground is nearly unlimited.
Hint:  (2^25) * Binom.dist(s,25,0.5,0) = Combin(25,s)            Note: terms work in Excel 2007 and newer.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 200 total points (awarded by participants)
ID: 41879827
>> Total no. of selections of zero or more things from n different things = nC0 + nC1 + nC2 + nC3 +….nCn=(2)exp n

Here is a simple way to demonstrate this. Let n=3 which we can say represents as having three coins that may be selected.
Let T = 3C0 + 3C1 + 3C2 + 3C3
Instead of looking at the formula for nCk, consider its meaning.


3C1: How many ways can I pick exactly 1 coin out of 3 coins. Answer: I can pick exactly one coin from either position 1, 2, or 3.
Let's show these three possibilities by indicating a '1' for a selected coin, and a '0' for an unselected coin.
1 0 0
0 1 0
0 0 1
Looks obvious that there are only 3 ways to do this.

3C2: How many ways can I pick exactly 2 coin out of 3 coins.
1 1 0
1 0 1
0 1 1
Not as obvious, but we see that there are 3 ways to select 2 of the three coins.

3C3: How many ways can I pick exactly 3 coin out of 3 coins.
Of course, if you only have 3 coins, then to satisfy 3C3, you have to select all of them:
1 1 1

We see that the number of ways to pick one or more coins from 3 coins is 3 + 3 + 1 = 7 ways.
Now your problem is to select 0 or more coins, so we have to add 3C0:
0 0 0
Yeah, that's one more case to consider, so we have 8 ways which happens to be (2)exp3 = 2^3.

Let's rearrange these 8 cases in a special order that you may recognize:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

In the above table, we show all possible values in a 3 bit binary word. And in 3 bits, you can have 2^3 = 8 values.

https://en.wikipedia.org/wiki/Combination#Number_of_k-combinations_for_all_k
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Suggested Solutions

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now