combinitorics: find number of possible vectors from n sets

[ciki57]

Hi! I'm new to this forums! I have the following problem:

We have n sets with k(n) elements each. Each set has unique elements, however some elements in the set A can be the same as some in set B. C(A,B) is the set of elements that A and B have in common.

Now we choose one element from each set to form a n-sized vector. All values in this vector must be unique. The first element of the vector must be from the first set, second from the second one and so on...

Question: How do i calculate the number of possible vectors?

Example:

set 1: ( 3 5 7 8 )
set 2: ( 1 7 8 )
set 3: ( 5 8 9 )
set 4: ( 6 )

n = 4;
k(1) = 4; k(2) = 3; k(3) = 3; k(4) = 1;
C(1,2) = { 8,7}; C(1,3) = {5,8}; C(1,4) = {}; C(2,3) = { 8 }; C(2,4) = {}, C(3,4) = {}

valid vector: [ 3, 1, 5, 6]
invalid vector: [ 5, 8, 5, 6] - two fives -> not good

number of possible vectors (solution of the problem) = 22

------------

I have found the solution if we only have two sets:

( k(1) - |C(1,2)| ) * k(2) + |C(1,2)| * ( k(2) - 1 )

However i need a general formula for n sets.

 

[pka]

Re: combinatorial questions.

We have n sets with k(n) elements each. Each set has unique elements, however some elements in the set A can be the same as some in set B.
C(A,B) is the set of elements that A and B have in common.
Now we choose one element from each set to form a n-sized vector. All values in this vector must be unique. Question: How do i calculate the number of possible vectors? Example:
set 1: ( 3 5 7 8 )
set 2: ( 1 7 8 )
set 3: ( 5 8 9 )
set 4: ( 6 )
valid vector: [ 3, 1, 5, 6]
number of possible vectors (solution of the problem) = 22
------------
I have found the solution if we only have two sets:
( k(1) - |C(1,2)| ) * k(2) + |C(1,2)| * ( k(2) - 1 )

I don’t agree with you answer for two sets. Here is why.
According to the rule: “Now we choose one element from each set to form a n-sized vector.” It does not say that the elements must be chosen in any order.
That is if [ 3, 1, 5, 6] is a valid vector then [1,3,6,5] is also a valid vector. It does not say that the first entry in the vector must come from the first set. Does it; is that what you mean to have written? In less you do mean that the entries vector are ordered by the numbering of the sets, then the answer you gave for two needs to be doubled.

 

[ciki57]

Sorry, I forgot to add that.

Yes, the first element from the vector must be from the first set, second from the second one and so on...

I have edited the original post to add that now.

 

[pka]

Yes, the first element from the vector must be from the first set, second from the second one and so on...

Actually, I feared that was the case! It may be hard to believe, but the other case is much, much easier to solve.

Your formula is correct for two sets. However, there is a much more compact way of expressing it. Let’s use some standard notation. If A is a set, the |A| stands for the number of elements in A. Now the formula for the number of two-vectors meeting the conditions of the problem is: \(\displaystyle \left| A \right|\left| B \right| - \left| {A \cap B} \right|\). That is, the product of the number in each set minus the number in the common part.

Now, for the bad news: To extend that idea is not a trivial matter. Using three sets, I have been able to construct counter-examples to any counting formula that I thought might work. Of course, a simple tree diagram will work but is not practical in larger cases. I intend to work on this.

 

[Denis]

Re: combinatorial questions.

set 1: ( 3 5 7 8 ) set 2: ( 1 7 8 ) set 3: ( 5 8 9 ) set 4: ( 6 )
n = 4;
k(1) = 4; k(2) = 3; k(3) = 3; k(4) = 1;
C(1,2) = { 8,7}; C(1,3) = {5,8}; C(1,4) = {}; C(2,3) = { 8 }; C(2,4) = {}, C(3,4) = {}

Perhaps writing 'em down in array fashion makes things "easier to see":

- - 3 - 5 - 7 8 -
1 - - - - - 7 8 -
- - - - 5 - - 8 9
- - - - - 6 - - -

IF all were different, then total vectors = k(1) * k(2) * k(3) * k(4) ; so 4*3*3*1 = 36

From that subtract the [bad guys]...

3156, 3186, 3196, 3756, 3786, 3796, 3856, [3886], 3896 : 1
[5156], 5186, 5196, [5756], 5786, 5796, [5856], [5886], 5896 : 4
7156, 7186, 7196, [7756], [7786], [7796], 7856, [7886], 7896 : 4
8156, [8186], 8196, 8756, [8786], 8796, [8856], [8886], [8896] : 5

Bad guys = 1+4+4+5 = 14; 36 - 14 = 22

So needed is a way to calculate the bad guys, which pka threatened to
let us know soon..... :wink: