Rude Boy Solutions
Solutions. For Life.

Fun With Numbers! (revised)

posted on: 5/29/2009, 8:48:00 AM

last updated: 9/14/2016, 7:56:00 AM

by: skamansam

This post is heavy with math formualae, so may take a few seconds to format correctly.
This post was originally written 2009/05/29, but was never finished. I just finished the revisions on 2016/09/14 and it is now complete.

I have always had a certain love for math and the neat things you can do with it. Here is a bit of information and shortcuts I have picked up in a few of my math classes.

Pascal’s Triangle

Pascal’s Triangle is a pretty neat thing. It is very simple to construct and can be used to understand a lot of different ideas. It follows a very simple form: start with a ‘1’ and add the two digits above  to get the next number. The first few line look like this:

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
...

The line numbers start at 0, and continue on ad infinitum. In order to generate this triangle, programmatically, you would use something like this:

vector<int> pascal(
      vector<int> prev, //the current (old) row data
      int *len,		//the length of the data
      int end,			//the row to retrieve
      int cur=0		//the current row we are on
      );

vector<int> pascal(vector<int> prev,int *len,int end,int cur){

       //return immediately if we are at the last row
      if (cur==end) return prev;

     	//if the current vector length is 0, then set it to 1
      	if (*len==0) *len=1;

      	//create a temp vector (all 1's) to store the new row data
      	vector<int> t((*len)+1,1);

      	//sum the two rows
      	for(int i=1;i<(*len);i++)
            t[i]=prev[i-1]+prev[i];

      	//increase the length by 1
      	*len=(*len)+1;

      	//return the new row data
      	return pascal(t,len,end,cur+1);

}

Binomial Expansion

Remember binomials from algebra? They were the pair of numbers used to create or simplify polynomial expressions, something like:

(x+3)3=x3+9x2+27x+27( x + 3 )^3 = x^3 + 9x^2 + 27x + 27

You can use Pascal’s triangle to find the coefficients of the polynomials. Let’s begin by solving for the generic case:

(a+b)n=(a+b)n1(a+b)=(a+b)n2(a+b)2=(a+b)n2((a+b)(a+b))=((aa)+(ab)+(ba)+(bb))(a+b)n1=(a2+2ab+b2)(a+b)n1=(a+b)^n = (a+b)^{n-1}(a+b) = (a+b)^{n-2}(a+b)^2 = (a+b)^{n-2}((a+b)(a+b)) = ( (a*a) + (a*b) + (b*a) + (b*b) )(a+b)^{n-1} = (a^2+2ab+b^2)(a+b)^{n-1} =

See the coefficients so far, with n=2n = 2 ? They are [1 2 1], which corresponds to the second row in Pascal’s triangle. But this could be a fluke, right, so let’s jump ahead to n=5n = 5 to see if that works as well.

(a+b)n=(a+b)n6(a+b)5=(a+b)n6((a+b)(a+b)(a+b)(a+b)(a+b))=(a+b)n6(((a+b)(a+b))((a+b)(a+b))(a+b))=(a+b)^n = (a+b)^{n-6}(a+b)^5 = (a+b)^{n-6}( (a+b) (a+b) (a+b) (a+b) (a+b) ) = (a+b)^{n-6}( ( (a+b)(a+b) )( (a+b)(a+b) ) (a+b) ) =

[we know what (a+b)2(a+b)^2 is, so: ]

((a2+2ab+b2)(a2+2ab+b2)(a+b))(a+b)n6=(((a2a2)+(a22ab)+(a2b2)+(2aba2)+(2ab2ab)+(2abb2)+(b2a2)+(b22ab)+(b2b2))(a+b))(a+b)n6=((a4+2a3b+a2b2+2a3b+4a2b2+2ab3+b2a2+2ab3+b4)(a+b))(a+b)n6=((a4+4a3b+6a2b2+4ab3+b4)(a+b))(a+b)n6=(( a^2+2ab+b^2 )( a^2+2ab+b^2 )(a+b) )(a+b)^{n-6} = ( ( (a^2*a^2)+(a^2*2ab) + (a^2*b^2) + ( 2ab*a^2) + (2ab*2ab) + (2ab*b^2) + (b^2*a^2)+(b^2*2ab) + (b^2*b^2) ) (a+b) )(a+b)^{n-6} = ( ( a^4 + 2a^3b+ a^2b^2 + 2a^3b + 4a^2b^2 + 2ab^3 + b^2a^2 + 2ab^3+ b^4) (a+b) )(a+b)^{n-6} = ( ( a^4 + 4a^3b + 6a2b^2 + 4ab^3+b^4) (a+b) )(a+b)^{n-6} =

[note: notice that the coefficients of (a+b)4(a+b)^4 are (1 4 6 4 1) ! ]

((a4a+a4b+4a3ba+4a3bb+6a2b2a+6a2b2b+4ab3a+4ab3b+b4a+b4b))(a+b)n6=((a5+a4b+4a4b+4a3b2+6a3b2+6a2b3+4a2b3+4ab4+ab4+b5))(a+b)n6=((a5+5a4b+10a3b2+10a2b3+5ab4+b5)(a+b)n6( ( a^4*a + a^4*b + 4a^3b*a + 4a^3b*b + 6a^2b^2*a + 6a^2b^2*b + 4ab^3*a + 4ab^3*b + b^4*a+b^4*b))(a+b)^{n-6} = ( ( a^5 + a^4b + 4a^4b + 4a^3b^2 + 6a^3b^2 + 6a^2b^3 + 4a^2b^3 + 4ab^4 + ab^4+b^5))(a+b)^{n-6}= ( ( a^5 +5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5)(a+b)^{n-6}

There it is! The coefficients correspond to the rows on Pascal’s Triangle!

Features

Now, to make things a little simpler, I will note some interesting “features” about what we just did.

General Formula for Binomial Expansion

The general formula for binomial expansion is:

(a+b)n=i=0n(Pnianibi)(a+b)^n = \sum_{i=0}^{n}(P_{ni}a^{n-i}b^i)

Where PniP_{ni} is the coefficient at row nn (starting from 0) and column ii in Pascal’s Triangle. The formula means to add from i=0i=0 to nn all the terms (Pnianibi)(P_{ni}a^{n-i}b^i) , replacing ii with the number you are at. For example, supposing i=3i=3, you would get:

i=03(P3ia3ibi)=\sum_{i=0}^{3}(P_{3i}a^{3-i}b^i) =
(P(3,0)a30b0)+(P(3,1)a31b1)+(P(3,2)a32b2)+(P(3,3)a33b3)=(P_{(3,0)}a^{3-0}b^0) + (P_{(3,1)}a^{3-1}b^1) + (P_{(3,2)}a^{3-2}b^2) + (P_{(3,3)}a^{3-3}b^3) =

since P3=[1331]P_3 = [1 3 3 1] , we finally get:

((1)a30b0)+((3)a31b1)+((3)a32b2)+((1)a33b3)((1)a^{3-0}b^0) + ((3)a^{3-1}b^1) + ((3)a^{3-2}b^2) + ((1)a^{3-3}b^3)

cleaning up a bit :

a3+3a2b+3ab2+b3a^3 + 3a^2b + 3ab^2 + b^3

Exponents

Note in all the expansions, the first variable counts down from nn to 00, while the second variable counts up from 00 to nn.

Does your binomial already have coefficients?

If your binomial already has coefficients, simply put them with their terms like so:

i=0n(Pni(xa)ni(yb)i)\sum_{i=0}^{n}(P_{ni}(xa)^{n-i}(yb)^i)

Using the commutative property, it can be rewritten as such:

i=0n(P3i(xniyi)anibi)\sum_{i=0}^{n}(P_{3i}(x^{n-i}y^{i})a^{n-i}b^i)

Let’s try an example!

(3a+2b)3=(1)(3a)3(2b)0+(3)(3a)2(2b)+(3)(3a)(2b)2+(1)(2b)3=(1)(33)a3+(3)(322)a2b+(3)(322)ab2+(1)(23)b3=(1)(27)a3+(3)(18)a2b+(3)(12)ab2+(1)(8)b3=27a3+54a2b+36ab2+8b3(3a+2b)^3 = (1)(3a)^{3}(2b)^0 + (3)(3a)^{2}(2b) + (3)(3a)(2b)^2 + (1)(2b)^3 = (1)(3^3)a^3 + (3)(3^2*2)a^{2}b + (3)(3*2^2)ab^2 + (1)(2^3)b^3 = (1)(27)a^3 + (3)(18)a^{2}b + (3)(12)ab^2 + (1)(8)b^3 = 27a^3 + 54a^{2}b + 36ab^2 + 8b^3

Conclusion

As you can see, it is fairly easy to use Pascal’s Triagel as a lookup table for binomial exapnsion’s coefficients. I hope you have much more fun in your maths!