# HR F#: Pascal's Triangle

The second problem from the Recursive subdomain is printing Pascal's Triangle for given `n`

.

Pascal's triangle is named after famous French mathematician from XVII century, Blaise Pascal. His findings on the properties of this numerical construction were published in this book, in 1665. Year before Great Fire of London.

The first row of the triangle is just one. (N+1)th row is constructed from Nth row by prepending and appending the sums of pairs from the Nth row with 1s:

```
row(0) = 1
row(1) = 1 1
row(2) = 1 2 1
row(3) = 1 3 3 1
row(4) = 1 4 6 4 1
row(n+1) = 1 (row(n)[0]+row(n)[1]) (row(n)[1]+row(n)[2]) ... 1
```

The k-th element of the n-th row can be calculated by `n!/(k! (n-k)!)`

so the straightforward solution is just a single `for`

with a factorial routine:

```
let rec f n =
match n with | 0 | 1 -> 1 | _ -> n * f (n-1)
let line n =
seq { for k in 0..n do yield ((f n) / ((f k) * f (n-k))) }
```

This solution works well for the test data but it is a bit inefficient (to be precise, its complexity `O(n^2)`

) Multiplication is quite heavy and there is definitely room for improvements. For example, calculating the factorials can be replaced with lookup from pre-build table.

```
open System
let buildFactorialTable n =
let rec build v i =
seq { if i <= n then
yield (i * v)
yield! build (i * v) (i + 1) }
(1 :: (build 1 1 |> Seq.toList)) |> List.toArray
let line (ft : int array) n =
seq { for k in 0..n do yield (ft.[n] / ((ft.[k]) * (ft.[n-k]))) }
[<EntryPoint>]
let main argv =
let n = Console.ReadLine() |> int
let factorialTable = buildFactorialTable n
for i in 0..(n-1) do
printfn "%s" (String.Join (" ", line factorialTable i |> Seq.map string))
0 // return an integer exit code
```

Although it also works well, it only can calculate a few lines of the triangle. This is due to fact that factorial grows very quickly.

So the best solution is to generate next line directly from the previous:

```
open System
let lines n =
let rec build (prev : int list) i =
[ if i < n then
let line = [ yield 1
for p in Seq.pairwise prev do
yield (fst p) + (snd p)
yield 1 ]
yield line
yield! build line (i+1) ]
[ yield [1]; yield! build [1] 1 ]
[<EntryPoint>]
let main argv =
let n = Console.ReadLine() |> int
lines n
|> Seq.iter (fun line -> printfn "%s" (String.Join (" ", line |> Seq.map string)))
0 // return an integer exit code
```

Why not to stay updated if the subject is interesting? Join Telegram channel Alex@Net or follow alex_at_net on Twitter. Or just, use the comments form below.