I'm currently working on finding the row sequences of Pascal's triangle. I wanted to input the row number and output the sequence of numbers in a list up until that row. For example, (Pascal 4) would give the result (1 1 1 1 2 1 1 3 3 1).
I am trying to use an algorithm that I found. Here is the algorithm itself:
Vc = Vc-1 * ((r - c)/c)
r and c are supposed to be row and column, and V0=1. The algorithm can be specifically found on the wikipedia page in the section titled "Calculating and Individual Row or Diagonal."
Here is the code that I have so far:
(define pascal n)
(cond((zero? n) '())
((positive? n) (* pascal (- n 1) (/ (- n c)c))))
I know that's hardly anything but I've been struggling a lot on trying to find scoping the function with a let or a lambda to incorporate column values. Additionally, I've also been struggling on the recursion. I don't really know how to establish the base case and how to get to the next step. Basically, I've been getting pretty lost everywhere. I know this isn't showing much, but any step in the right direction would be greatly appreciated.
Using as a guide the entry in Wikipedia, this is a straightforward implementation of the algorithm for calculating a value in the Pascal Triangle given its row and column, as described in the link:
#lang racket
(define (pascal row column)
(define (aux r c)
(if (zero? c)
1
(* (/ (- r c) c)
(aux r (sub1 c)))))
(aux (add1 row) column))
For example, the following will return the first four rows of values, noticing that both rows and columns start with zero:
(pascal 0 0)
(pascal 1 0)
(pascal 1 1)
(pascal 2 0)
(pascal 2 1)
(pascal 2 2)
(pascal 3 0)
(pascal 3 1)
(pascal 3 2)
(pascal 3 3)
Now we need a procedure to stick together all the values up until the desired row; this works for Racket:
(define (pascal-up-to-row n)
(for*/list ((i (in-range n))
(j (in-range (add1 i))))
(pascal i j)))
The result is as expected:
(pascal-up-to-row 4)
> '(1 1 1 1 2 1 1 3 3 1)
I discussed Pascal's Triangle at my blog.
In your question, the expression for Vc is just for one row. That translates to code like this:
(define (row r)
(let loop ((c 1) (row (list 1)))
(if (= r c)
row
(loop (+ c 1) (cons (* (car row) (- r c) (/ c)) row)))))
Then you just put together a bunch of rows to make the triangle:
(define (rows r)
(let loop ((r r) (rows (list)))
(if (zero? r)
rows
(loop (- r 1) (append (row r) rows)))))
And here's the output:
> (rows 4)
(1 1 1 1 2 1 1 3 3 1)
The base case is (= r c) in the first function and (zero? r) in the second.
If you want to write subscripts clearly, you can adopt the notation used by TeX: subscripts are introduced by an underscore and superscripts by a caret, with braces around anything bigger than one character. Thus Vc in your notation would be V_c, and Vc-1 in your notation would be V_{c-1}.
