Question about notation, language, and meaning in the context of combinatorics

Question

In my math class today, my teacher defined a function as follows:

A string on alphabet $[m]$ of length $n$ is a function:

$$ s: [n] \rightarrow [m] $$

To seque back to math from programming, what exactly is this function? It reads like it is taking an $n$-length input and outputting an $m$-length output.

I think some other specifications might be necessary: for instance, that the function is 1:1: for a number, $n$, there is one output, $s_n$.

Is this specification implied in the arrow notation? Or is it missing, where the arrow notation could just as easily imply that $s$ in fact, takes the whole of $[n]$ and produces a vector of length $[m]$...and I should fill in the gaps...

Also, in terms of programming, a string can be defined as the physical sequence after the mapping occurs...

Finally (and here is where all of my trouble stems from), the intent of this definition is that $s$ produce a tuple, or indexed item (indexed by $n$)...but the function signature indicates that it produces a $[m]$...

Honestly, I hate it when I wind up answering myself by rewriting the question.

---

---

$$ \begin{align} f(n) &= x, x \text{ is a valid index of m}\\ s(n) &= (m_{f(n)})_n\\ s(1) &= (m_{f(1)})_1\\ \end{align} $$

Where the tuple of information, $(n,m)$ is baked into the ordered list, $[m]$.

It's funny, but I have no idea why I was confused anymore...

Anyhow, the rule I've got is that with $s: [n] \rightarrow [m]$, 1:1ness is implied by default...for every 1 $n$, there is a single index number from $m$ placed next to $n$ by virtue of it being output in order with $n$...so the type signature of the output is actually the map, $\lbrace \lbrace 1,f(1) \rbrace, ... \rbrace$...

Answer 1

The elements of $[n]$ are naturally ordered, and this order gives a sequence $[s_{1}, \ldots, s_{n}]$, where each of the $s_{i} \in [m]$. In other words, you have $n$ symbols from $[m]$ laid out in a specified order.

It is sometimes convenient to think of this functionally, so the $i$th character of the string is given by $s(i) = s_{i}$. As a programmer, you can think of this as like an access function, to read a specified character from your string. You have that $[n]$ is the domain of the function (the positions that can be read), and $[m]$ is the codomain (the characters that might be in those positions).

Note that you are thinking of your "alphabet" as the numbers $1, \ldots, m$, because you really don't care what the symbols actually are, from a mathematical point of view, only how many symbols you are using.

Answer 2

Review your programming. A string of length $n$ can be represented as a function eating an input $i \in [n]$ and spitting out a single alphabet letter. For example, the string Hello can be represented using the following function (in pseudocode):

function hello(i):
  if i = 1 then return 'H'
  if i = 2 then return 'e'
  if i = 3 then return 'l'
  if i = 4 then return 'l'
  if i = 5 then return 'o'

The type of this function is exactly $\{1,2,3,4,5\} \to A$, where $A$ is any set containing all the letters in Hello.

Answer 3

A string of length $n$ is a finite sequence $s_1\cdots s_n$ with $s_i\in\{1,\ldots,m\}$ for each $i$. Writing $s(i)=s_i$ you get a map $s\colon\{1,\ldots,s\}\to\{1,\ldots,m\}$.

Answer 4

Maybe some concrete examples would be helpful. To run the code in this answer, you'll need to install the tensor package for Haskell.

---

Let's say my friend is moving to Florida, and they want to give me their phone number so we can stay in touch. What exactly do they need to give me?

To call my friend, all I need is a way to get the digits of my friend's phone number, one by one, so I can punch them into my phone. Accordingly, my friend gives me the following Haskell function.

import Data.Ordinal

genDigit :: Ten -> Nine
genDigit First = toOrdinal 2
genDigit (Succ First) = toOrdinal 3
genDigit (Succ (Succ First)) = toOrdinal 9
genDigit i = toOrdinal (p - q + r)
  where p = fromOrdinal (genDigit (toOrdinal ((fromOrdinal i) - 1)))
        q = fromOrdinal (genDigit (toOrdinal ((fromOrdinal i) - 2)))
        r = fromOrdinal (genDigit (toOrdinal ((fromOrdinal i) - 3)))`

When I want to call my friend, I call genDigit (toOrdinal 1) and punch the result into my phone. Then I call genDigit (toOrdinal 2) and punch that in. I keep punching in digits all the way up to genDigit (toOrdinal 10). Then, the phone connects me to my friend.

---

This is, admittedly, a really weird way to give someone a phone number. When your friend wants to give you their phone number, they probably give you a static memory device, like a piece of paper, with all the digits of the phone number written on it. In other words, when your friend wants to give you their phone number, you probably expect them to give you something like this:

digits = [2, 3, 9, 8, 2, 3, 9, 8, 2, 3]

I think this is what you mean when you say that "on a computer, a simple map, $s \colon [n] \rightarrow [m]$ is not a string until you allocate memory, evaluate the map and output the results of the mapping into the memory." When you ask your friend for their phone number, you expect to get a static block of memory, so you've decided that a phone number is a static block of memory.

To understand your teacher's way of speaking, I suggest you think in a different way: think of a phone number as a way to get digits to punch into your phone. From this point of view, you can't use the list digits as a phone number until you have a function to access it.

memDigit :: Ten -> Nine
memDigit i = toOrdinal (digits!!(fromOrdinal i - 1))

The function memDigit is the phone number; the list digits is just a resource used in defining the function. It's not hard to check that genDigit and memDigit give you the same output if you give them the same input. In other words, the Haskell functions genDigit and memDigit are two different expressions of the same abstract function $d \colon [10] \rightarrow [9]$.

---

As support for the point of view I'm suggesting, notice that when I use genDigit to contact my friend, the digits I'm dialing are never all written down in memory at the same time. In other words, I can use the function $d \colon [10] \rightarrow [9]$ to call my friend even if I never "allocate memory, evaluate the map and output the results of the mapping into the memory." To me, this is a pretty compelling reason to call the function $d$ a phone number even if I never write all its outputs down in one place.

A more practical argument for the "phone numbers as functions" point of view is that it generalizes nicely to situations where phone numbers are infinitely long—maybe my phone number is the infinite Fibonacci string, and yours is the Kolakoski sequence. I can't give you my phone number by writing it down on a piece of paper, but I can give it to you as a Haskell function fibDigit:

fibDigit :: Int -> Nine
fibDigit i = fibRecurse i [toOrdinal 1, toOrdinal 8] [toOrdinal 1]

fibRecurse :: Int -> [Nine] -> [Nine] -> Nine
fibRecurse i oneBack twoBack =
  if i <= length oneBack
    then oneBack!!(i - 1)
    else fibRecurse i (oneBack ++ twoBack) oneBack

When I call this a practical argument, I'm not joking. Haskell actually handles infinite lists by thinking of them as functions from $\mathbb{N}$ to the appropriate alphabet.