{"id":253,"date":"2017-05-21T15:31:15","date_gmt":"2017-05-21T22:31:15","guid":{"rendered":"https:\/\/blogs.ubc.ca\/organizingchaos\/?p=253"},"modified":"2018-02-09T20:56:14","modified_gmt":"2018-02-10T04:56:14","slug":"mathematical-aside-golden-mean-shift-and-pascals-triangle","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/organizingchaos\/2017\/05\/21\/mathematical-aside-golden-mean-shift-and-pascals-triangle\/","title":{"rendered":"Mathematical Aside: Golden Mean Shift and Pascal’s Triangle"},"content":{"rendered":"

I noticed something curious when I was working on my summer project<\/a> last year. Basically, you consider the set c_n of binary strings (strings of length n where each symbol is either a 1 or a 0 and 1‘s are non-adjacent).\u00a0 So we construct a table like<\/p>\n

 <\/p>\n\n\n\n\n
Length<\/strong><\/td>\n1<\/strong><\/td>\n2<\/strong><\/td>\n3<\/strong><\/td>\n4<\/strong><\/td>\n5<\/strong><\/td>\n6<\/strong><\/td>\n<\/tr>\n
Strings<\/strong><\/td>\n0;1<\/td>\n00;01;10<\/td>\n000;001;010;100;101<\/td>\n0000;0001;0010;0100;0101;1000;1001;1010<\/td>\n\u2026<\/td>\n\u2026<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

And then count the number of elements of length n with m ones.<\/p>\n\n\n\n\n\n\n\n\n\n
Number of ones [m] (below)<\/strong><\/td>\nNumber of strings (below)<\/strong><\/td>\n<\/tr>\n
Length of string [n] (right)<\/strong><\/td>\n1<\/strong><\/td>\n2<\/strong><\/td>\n3<\/strong><\/td>\n4<\/strong><\/td>\n5<\/strong><\/td>\n6<\/strong><\/td>\n<\/tr>\n
0<\/strong><\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
1<\/strong><\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n<\/tr>\n
2<\/strong><\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n3<\/td>\n6<\/td>\n10<\/td>\n<\/tr>\n
3<\/strong><\/td>\n<\/td>\n<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n4<\/td>\n<\/tr>\n
4<\/strong><\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Do you see Pascal’s Triangle hiding inside? Starting from the top left and diagonally down to the left. First one is 1,2,1, then is 1,3,3,1 etcThe explanation is simple enough. We are using the fact that the subset of \u00a0c_n composed of strings with m ones (lets call this c_{n,m}) can be made by taking an\u00a0element in c_{n-1,m} and appending a zero to it or an element in c_{n-2,m-1} and appending a zero-one to it. We end up with the recurrence\u00a0c_{n,m}= c_{n-1,m}+ c_{n-2,m-1}. If we consider d_{n,m} as the n^{th} element in the m^{th} diagonal, then we realize that d_{n.m} follows the same recurrence. This reccurence is well documented in the literature for calculating |c_n|, here we are just using this idea for subsets of c_n with exactly m ones to connect it with Pascal’s Triangle.<\/p>\n

The adventure continues in Part 2<\/a>!<\/p>\n","protected":false},"excerpt":{"rendered":"

I noticed something curious when I was working on my summer project last year. Basically, you consider the set of binary strings (strings of length where each symbol is either a or a and ‘s are non-adjacent).\u00a0 So we construct a table like   Length 1 2 3 4 5 6 Strings 0;1 00;01;10 000;001;010;100;101 […]<\/p>\n","protected":false},"author":28516,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":true,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13426,1],"tags":[],"class_list":["post-253","post","type-post","status-publish","format-standard","hentry","category-asides","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/253","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/users\/28516"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/comments?post=253"}],"version-history":[{"count":14,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/253\/revisions"}],"predecessor-version":[{"id":353,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/253\/revisions\/353"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/media?parent=253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/categories?post=253"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/tags?post=253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}