Total Possible Combinations Of Mostly Unique Sets

Question

Given X sets of N numbers if at least one number of each set must be unique what is the total number of possible of combinations? First set starts at 1, each sequential number is multiplied by 2 and each sequential set is 10*previous set.

Example, 3 sets, 5 numbers. X=3, N=5

Set 1 [1,2,4,8,16]

Set 2 [10,20,40,80,160]

Set 3 [100,200,400,800,1600]

Example combinations.

[1,2,4,8,160] [1,2,40,80,160] [1,200,40,8,1600]

good(at least one non matching number)

[1,2,4,8,160] [10,20,40,80,160]

bad(already generated/0 non matching numbers)

In plain English, at least one of the numbers must be different than any other set. I need to know what the formula would be to determine how many possible sets there are matching this criteria. I know that X=5 & N=5 = 2592.

I'm new to learning about combinatorics and I'm sure I'll understand how to figure this out eventually but I need an answer sooner rather than later so any help is appreciated, especially a specific formula I can use. Thank you! :)

Answer 1

Note: I am assuming all X sets are mutually exclusive as in the example. This math only works for X mutually exclusive sets.

(x)(x+1)(x+2)(x+3)(x+4)/n! = 126 - 5 identies sets = 121 for x = 5 && n = 5

Let's first start with x = 5 n = 1

1

2

3

4

5

Are all possibilities so the formula is 5/1! = 5 but all 5 are idendities so 0 unique sets

The formula expands are you go up in n so x = 5 n = 2 is

(x)(x+1)/2! = 15

55 54 53 52 51 44 43 42 41 33 32 31 22 21 11 = 15 members. - 5 identities = 10 unique members

There is no closed form formula but you generate the formula based on the pattern

for x =5 and n = 3

x(x+1)(x+2)/3! = 35 -5 = 30 unique members

this works for any x and n, just see there are n terms in numerator

for x =3 and n = 5

(x)(x+1)(x+2)(x+3)(x+4)/5!= 168 - 5 = 163 unique members ( we dont count 11111 22222 33333 44444 55555)

How to count these sets?

Lets represent a unique set.

22345 - means we first pick from set 2, then set 2 again then set 3 then set 4 then set 5

But this is a problem because

54322 is the same set as before just different ordering

So count like this

54322 --> every digit must be >= to the one after it. This makes sure you only count each representation once

5

4

3

2

1

55 44 33 22 11

54 43 32 21

53 42 31

52 41

51

From there you can get the basis for understanding how the formula works