# Permutation rules

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
###### Who is Participating?

Commented:
>> 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

Commented:
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 Commented:
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

Commented:
>> 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

Commented:
Did you mean combinations rather than permutations?

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

Commented:
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

RetiredCommented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.