Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to design an algorithm to generate something that I don't know how exactly to call! Ok, I'm not a mathematician, I'm studying computer science and thought this would be a great moment to use some recursive algorithms.

But I'm not asking how to do it, what I really want to know is what's the name of this so I can read more about.


Basically, it would be a kind of permutation, but I'm not sure:

Given a set of $\{a, b, c\}$ generate conjuncts of 3 elements, which came from the set. Example:

aaa | bbb | ccc | aab | aba | baa | bba | bab | abb | ... | aca | ... | acc | ... | abc | acb | cbb | ...

These are 27 in total, as I have three elements, each one from a set of another 3:

_ _ _ -> $3 \cdot 3 \cdot 3$ -> $27$

Similarly, given a set of $\{0, 1\}$ generating a 8 element conjunct would end in a list of zero to 255, in binary.

So, how is this called formally?

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

In technical mathematical terms, these are called tuples (over sets of size $n$). They are ordered collections of length $k$ with replacement (the latter meaning you can repeat an element that has already appeared in the list). The name comes from things like 'triple' which is an ordered collection of length 3.

The set $\{a,b,c\}$ is of size $n=3$, and you are showing all ways of listing a sequence of length $k=3$. So one object is $aab$ and another is $aba$ (order matters, and you can repeat elements.

For your second example, your list is of length 8, and each item is either 0 or 1.

And you've found how to count the total ways of assembling such a compound object $n^k$, because each item has $n$ ways of choosing it, and there are $k$ positions, for $n\cdot n\cdot ...\cdot n$ for $k$ times.

A permutation technically refers to an ordered collection without replacement. Or even more technically, a $k$-permutation is one of length $k$ from a set of size $n$ (how many of these are there?), and a plain old permutation is really an $n$-permutation, a permutation of length $n$ from a set of size $n$ (how many of -these- are there?) and you should be able to convince yourself why there are no $n+1$- permutations.

Another possibility is an unordered collection (of size $k$) without replacement from a set of size $n$. This is called a combination (or subset). You can figure out how many of these there are from the number of $k$-permutations.

The missing part of the square are called multisets (unordered with replacement). The terminology of 'replacement' is in reference to a balls and bins model; I find it easier to think instead of 'repetition' allowed or not.

share|improve this answer
    
Thanks a lot for your comprehensive answer. Math is such a beautiful thing! Tuples is a new term for me. Most of the others I started to remember from school, but it was really useful to read this here as my primary education was not in english, and I'm now having to relearn many terms. If I may answer the questions, the first for the $k$-permutation would be $\frac{n!}{(n-k)!}$, or something like that, right? The $n$-permutation is easy: $n!$. Now, I'm not quite sure if I can convince myself why there are no $n+1$-permutations. Does $n+1$ relates to the set, without sufficient elements? –  sidyll Mar 30 '11 at 12:17
    
@sidyll: The idea 'without sufficient elements' is right. Suppose you have an $n$-permutation and you want to put one more element at the end (for length $n+1$), but you can't repeat any that you've used already? You've used all $n$ already so there are no more, so it is impossible to do. –  Mitch Mar 30 '11 at 13:52
    
@sidyll: Yes, $\frac{n!}{(n-k)!}$ is right. For combinations, divide this by $k!$ (because you're removing all the ways of ordering those $k!$ elements. –  Mitch Mar 30 '11 at 13:53
    
@sidyll: mathematics is its own foreign language, so no matter how evocative or metaphorical a technical term may sound, one has to learn what it really technically means. –  Mitch Mar 30 '11 at 13:55
add comment

These are called "tuples", "3-tuples", or "triples". They are called arrays or vectors in programming, and "strings of length 3 from the alphabet {a,b,c}" in computer science (as in a formal language).

They are often denoted as: $$\{ a,b,c \}^3 = \{ aaa, aab, aac, aba, abb, abc, aca, acb, acc, \dots, ccc \}$$

Wikipedia has an article on them.

share|improve this answer
    
+1, thanks for your answer sir, and for providing the useful links. –  sidyll Mar 30 '11 at 12:20
add comment

The above can rightly be called the Permutations, which is basically the no. of ways of arranging the elements of a set in a specified manner specification refers to:

1) No. of positions to fill (like in n-tuple, there're n positions to fill). 2) Total no. of elements that we can fill the positions with (i.e. Cardinality of set of elements) 3)Whether we're allowed to repeat the elements, once we already have used it to fill a position.

Yours is the case where we're allowed to repeat the elements, so that :

**For the first case** :- 

1) You can fill the first position in 3 ways (i.e. with a or b or c). 2) Then 2nd position in 3 ways (repetition is allowed ) 3) 3rd too in 3 ways HENCE making total no. of ways 3 * 3 * 3 = 27 (3^3)

share|improve this answer
add comment

Your conjuncts are called tuples or sequences. (See other names in @Jack Schmidt:'s answer.) The set of tuples, where each element of a tuple is taken from some set $B$ and a length of the tuple is always $n$, is written via the $n$-fold Cartesian product $B\times\dots\times B$. It is essentially the same as a set of functions $N\to B$, where $N$ is some set such that $card(N)=n$. Somebody works with functions instead of tuples.

The number of functions $N\to B$ is $card(B)^{card(N)}$, $3^3=27, 2^8=256$ in your examples. In your first example any conjunct is just a function $\{0,1,2\} \to \{a,b,c\}$.

$card(A)$ is a number of elements in the set $A$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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