1
$\begingroup$

Suppose I am given $m$ sequences of length $n$. Is there a term for the $m^n$ sequences that can be formed by taking one element at index $i$ from any of the original sequences? Or perhaps a term for the process of constructing such a set?

For example, given two source sequences, $\langle 1,2,3 \rangle$ and $\langle 10, 20, 30 \rangle$, the resulting sequences would be:

$$\langle 1, 2, 3\rangle , \langle 1, 2, 30\rangle , \langle 1, 20, 3\rangle , \langle 1, 20, 30\rangle , \langle 10, 2, 3\rangle , \langle 10, 2, 30\rangle , \langle 10, 20, 3\rangle , \langle 10, 20, 30\rangle$$

It seems like such a term would come from combinatorics. The only terms I know that are kind of in the same ballpark are "permutation" and "combination". fwiw I have looked at some combinatorics pages on the web, but haven't noticed anything promising yet. e.g. I've looked at every definition containing "sequence" at Douglas B. West's Glossary of Terms in Combinatorics. Maybe I'm just not noticing some other way of thinking about these sequences that would lead me to an obvious term.

EDIT: Here is more concrete way of illustrating the kind of sequence-construction relation that I have in mind:

I have $n$ "target" bins in a row that I'm trying to fill with one marble each. I have $m$ other rows of "source" bins of the same length. Each source bin contains a single, unique marble. To fill target bin $i$, I can use a single marble from the $i$th bin in any one of the source rows. I can't use the same marble twice.

(The uniqueness of marbles is just a way of capturing the idea that the combination of an index $i$ and a source row specifies a unique filler of a target bin at $i$. In practice the marbles could have numbers on them, and there's nothing in the story that implies that two bins couldn't have the same marble-number in them if, for example, source row $k$ has the number 14 on the marble in bin 22, while source row $k'$ has a 14 on the marble in bin 25, or in 22 as well. That is, any number could be in any position in the source sequences, but I can only fill target sequence location $i$ from location $i$ in some source sequence.)

$\endgroup$
  • $\begingroup$ Looks a bit like what you do when you take the determinant? ($A_{i,\sigma(i)}$ in Liebniz formula, row i being analogous to the index here ... maybe). Maybe you can find something in algebra. $\endgroup$ – Emil Jun 30 '17 at 7:27
  • $\begingroup$ I see the analogy, @Emil. Will think about that. $\endgroup$ – Mars Jun 30 '17 at 21:49
1
$\begingroup$

To construct them, you can form all the words of length $n$ out of the characters $\{1,2,3,\ldots,m\}$ The character at position $k$ tells you which sequence to take the $k^{\text{th}}$ character of. There are $m^n$ of them in the set. It feels a bit like a Cartesian product of the sequences, but I don't know a nice name for the set.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice representation. Hmm ... so let the $m$ sequences be row vectors, and stack them up as rows of an $m\times n$ matrix. Then we can think of the target sequences as the Cartesian product of elements of the column vectors. I'm thinking about this. (The matrix just provides a convenient way of expressing the transformation.) $\endgroup$ – Mars Jun 30 '17 at 21:42
0
$\begingroup$

Set of all permutations with repetitions.

Resulting sequence $i$-th element is formed using $i$-th element from $j$-th given sequence, so that $j_i$ can be equal $j_{i+1}$. This means that repetitions are allowed. See [wiki].1

Imagine, that you have no $m$ sequences of length $n$, but you have set of $m$ elements. You construct a resulting sequence of length $n$, so that elements in sequence can be included more than one time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks P.M.Z. But either I'm misunderstanding you, or you've misunderstood me. Either way, it may be my fault. I had trouble making the idea as clear as I'd wanted. Think of it this way: I have $n$ "target" bins in a row that I'm trying to fill with one marble each. I have $m$ other rows of "source" bins of the same length. Each source bin contains a single, unique marble. To fill target bin $i$, I can use a single marble from the $i$th bin in any one of the source rows. I can't use the same marble twice. Does that fit your understanding of what I was asking about? Thanks. $\endgroup$ – Mars Jun 30 '17 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.