Wikipedia:Reference desk/Archives/Mathematics/2015 November 22

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 22

A006355 - Number of binary vectors of length n containing no singletons - obvious proof?

I started looking at how many ways a season could go with every game being part of a 2+ game winning streak or a 2+ game losing streak. After calculating the examples for up to 6 games, I found OEIS: A006355, which has as one if its examples "a(6)=10 because we have: 000000, 000011, 000111, 001100, 001111, 110000, 110011, 111000, 111100, 111111. - Geoffrey Critzer, Jan 26 2014". So this is what I'm looking for. This sequence is a Fibonacci sequence starting with positive numbers: 0,2,2,4,6,10,16, etc. (So if you only count those where the team started out by winning, you get the standard Fibonacci series, offset)

So my question is, is there any obvious way to see in calculating that (for example) the number of 8 game seasons is equal to the sum of the number of 7 game seasons and the 6 game seasons?Naraht (talk) 08:49, 22 November 2015 (UTC)

Take all possible 7-digit sequences, repeat the last digit, and you get all possible 8-digit sequences ending in 000 or 111. Take all possible 6-digit sequences, append the opposite of the last digit twice, and you get all possible 8-digit sequences ending in 011 or 100. Combining these two cases, you get all possible 8-digit sequences. Egnau (talk) 13:17, 22 November 2015 (UTC)

A direct proof is this: Remove the initial and final digit from each sequence. Now for a given sequence, replace each 01 or 10 with a 2, and each digit between two of the same digit with a 1. For example 001110000110011111→0111000011001111→21211222111. This gives a 2 to 1 correspondence between the sequences of length n+2 and ways of writing n as a sum of 1's and 2's. If you count the latter you get the Fibonacci sequence. There are many similar correspondences between strings and sums satisfying certain criteria; some come from simple rewrite rules and some are more difficult. A surprising one is between strings of 0's and 1' that do not contain "101" (OEIS: A005251) and sums of 2's and 3's (OEIS: A000931) . --RDBury (talk) 15:23, 22 November 2015 (UTC)

@Egnau: That makes sense, thanx!Naraht (talk) 04:21, 24 November 2015 (UTC)