Calculating Number of Distinct x Tuples from a Set A

[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?

 

[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?

 

[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".

 

[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 {x₁, x₂} where x₁ and x₂ 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.

 

[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?

 

[Dr-NiKoN]

You know how to choose multiple groups at the same time?

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.

So, the correct answer is:

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

?

 

[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.

 

[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 m². Subtract from that the number of pairs with non-distinct terms: (1, 1), (2, 2), (3, 3), ..., (m, m) -this is just m. So (m² - 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.

 

[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?

 

[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)!.

 

[Dr-NiKoN]

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.

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:

%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 :)

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

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

 

[BicycleTree]

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

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.

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

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:

so, if you have:
(1, 2), (3, 4), (4, 5), (6, 7)

(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?

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

It will?

 

[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.

 

[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!.

 

[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.

 

[BicycleTree]

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

 

[BicycleTree]

I should be more detailed:

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

SO, now you have r the number of objects. r = 6.

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!.

From above, r = 6. Dividing by r! is dividing by 720. Now do you see?

 

[gptejms]

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)!.

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!

 

[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".

So the answer is:

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

?

 

[Dr-NiKoN]

So the answer is 16P2*14P2*12P2*10P2/4! or in other words 16P8/4!

$$\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?

 

[gptejms]

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".

So the answer is:

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

?

that's right.

 

[gptejms]

$$\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?

I am not sure of what you are saying here.The expression is $$\frac{n_P_r}{(r/2)!}$$ and this equals $$\frac{n!}{(n-r)!(r/2)!}$$

 

[Dr-NiKoN]

Thanks, I _finally_ get it :)

 

[BicycleTree]

Another way to write it is C(n, r) * P(r, r/2). But is this really what you want? You said that (1, 2), (3, 4), (4, 5), (6, 7) is one possible combination for your example problem, and you're talking about cryptographic functions--it would seem like an odd restriction to require that no element be used twice in the function. With respect to your cryptographic function, what are you trying to count?

 

[AKG]

As far as I can see, all you want to do is find the number of ordered pairs you can make from a set, then find the number of ways to make sets (combinations) of a certain number of pairs. Suppose we start with a set of n numbers. Then there are n² ordered pairs, and (n² C r) ways to make sets of r many ordered pairs (an ordered pair is a 2-tuple), where

$$(a\ C\ b) = \frac{a!}{b!(a - b)!}$$

and we'll assume n² > r. Let's actually phrase this problem as the problem of finding (N C r), where, for now, N is n². But do we want to include pairs like (2, 2)? If we have a pair (4, 5) are we allowed to have (5, 4)? If you clearly state the restrictions on what kinds of pairs we can choose, then we can figure out what N should be (maybe n² is inappropriate as I assume you don't want to count (1, 1) as a pair), and then it's a simple matter of finding (N C r), where, for example, r=7 in your first post.

 

[honestrosewater]

Eh, couldn't each symbol appear on the nonterminal or left hand side in at most one rule (for each set of rules)? Has that been acounted for? I couldn't find much about cryptosystems, but the example looks like just a string rewriting system.

 

[BicycleTree]

I don't know a lot about encrypting but I think normally if you're encrypting one set of numbers to another set of numbers (with just a correspondence between each number of the first set and each number of the second set, nothing fancy) you want a function that is one-to-one, and no other restrictions. The number of one-to-one functions from a set of size a to a set of size b is P(b, a).

I don't know anything about string rewriting systems but it sounds about right.

 

[Dr-NiKoN]

But do we want to include pairs like (2, 2)? If we have a pair (4, 5) are we allowed to have (5, 4)?

I have maybe explained this poorly, but let me try one last time.
Say you have a set:
A = {1 .. 10}

The cryptographic function has A as it's domain and codomain.

Now, to create these pairings we have to take elements 'out' of the set.
So, if our first pair is: (1, 2), then we are left with:
A = {3 .. 10 }

Think of it as a physical system containing 10 physical elements, if 1 is used in one pair, it can't be reused in another pair or again in the same pair.
so, (2, 2) can't be used and (2, 3), (2, 4) can't be used.

Imagine swapping bits in a byte-stream, 1 byte at a time.
A = {0 .. 7}
(0, 7), (1, 6), (2, 5), (3, 4)

So, if you have a byte that looks like this: 01010101
the 'encrypted' version would look like this: 10100101

The question is this:
How many ways can a byte be encrypted using this method.
The answer is:

$$\frac{8!}{4!(8 - 4)!}$$

Or so I believe.

Another example:
You have a computer keyboard where you can swap 2 keys with each other. There are a total of 26 characters you can change/swap: A = {a .. z}, and there is a restriction that you can only swap 20 keys.

How many different ways can you change the text "abcdefghijklmnopqrstuvwqyz", using this system?

The answer:

$$\frac{26!}{10!(26 - 20)!}$$

The general formula is:

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

 

[BicycleTree]

Actually, in your last example (with the keyboard) the formula does not apply. For example if I switch keys (q, w) then I can also switch keys (q, e) (or (w,e) depending on the notation) so that the top row starts with weqrty instead of qwerty.

 

[AKG]

Yes, it's a very simple thing which you're explaining very poorly. You're now saying that numbers cannot be repeated, but you gave us one example with (1,2), (3,4), (4, 5), (6,7) and the conversion that followed wasn't even right (you converted a string of 8 numbers into 9 somehow).

Now, it seems you want to know how many ways you can choose n ordered pairs from a set of N elements such that no two ordered pairs share any elements and such that no ordered pair contains a single repeated element. First, you want to find the number of ways of choosing 2n elements, that is C(N, 2n). Next, given 2n elements, you want to know the number of ways to make an ordered pair, that's P(2n, 2). Given the remaining 2n - 2 elements, you again want to find an ordered pair, so you multiply by P(2n - 2, 2). You'll get:

C(N, 2n) x P(2n, 2) x P(2n - 2, 2) x ... x P(2, 2)

But this will give you the number of arrangments of n ordered pairs, but you only want the combinations, so you divide by n!

This will be:

$$\left [\frac{N!}{(N - 2n)!(2n)!}\right ][(2n)(2n - 1)][(2n - 2)(2n - 3)]\dots [(2)(1)]\left [\frac{1}{n!}\right ] = \frac{N!}{n!(N - 2n)!}$$

This looks like your formula.

 

[AKG]

BicycleTree, you are not allowed to swap a key that has already been swapped.

This is what is meant when he said:

Think of it as a physical system containing 10 physical elements, if 1 is used in one pair, it can't be reused in another pair or again in the same pair.
so, (2, 2) can't be used and (2, 3), (2, 4) can't be used.

 

[BicycleTree]

Yeah, but that doesn't strictly apply to the keyboard example. It's not really important.