Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3
PASCAL’S TRIANGLE

In this chapter, we discuss Pascal’s triangle and explain the relevance of its entries to number theory.

FACTORIALS

As you are probably aware, n!, or n factorial, is the product of the first n positive integers, that is,

We define 0! to be 1. There are n! permutations of n distinct objects.

There are two ways (at least) of programming factorial. One uses the definition: factorial of n is the product of the first n integers. This is called the iterative way. It is not too unsurprising that this is coded using a for-loop, going from 1 to n. The exact coding is

var ans = 1;
  for (var j=1;j<(n+1);j++){
 ans *= j;
 }

The second way uses recursion. The informal definition of a recursion function is one that calls itself. (A critical concept in theoretical computer science is that the recursive functions are the set of functions obtained when starting with a small set of functions and allowing certain function making procedures including composition and finding the inverse. One of the function making procedures is termed primitive recursion.) Using recursion, factorial is

If n ≤ 1, factorial(n) is 1
Otherwise, factorial(n) is n*factorial(n − 1)

(This definition is written in what is termed pseudocode, a combination of coding and English.)

This definition can be used as the basis of a program. This may be surprising and the technique can be misused. The programmer has to be sure that the recursion will end; that is, that it isn’t equivalent to circular reasoning. In this particular case, observe that the value passed as the parameter to the factorial function is going down and so will eventually reach 1. The relevant code in my program is

function worker(n){
 if (n<=1) { return 1;}
 else {return n*worker(n-1);}
}

So now let’s ask the question, which way is better? That is, which is faster? The answer was slightly different than I anticipated. Before giving away the punch line, let me say why I thought that iteration would be better. Recursion is a wonderful technique. However, certain operations are performed when we use recursion. There is something called the program stack, and information about each function call is pushed onto the stack and used until the function completes and then it is popped, removed from the stack. My thinking was that the bookkeeping for a for-loop is less computationally heavy than the bookkeeping for function calls.

I added code to keep track of time, using Date, and getTime, as was done in earlier examples. By the way, I needed to extract the functionality that displayed the answers from the inner program. That is why you see a function called worker in my example. You can examine both programs at the end of the chapter.

It was the case that at some point (you figure out when), there was an error message of too much recursion! However, before that point, for both the iterative approach and the recursion approach, something else broke down! The numbers grew too big. Recall scientific notation. The number 123 can be expressed as 1.23 times 10². It also can be expressed as 12.3 times 10¹ or 123 times 10⁰.

This is called floating point in programming. All numbers in JavaScript are kept using what is termed double precision, using 64 bits, each bit being a 1 or a 0. For the 64 bits, using the numbering system 0 to 63, bits 0 to 51 hold a number, bits 52 to 62 hold an exponent, and bit 63 is used for a sign (0 for positive and 1 for negative). Now, returning to example above with 123 (which conveniently uses decimal, i.e., base 10), let’s say our system only allowed three decimal spaces for the number. Our system could not precisely express 1234! Let’s say our system only allowed the exponent to be 0 to 9. Then the system could not express small numbers such as .12 or very big ones. JavaScript is better than what I just described, but if and when a number exceeds its capacity in one of these ways, JavaScript says the number is infinity! Try it. As it turns out, though iterative factorial does not produce the too much recursion error, the fact that the number is outside the capacity of double precision occurs the same time for both methods.

If you have an application in which double precision is not good enough, then you can try and find a library for arbitrary or unlimited precision. Such libraries exist and we may use one for a later topic.

THE COMBINATORIAL NUMBERS n CHOOSE k

Let us consider the following problem. Given n distinct objects, in how many ways can we select k of them where order does not matter? If I have three extra tickets to a baseball game and I have 10 friends, in how many ways can I select the lucky trio of friends who will receive free tickets? Here, order does not matter. The choice Newton, Archimedes and Euclid is the same as the choice Euclid, Newton and Archimedes.

We begin with the first k factors of n!, namely, . This is because there are n ways to pick the first object, n − 1 ways to pick the second object, and so on till the last choice (the kth object), which can be made in (n − k + 1) ways.

The expression is too big to be the answer to our problem. To see this, consider the number of combinations of three objects from among six distinct objects. Let the six objects be the letters A through F. The three-letter choice ACD, for example, will be counted six times instead of once. It will appear in the list of permutations as ACD, ADC, CDA, CAD, DCA, and DAC. But we only want it (and all the other combinations such as ACE, etc.) listed once in the list of combinations. So we divide by 6—the number of permutations of three objects. This suggests the following procedure for the number of combinations of k objects chosen from among n distinct objects. Divide the product by k!. In symbols,

(3.1)

The symbol on the left of Equation 3.1 is pronounced “n choose k.” If we multiply the numerator and denominator by (n − k)!, we obtain the alternative formula

3.2a

The numerator of the middle expression in (3.2a) is seen to be n! after we expand the (n − k)!, thereby realizing it supplies all the factors of n! that were missing in the numerator of 3.1.

Let’s rewrite (3.2a) without the middle expression:

3.2b

The numbers k and n − k in the denominator of (3.2b) are called complements because they add up to n. If we replace each k by its complement, n − k, we obtain

or, more simply,

(3.3)

After all, choosing a meal of k dishes from a menu of n is equivalent to indicating the n − k dishes not chosen. Thus, to evaluate images , it is easier to evaluate images .

Observe that “n choose n” yields two answers, which may be compared. On the one hand, it is, using formula (3.2b), , while on the other hand, common sense tells us that the answer must be 1. (There is only one way to choose all n objects.) It follows that 0! must be 1. Moreover, it follows that images .

Another useful observation is that images .. This could, of course, be verified without the help of Equation 3.1 by using common sense. There are n ways to choose one item among n distinct items.

PASCAL’S TRIANGLE

There is an ancient array of numbers called Pascal’s triangle, shown below up to the seventh row. (The name of the row is given by the second entry, printed in bold.)

Each entry is the sum of the two entries immediately above it. Thus, the first 35 in the seventh row is the sum of the 15 and 20 in the sixth row. You should have no trouble obtaining the entries of the eighth row using this method of generation.

When first confronting the exercise, I admit that I thought of using the factorial and the n choose k formulas as described next in this chapter. However, I quickly decided that the basic definition could be a sound alternative. That is, each row of the triangle is constructed from the last. If I could keep track of positions, it would be a good way.

How can I (my code) produce the next row? The first step is to take a row and add in what I view as the ghost elements, a zero at the start and a zero at the end. If the row is

1 3 3 1

then my code constructs an array of elements: 0, 1, 3, 3, 1, 0.

The next row will be

0 + 1, 1 + 3, 3 + 3, 3 + 1, 1 + 0.

This next row is one longer than the original row. The challenge is to produce the extended row. As it turns out, JavaScript has two array methods that do exactly what is called for: unshift adds a new element at the start and push adds a new element at the end. These methods (method is the technical term for a function associated with a given class of objects, in this case, with arrays) actually change the array and return the length of the new array. I use this in the code:

count = last.unshift(0);

Another challenge of the coding is that I use a for-loop inside a while loop. A variable called limit is used to keep count of the number of rows remaining to be done. You can examine the code at the end of the chapter.

One last point, I did have a worry about formatting the triangle nicely, but it came almost for free. I am using JavaScript with html and html has <center> and </center> tags. My code creates a long string of characters. The code turns the numbers into character strings using String and puts a space between numbers using the entity. It stands for nonbreaking space. A line break is indicated by the tag <br/>. Centering centers each line.

BINOMIAL COEFFICIENTS

Now, it is amazing that the entries of the nth row of Pascal’s triangle consist of the n + 1 combinatorial numbers:

These combinatorial numbers are the coefficients in the expansion of (a + b)ⁿ and are often called binomial coefficients. Moreover, the third entry of each row, that is, the numbers of the form images , are the sums of the positive integers from 1 to n − 1, as can be seen by using equation 1.2 in Chapter 1, after replacing n by n −1. These numbers are triangular.

The principle used to generate the (n + 1)st row from the nth row can be written as

(3.4)

EXERCISES

An asterisk (*) indicates that the exercise can be developed into a research project.

Write a program to find n! for a given nonnegative integer, n. Then use this program to tabulate n! for all n ≤ 20. You can use either of the factorial examples to help you do this.
Using the previous exercise, write a program to find for a given pair of integers k and n such that 0 ≤ k ≤ n/2, with n ≠ 0, using formula (3.2). (Why can we assume that k ≤ n/2?)
Now, write a program to find using formula 3.1. Which program is faster? Why?
Write a program that prints out the first k rows of Pascal’s triangle for a given k. See the example at the end of the chapter. Perhaps you can improve the formatting.
10! = 6!7!. Are there more relations of the form c! = a!b! where 2 ≤ a ≤ b < c ≤ 30?
^*The 14th oblong number, 210, can be written as 5 × 6 × 7. Are there other oblong numbers less than 1000 that can be written as products of three consecutive numbers?
^*Find all triangular numbers less than 1000 that can be written as products of three or more consecutive integers.
^*Show that for n ≤ 100.
The Catalan numbers are defined by and are useful in combinatorics, number theory, and computer science. They satisfy the recurrence relation . Find the first 100 Catalan numbers (i) using this recurrence and (ii) using the definition. Which is faster?
For n ≤ 1000, show that the entries of the nth row of Pascal’s triangle, excluding the initial and final 1’s, are all even if and only if n is a power of 2. The entries of the fourth row, for example, are 1, 4, 6, 4, 1, which, except for the initial and final 1’s, are even.
For n ≤ 100, show that .
For n ≤ 100, show that .
^*Verify that the following infinite array of equations involving the triangular numbers is correct for n ≤ 100.
Find 50 primes of the form 5n + 1.
Given the polynomial f(n) = n² + n + 41, verify that f(n) is prime for n = 0, 1, 2, …, 39.
Show that n! is not a square when 1 < n < 50.
^*Consider the equation n!m! = s!t! where m > n and t > s. Write a program that accepts the values of n and m from the user and finds a pair s and t or determines that none exists. Verify that 4!15! = 7!13! yields an example of this equation.

Iterative Factorial

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Factorial Iterative</title>
<script>
function fac(ns){
var n = parseInt(ns);
var start = new Date();
var startmm = start.getTime();
var ans = 1;
for (var j=1;j<(n+1);j++){
ans *= j;
}
var now = new Date();
nowmm = now.getTime();

var elapsed = nowmm - startmm;
alert("ans is "+ans+" performed in "+elapsed+" msec.");
return ans;
}
 
</script>
</head>
<body>
Choose limit <br/>
<form name="f" onsubmit="return fac(this.num.value);">
<input type="text" name="num" value="  "/>
<input type="submit" value="Submit a number "/>
</form>
<p id="place">
The answer will go here.
</p>
</body>
</html>

Recursive Factorial

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Factorial Recursive</title>
<script>
function fac(ns){
var n = parseInt(ns);
var start = new Date();
var startmm = start.getTime();
var ans = worker(n);
var now = new Date();
nowmm = now.getTime();
var elapsed = nowmm - startmm;
alert("ans is "+ans+" performed in "+elapsed+" msec.");
return ans;
}
function worker(n){

if (n<=1) { return 1;}
else {return n*worker(n-1);}
}
 
</script>
</head>
<body>
Choose limit <br/>
<form name="f" onsubmit="return fac(this.num.value);">
<input type="text" name="num" value="  "/>
<input type="submit" value="Submit a number "/>
</form>
<p id="place">
The answer will go here.
</p>
</body>
</html>

Pascal’s Triangle

<title>Pascal's Triangle</title>
<script>
 
function triangle(ns){
var limit = parseInt(ns);
var output = "<center>";
output +="1<br/>";
var last = [1];
var lastext;
var next;
var val;
limit––;
while (limit>=0) {
//unshift and push each change the array itself. 
//Each returns new length
count = last.unshift(0);
last.push(0);
next = []; 
       
for (var i=0;i<count;i++){
val = last[i]+last[i+1];

next.push(val);
output+=String(val)+" ";
}
output+="<br/>";
 
last = next;
limit––;
}
 
output+="</center>";
document.getElementById("place").innerHTML = output;
return false;
}
</script>
</head>
<body>
Choose limit <br/>
<form name="f" onsubmit="return triangle(this.num.value);">
<input type="text" name="num" value="  "/>
<input type="submit" value="Submit a number "/>
</form>
<p id="place">
The answer will go here.
</p>
</body>
</html>

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3 PASCAL’S TRIANGLE

Create new playlist

Sign In

Sign Up

FACTORIALS

THE COMBINATORIAL NUMBERS n CHOOSE k

PASCAL’S TRIANGLE

BINOMIAL COEFFICIENTS

EXERCISES

Table of Contents for
3 PASCAL’S TRIANGLE