Balls into urns | Image by author

Pascal’s Identity with Balls and Urns

Hello!

If you are a high school student or you have just recently passed out from one and if you have had taken math you might already know about the infamous “Pascal’s Triangle”. Even if you do not no worries as we will see it is called a triangle and it looks like a triangle but not actually a triangle (Bam!).

If you have come across pascal’s triangle before you may or may not know about-wait for it- the “Pascal’s Identity”. Now if you guys know about the triangle and the identity you also know how easy it is to derive from the triangle.

But what many of you do not know is that how you can intuitively compare the identity where you need to arrange balls into urns so that no urn goes empty! That is to say, you will know instantly where you will need to use the identity though there is not visibly anything related to a triangle around you!

The Binomial Coefficient and The Pascal’s Triangle

Now please do not tell me you haven’t heard about the Binomial Theorem.. well yeah it is possible but you may have heard about the well-known formula (a + b)² = a² + 2ab +b². Binomial -as in the name, means two things, the ‘a’ and the ‘b’. That is to say an expression such as this (a + b)² or say (1 + x)³ etc is called a binomial expression with two terms inside the bracket. And the right-hand side of the equation- a² + 2ab +b² is called the Binomial Expansion. As you can clearly see it is the de-simplified/expanded form of the binomial expression. Let us take 3 or 4 binomial expressions and take their expansion:

Some binomial expansion examples | Image by author

Now if we take binomial expansions of terms like (1+x)⁹ it would be possible to calculate of course but it would get pretty hard to sit and calculate as the power of the binomial expression increases. So to simplify that we have something called the Binomial Theorem. We will not go in-depth with that but know this that formula really simplifies the expansion of binomial coefficients containing large powers.

Have you noticed? In the previous example of 4 binomial expansions, the coefficient of each term looks like it follows a pattern. The same thing was noticed by Pascal back in the days and the pattern is as follows:

The Pascal’s Triangle | Image by author

So you now know the coefficients of the binomial expansion when set up like a pyramid we get Pascal’s triangle.

But again still it is tedious to calculate by summing down the pyramid until we find our needed binomial coefficient for the expansion. So we may use the coefficient formula from the binomial theorem stated as:

where r is the row number (i.e the power of the binomial expression. Also note that the row starts from 0.) and n is the nth coefficient you want to find for that expression. (Note that n also starts from 0.) So that now the triangle will look like:

Combinatorial Pascal’s Triangle | Image by author

If you have noticed the nth value of the rth row is the sum of the nth and (n-1)th value of the (r-1)th row such that

Pascal’s Identity | Image by author

That is in the equation you can say the nth term in rth row is:

And this identity above, the formula you are seeing is called Pascal’s Identity.

Given R identical balls and N unique urns

Given R identical balls, what is the number of ways in which you can distribute them in N uniquely marked urns so that no urn goes empty?

To solve this problem let us proceed with putting one ball in each of the N urns so now we are left with (R-N) balls. Now if we put all these (R-N) balls in the ground and put N-1 sticks with/between them such that, any number of balls between two consecutive lines represents an urn.

Balls and Bars Method | Image by author

So there are total of (R-N) + (N-1) items to be arranged. But since All the balls and the bars are identical we divide the arrangement with (R-N)! and N!

Now look at the last identity doesn’t it look something familiar? Let us try and solve this some in some other way using pascal’s identity:

This represents, Arrangements where no urn can be empty = Total arrangement - A or, A = Total arrangement - Arrangements where no urn can be empty = Arrangement where there is at least one empty urn.

ie, A= Arrangement where there is at least one empty urn.

So it is hence proved that you can present Pascal’s identity such as the total number of arrangement of R identical balls into N non-identical unique urns is equal to total arrangements where no urn is empty plus all the possible arrangement where at least one urn is empty.

If this is whatsoever a little complex to understand for newbies who are relatively new to Combinatorics, I suggest them to learn more about The Binomial Theorem, The Pigeonhole Principle (The idea of which we used at first to put one ball in each of the urns so no urn goes empty) and last but not least the Stars and Bars Technique.

Do connect with me so you can receive notifications whenever a new blog of mine is out. Until then stay safe and healthy!