Math: Sierpinski's Triangle is a Variation of Pascal's Triangle

Here's a picture of Pascal's triangle from Wikipedia. It's animated just in case you don't remember how Pascal's triangle is created:



Here's a picture of Sierpinski triangle, also from Wikipedia:



You can see in the top image that to calculate a spot in Pascal's triangle, you just add the two above spots. To get Sierpinski's triangle instead of Pascal's triangle, you just xor the above two spots. Cute trick, eh?

I learned this trick while reading Concepts, Techniques, and Models of Computer Programming, which is a fantastic book, by the way. Here's my Oz code for printing out Pascal's triangle:
% This is a generic version of Pascal's triangle that let's you specify the
% operation instead of just using "+".

declare GenericPascal OpList ShiftLeft ShiftRight
fun {GenericPascal Op N}
if N==1 then [1]
else L in
L={GenericPascal Op N-1}
{OpList Op {ShiftLeft L} {ShiftRight L}}
end
end

fun {OpList Op L1 L2}
case L1 of H1|T1 then
case L2 of H2|T2 then
{Op H1 H2}|{OpList Op T1 T2}
end
else nil end
end

fun {ShiftLeft L}
case L of H|T then
H|{ShiftLeft T}
else [0] end
end

fun {ShiftRight L} 0|L end

declare
fun {FastPascal N} {GenericPascal Number.'+' N} end

for I in 1..10 do {Browse {GenericPascal Number.'+' I}} end

Comments