# Combinations, tuples

1. Apr 26, 2005

### Dr-NiKoN

Ok, given a set: A

How many distinct x tuples can be created using a subset of A?

Example:
|A| = 20

I want to know how many combinations of 7 tuples can be made from that set.

Example:

If A = {1 .. 20} three such combinations could be:

{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {13, 14}
{2, 1}, {4, 3}, {6, 5}, {8, 7}, {10, 9}, {12, 11}, {14, 13}
{20, 1}, {19, 2}, {18, 3}, {17, 4}, {16, 5}, {15, 6}, {14, 7}

The following is not another combination, since it's the same as the first one just with the tuples in a different order:
{13, 14}, {11, 12}, {9, 10}, {7, 8}, {5, 6}, {3, 4}, {1, 2}

My first tought was to just simply use: $$\frac{n!}{r!(n-r)!}$$ but that would include combinations like the last one. Where it's equivalent to the first, just with a different order.

How do I approach such a problem?

2. Apr 27, 2005

### honestrosewater

Do you mean {1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {13, 14} to be a 7-tuple or a set? Do you mean {1, 2} to be a 2-tuple or a set?

3. Apr 27, 2005

### Dr-NiKoN

Ok, let me give another example without "notation".
I have 20 numbers. I want combinations of 14 numbers that are ordered as tuples.
Some combinations
1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 1 4 3 6 5 8 7 10 9 12 11 14 13
20 1 19 2 18 3 17 4 16 5 15 6 14 7

The combination:
3 4 1 2 5 6 7 8 9 10 11 12 13 14

Is not a new combination, since it has the exact same tuples as the first example.
The first example consists of the following tuples:
(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14)
The last example consists of the following tuples:
(3, 4), (1, 2), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14)

The order of the "tuples" doesn't matter, so these are to be treated as the same "combination".

4. Apr 27, 2005

### honestrosewater

Okay, an n-tuple is a sequence (so order matters) of n terms, and its terms don't need to be distinct. So (1, 1), (1, 2), and (2, 1) are all distinct 2-tuples. If order doesn't matter and you want the terms to be distinct, then you want a set. For instance, {1, 2}, {2, 1}, and {1, 1, 2} are all the same set.
It seems like you want both the "tuples" and combinations to be sets, but you want some of them to be disjoint. I think this is what you want:
Let set A = {1, 2, 3, ..., m}. Define an n-combination in A to be a set of n disjoint sets {x1, x2} where x1 and x2 are distinct elements in A. You then want to know how many n-combinations in A there are, for some m and n. For your examples above, let m = 20 and n = 7. I don't know if I know how to solve this- I thought you were talking about tuples ;) But I'll think about it.
Edit: I should add that if you actually want to have some n-combinations, m > 2n (if m < 2n, you won't have enough m's to fill all the spots). So you may want to start with m = 2n and see how many n-combinations there are. Then try m = 2n + 1, etc. and look for a pattern.

Last edited: Apr 27, 2005
5. Apr 27, 2005

### BicycleTree

I think I understand what he's getting at. By "tuple" I think he means "ordered pair."

I assume no element of set A can be used more than once over all the ordered pairs (since that's what you have in your example).

You want to choose 7 groups of size 2 from a group of size 20. (You know how to choose multiple groups at the same time?) That will give you the number of ways to choose 7 different _sets_ of size 2 from A, where order within each set of size does _not_ matter (and, also, the order that the sets of size 2 come in does not matter). So now you want to compensate for that to make the order within each set of size 2 matter. There's a number you can multiply by to go from counting seven sets of size 2 to counting seven ordered pairs. What is it?

6. Apr 27, 2005

### Dr-NiKoN

Let's make it simpler.
|A| = 5
The total number of combinations of 2 groups of size 2 is:

$$\frac{5!}{(5-2)!}$$

This should basically be any permutation of 4 elements(2 ordered pairs) where order does matter. But, here the order of the ordered pairs themselves doesn't matter. So, this number is to big.

Since I have 2 ordered pairs, the number should be 2! to big.
2! = 2
permutations of 2 ordered pairs:
$$(x_1, x_2), (x_3, x_4)$$ AND $$(x_3, x_4), (x_1, x_2)$$

3! = 6
permutations of 3 ordered pairs:
$$(x_1, x_2), (x_3, x_4), (x_5, x_6)$$ AND $$(x_1, x_2), (x_5, x_6), (x_3, x_4)$$ AND $$(x_3, x_4), (x_1, x_2), (x_5, x_6)$$ AND $$(x_3, x_4), (x_5, x_6), (x_1, x_2)$$ AND $$(x_5, x_6), (x_1, x_2), (x_3, x_4)$$ AND $$(x_5, x_6), (x_3, x_4), (x_1, x_2)$$

For every r ordered pairs, the pairs can be rearranged r! ways which is just a permutation of the original order.
Thus,

$$\frac{n!}{(n-r)!}$$ is r! to large.

$$\frac{n!}{r!(n-r)!}$$

?

Last edited: Apr 27, 2005
7. Apr 27, 2005

### BicycleTree

I don't think that's right. However, your general idea should work.

Consider what you're planning on permuting: you have r pairs so you have r * 2 objects to permute initially.

8. Apr 27, 2005

### honestrosewater

Oh, sorry, I didn't notice the order. BicycleTree knows more about this than I do, so if what I say confuses you, just ignore it.
If your figures keep coming out too big, remember that the terms of an n-tuple (an ordered pair is a 2-tuple) don't need to be distinct: (1, 1) is an ordered pair. If your formula is for tuples, this may be what's throwing you off. Just requiring that there are no common terms between pairs won't correct this; It still allows for {(1, 1), (2, 2), (3, 3), ...}, and so on.
Say you want n pairs of m numbers. The total number of possible pairs is m2. Subtract from that the number of pairs with non-distinct terms: (1, 1), (2, 2), (3, 3), ..., (m, m) -this is just m. So (m2 - m) gives you the number of pairs with distinct terms. You can then try to figure out how many n-combinations of these pairs there are. If you don't know how to do this, try an example and look for patterns. Say m = 4 and n = 2. Draw an array.
$$\begin{array}{|c|c|c|c|}\hline 1\ 1&2\ 1&3\ 1&4\ 1\\\hline 1\ 2&2\ 2&3\ 2&4\ 2\\\hline 1\ 3&2\ 3&3\ 3&4\ 3\\\hline1\ 4&2\ 4&3\ 4&4\ 4\\\hline \end{array}$$
You've already eliminated the non-distinct terms, so cross them out. Now say the pair in column 1, row 2 is in the combination. Then no other pair in columns 1 or 2 or in rows 1 or 2 can be in the combination- cross them out. What is left? Does this hold for any column and row you select? Extend your array to m = 5. How many more options did you just add? Does this hold in general? And so on. I guess this is just general advice- if you don't know the general solution, try some examples. I think an array helps to see the patterns and arguments.

Last edited: Apr 27, 2005
9. Apr 28, 2005

### gptejms

Dr-Nikon,
Interesting problem.At first glance it looks like this:-
Say you have 16 elements and you want to know the no. of distinct 4 tuples.You can choose two elements out of 16 in 16C2 ways,another two from the remaining 14 in 14C2 ways,another two in 12C2 ways,last two in 10C2 ways.So the no. of ways seems to be:-
16C2 * 14C2 *12C2 * 10C2
But you have to divide the above by 4! because the order of the tuples is not important.So the answer is :-
16C2 * 14C2 *12C2 * 10C2/4!

Right?

10. Apr 28, 2005

### BicycleTree

gptejms, that was the way I suggested doing it, except you're not done because the order of the elements within the ordered pairs are important. You'd have to multiply that answer by a certain number. (By the way, call them ordered pairs, ok? "tuple" can refer to ordered lists with any number of elements; for example an example of a "4-tuple" is (1, 3, 8, 4))

Anyway, the way he found to do it is simpler to compute.

Nikon, here's a hint: referring to the beginning of your post, the number of ways to permute 4 objects out of 5 is 5!/(5-4)!.

11. Apr 28, 2005

### Dr-NiKoN

Ah, this may have caused some confusion. I haven't given you the full information.

I'll give a third example, that should have all the information:
Consider you have 9 numbers(1, 2, 3, 4, 5, 6, 7, 8, 9).

You have some sort of crypto-system that can hold 4 pairs of numbers. The crypto-system simple converts from 1 number to the other. So, think of any ordered pair as a machine that takes an integer and if the integer matches one of the first numbers in any pair, it converts that number to the other number in the pair.

Here it is in Perl:
Code (Text):

%crypto = {'1' => '2', '3' => '4',  '5' => '6',  '7' => '8'};

print "Insert number\n"
my $num = <STDIN>; chomp($num);

foreach my $digit (split //,$num) {

if ( %crypto{$digit} ) print$crypto{$digit}; else print$digit;
}

print "\n";
}
so, if you have:
(1, 2), (3, 4), (4, 5), (6, 7)

And give the crypto system the number:
123456789
It will encrypt it to:
2233557789

ie 1 becomes 2, 2 stays the same(no input that matches in the crypto system), 3 becomes 4 etc.

So, the members of the tuples will always be distinct, as all elements of the original set will be distinct.

$$\frac{n!}{(n-r)!}$$
gives me all combinations, but the order of the 'pairs' does matter.

$$\frac{n!}{r!(n-r)!}$$
gives me all combinations where the order of the pairs doesn't matter. Since r! is the number of different orders the pairs can be in?

I'm not sure if this is correct, but I can't really understand how it can be wrong :)

Originally there is n! objects to permute(you just disregard the last n-r objects)?

12. Apr 28, 2005

### BicycleTree

You disregard the last n-(r*2) objects. If you were disregarding the last n-r objects then you would be permuting r objects, but since there are r ordered pairs there are r*2 objects to permute, so you disregard (n-r*2) objects.

Well, if you are talking about sets of distinct ordered pairs so that no element of any ordered pair occurs more than once in all the ordered pairs in a given set, it is wrong.

However, your problem here seems to be different from how you originally presented:
(3, 4) and (4, 5) can BOTH be ordered pairs here? I thought each element of any ordered pair could not occur in the same or in any other ordered pair in the combination. Can you confirm that {(1, 2), (3, 4), (4, 5), (6, 7)} is a valid set of ordered pairs for your question?

It will?

Last edited: Apr 28, 2005
13. Apr 28, 2005

### BicycleTree

If you're just trying to find all possible distinct functions from {1, 2, ... , 9} to {1, 2, ... , 9}, the answer is 9^9.

14. Apr 28, 2005

### Dr-NiKoN

Hm, this isn't easy.
A set of numbers:
A = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Permutations of this set will look like:
1 2 3 4 5 6 7 8 9
2 1 3 4 5 6 7 8 9
2 1 4 3 5 6 7 8 9
8 9 1 2 3 4 5 6 7

Let's order these permutations like this:
$$(x_1, x_2), (x_3, x_4), (x_5, x_6), x_7, x_8, x_9$$

We consider the two elements $$x_1$$ and $$x_2$$ as a pair. The same for the rest, until we get to $$x_7$$, it's outside of the pairs we care about.

Here n = 9, r = 6, we disregard n - r objects = 9 - 6 = 3

The total number of permutations is n! or 9!. But, we only want information about r elements, so n! is to big by a factor of (n - r)!
thus:

$$\frac{n!}{(n-r)!}$$

Now, this will give us the number of permutiations of length r/6 we can create from a set of n/9 elements.

Now, for every permutation of r/6 elements(like 1 2 3 4 5 6), the sets can be rearranged in r! ways which we don't want.
Here are the ways we don't want from the mentioned permutation(don't worry about the delimiters, they are only there as visual hints):
1 2 | 3 4 | 5 6
1 2 | 5 6 | 3 4
3 4 | 5 6 | 1 2
3 4 | 1 2 | 5 6
5 6 | 1 2 | 3 4
5 6 | 3 4 | 1 2

All these include the same 'sets'(1,2:3,4:5,6).

So, the number:

$$\frac{n!}{(n-r)!}$$

is to large by r!.

15. Apr 28, 2005

### BicycleTree

Would you answer the question about whether those pairs you gave with the repeated element in them were valid for your problem?

But working within the system you have been working in, you need to nail one thing down:

either r is the number of pairs, or r is the number of elements within the pairs, but not both

You originally said r is the number of pairs.

You're going to have to have either r*2 in one place, or r/2 in the other place, depending on what you define it as. You can't have both places be r.

16. Apr 28, 2005

### BicycleTree

By the way, n!/(n-r)! is called P(n, r) (permuting r objects from n)

17. Apr 28, 2005

### BicycleTree

I should be more detailed:

SO, now you have r the number of objects. r = 6.
From above, r = 6. Dividing by r! is dividing by 720. Now do you see?

18. Apr 29, 2005

### gptejms

The order in the ordered pair is important you say----strange,but no problem.Use 16P2 instead of 16C2 etc..So the answer is 16P2*14P2*12P2*10P2/4! or in other words 16P8/4!

19. Apr 29, 2005

### Dr-NiKoN

Ah, yes :)

$$\frac{n!}{(n-r)!}$$

Is to big. But if you take away a factor of r!, you take away all permutations of elements. So, I need to take away $$(\frac{r}{2})!$$ to take away all permutations of "pairs".

$$\frac{n!}{ (\frac{r}{2})! (n-r)!}$$

?

20. Apr 29, 2005

### Dr-NiKoN

$$\binom{\binom{n}{r}}{\frac{r}{2}}$$

? :)
(I know the above isn't correct btw)

Is there any way to express this using nPr or nCr?

Last edited: Apr 29, 2005