Wikipedia:Reference desk/Archives/Mathematics/2011 September 21

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.

September 21

Binary numbers with no adjacent 1s

I was calculating how many patterns there are for binary numbers of length L where there are never two adjacent 1s.
Thus L1 has 1 = 1
L2 has 01 and 10 = 2
L3 has 001 010 100 and 101 = 4
L4 has 0001 0010 0100 1000 0101 1010 1001 = 7.
Further terms are L5 = 12, L6 = 20, L7 = 33, L8 = 54, L9 = 88 etc.
It turns out that these are the fibonnaci numbers less one. Is there any reason why these are related to the fib nos, or is it just a big coincidence? -- SGBailey (talk) 15:15, 21 September 2011 (UTC)

They satisfy the Fibonacci recurrence. Count the number of admissible binary strings of length n, conditioned on whether the first digit is a 1 or 0. Sławomir Biały (talk) 15:27, 21 September 2011 (UTC)

Sorry - I don't understand what your reply says. Can expand or rephrase or something please. -- SGBailey (talk) 15:30, 21 September 2011 (UTC)

What makes it a little more consistent is that you are dropping the all zero case. Once you add that, you end up with a fairly easy construction. L(N) consists of all of the entries in L(N-1) with a 0 added at the front and all of the entries of L(N-2) with a 10 added at the front so L4 = 0/000 , 0/001, 0/010, 0/100, 0/101 and 10/00, 10/01, 10/10. (It works out the same with a 0 added at the end of the L(N-1) and a 01 added at the end of L(N-2))Naraht (talk) 15:35, 21 September 2011 (UTC)

Note that the string counts don't satisfy the Fibonacci recurrence - they satisfy

$x_{n}=x_{n-1}+x_{n-2}+1$

It just so happens that $x_{n}=F_{n}-1$ satisfies that recurrence too. Gandalf61 (talk) 15:38, 21 September 2011 (UTC)

Sorry, I didn't realize we were excluding the case of all zeros. The recurrence is easier to get if you don't artificially exclude this possibility. Sławomir Biały (talk) 16:03, 21 September 2011 (UTC)

It's sequence A000071 in the OEIS, if any of that gives you a lead. Grandiose (me, talk, contribs) 15:31, 21 September 2011 (UTC)

Makes sense now. Thanks. -- SGBailey (talk) 18:21, 21 September 2011 (UTC)

Mandatory link: Fibonacci coding. -- Meni Rosenfeld (talk) 07:45, 22 September 2011 (UTC)

eating mashed potatoes with your hands when silverware is available

Some (all?) computer programming languages required everything to be written using only characters on standard keyboards. One can write 3 x 4 (with the letter x as a substitute for ×) when one types a letter, but in programming languages one wants that letter to be available for other uses, so a workaround was adopted, the asterisk: 3 * 4.

But within Wikipedia there's a little menu from which one can chose the "×" character, and in TeX and LaTeX and the like one can write

$3\times 5,\qquad 3\cdot 5,\qquad 3\otimes 5,\qquad 3\boxtimes 5,\qquad 3\odot 5,$

etc., etc. There's no need for uncouth substitutes or workarounds.

But within Wikipedia and elsewhere, even today, one finds people eating mashed potatoes with their hands when silverware is available, writing

$3*5\,$

in TeX!

Are people being taught in school today that the use of the asterisk for this purpose is a standard thing rather than a substitute used in the remote wilderness when limited to keyboard characters? Michael Hardy (talk) 20:18, 21 September 2011 (UTC)

(I posted this to the language reference desk as well.) Michael Hardy (talk) 20:18, 21 September 2011 (UTC)

I don't think this is something that's taught as correct from a notational point of view, because, for example, I don't ever (well, hardly ever) see people use asterisks when they write math by hand. I think people just learn through experience with things like spreadsheets, programming languages, Texas Instruments calculators, and so on that the asterisk is the character that represents multiplication when dealing with computers, so they use it here too. On the other hand, I don't think I've ever been explicitly told by anyone that, in ordinary usage, the asterisk is not an acceptable substitute for a proper multiplication sign—I just had to infer that by reading a lot of math and noticing the symbols that were used. So the answer, I think, is that notation is rarely taught explicitly; everyone picks up notation by observing patterns in what everyone else uses, and some people don't notice (or haven't yet noticed) that the use of the asterisk is generally limited to certain contexts. —Bkell (talk) 22:18, 21 September 2011 (UTC)

Silverware is not always available. I can not write 3×5 cm² in an email. Editing wikipedia, after typing 3\times 5\,cm^2 you must type alt+shift+P in order to see the picture $3\times 5\,cm^{2}$, which is not silverware calligraphy anyway. Mathematics was written by hand by people who knew the greek alphabet, but now the notation is intimidating to young readers, and even computers do not understand it. The old mathematical notation must eventually be replaced by some programming language. Personally I like the J (programming language). The last word has probably not been said yet. Bo Jacoby (talk) 10:17, 22 September 2011 (UTC).

I don't understand what you mean by saying you need to type alt+shift+P to see $3\times 5\,cm^{2}$. On the machine I'm at, alt+shift+P is for "private browsing". I certainly don't need to do that in order to see $3\times 5\,cm^{2}$. Michael Hardy (talk) 22:14, 22 September 2011 (UTC)

alt-shift-p is the shortcut for the 'Show preview' button. Bo Jacoby (talk) 06:12, 23 September 2011 (UTC).

I usually prefer that people write asterisks on computers so expressions can more easily be copy-pasted to a program or expression parser. I read some math mail lists and forums where it's possible to write × but nobody does it and it would be very annoying if they did. But in Wikipedia I write × in articles (not always in discussions). PrimeHunter (talk) 12:18, 22 September 2011 (UTC)

Does anyone commonly use × for multiplication past elementary school level math? In my own experience I would say no. It's too easy to confuse it with the letter x, even if you're using a type set that distinguishes them. If a student used × for multiplication, I would tell them not to. I don't think it's correct to assume that using × is the standard notation, since this seems to contradict the empirical evidence. Rckrone (talk) 19:38, 22 September 2011 (UTC)

You're quite mistaken. For one thing, it's used for the cross-product of vectors, and it's commonly used when writing about measurements or referring, for example, to an $n\times m$ matrix. It's also used for Cartesian products of sets and spaces and direct products of groups. It is used in some contexts when the only things one is multiplying are integers, e.g. when talking about prime factorizations of numbers. And sometimes it's used as the last character on a line when one wants to make it clear that the list of factors being multiplied continues on the next line. Michael Hardy (talk) 22:18, 22 September 2011 (UTC)

Of course it's used for things that aren't multiplication (cross product, Cartesian product), but it's only used for multiplication in very specific circumstances. I guess I just don't understand why you're implying we would be better off if it were used more widely (as in your silverware/hands/mashed potatoes analogy). I think most people don't use × because it isn't the convention, not because of a failure to take advantage of the tools available. Rckrone (talk) 05:33, 23 September 2011 (UTC)

I think $3\times 5$ is probably better than $3*5$ because of the possibility of confusing the asterisk for its use in some formulations of regular expressions. I think $3\cdot 5$ is still better. Can't say I see it as a huge issue in any case. Certainly not one for the math refdesk — might have made more sense on WT:WPM. --Trovatore (talk) 05:44, 23 September 2011 (UTC)

WT:WPM is for discussing what ought to be done with Wikipedia articles on math, not for finding out what is done in classrooms. Michael Hardy (talk) 18:20, 23 September 2011 (UTC)

See the images at Tuf | Board Game | BoardGameGeek.

—Wavelength (talk) 06:23, 23 September 2011 (UTC)