1
$\begingroup$

I am writing up an assignment with includes many identities of Fibonacci numbers. I have made up the following notation (here $f_n$ is the number of tilings of an $n$-board by dominoes and squares - a well known interpretation of Fibonacci numbers):

Given an $n$-board, and some sequence $seq$ of dominos and squares, let $f_n^{seq}$ represent all tilings of an $n$-board that end with the sequence $seq$. So for example $f_n^{DS}$ are all tilings of an $n$-board that end with a domino succeeded by a square. Furthermore, for repeating sequences write: $ \underbrace{seq,seq, \cdots, seq}_{n-\text{times}} = n\cdot seq $ So for example $f_n^{SSDSDSDSDS} = f_n^{2S4DS}$. Let the size of a sequence $|seq|$ be the number of tiles the sequence occupies, so $|SS4DS| = 14$. It is clear that: $ f_n^{seq} = f_{n - |seq|} $

How may this be improved? Are statements such as

$ f_{3n-3k} = f_{3n}^{kDS} = f_{3n}^{SSkDS} + f_{3n}^{DkDS} + f_{3n}^{(k+1)DS} = f_{3n-3k}^{SS} + f_{3n-3k}^{D} + f_{3n-3k}^{DS} = $ $ = 2f_{3n-3k-2} + f_{3n-3k-3} $

a bit understandable without explanation? (I do offer an explanation of course).

  • 0
    An $1\times n$ board to be precise :)2011-03-01

3 Answers 3

6

Putting all that into a superscript (especially with the exponential notation suggested by others) is hard on the eyes. How about:

$f_{3n-3k} = f_{3n}(*(DS)^k) = f_{3n}(*SS(DS)^k) + f_{3n}(*D(DS)^k) + f_{3n}(*(DS)^{k+1})$

etc. Here * represents any sequence (so the argument in parentheses is not the end of the sequence, it's the whole sequence).

  • 2
    Agreed. I would even write the left-hand side as $f_{3n-3k}(*)$.2011-03-01
4

I must say that I don't find your $n \cdot seq$ easy to read, and it can appear ambiguous. I'd be inclined to borrow from automata theory and write e.g. $SSDSDSDSDS$ as $S^2(DS)^4$.

I would be inclined to help the lazy reader by also reminding him with the notation that you're talking about the end of sequences, so $\ldots S^2(DS)^4$.

I'm not sure how aesthetic this is when superscripted, but you can see for yourself: $f_{3n}^{\ldots S^2(DS)^4}$

  • 2
    @Milcak: You still get ambiguity when writing $(3DS)$. Does that mean $DDDS$ or $DSDSDS$?2011-03-01
0

Since the topic relates to ordered partitions of n, I would try to dovetail with existing nomenclature for ordered partitions. In particular, I suggest using 2 instead of D and 1 instead of S.

  • 0
    This would not be as clear for combinatorial proofs. Dominoes and squares are magic. $1$'s and $2$'s are not (so much). :)2011-03-01