Combinatory analysis between groups with specific rules

Question

Goal: Calculate the total number of combinations between n groups composed of n integer positive numbers following the rules:

-The combinations must have only one number of each group

-The combinations must have no repetitions of numbers

-Ther order of the numbers in the combination must be crescent, meaning that a number in the group ahead must always be greater.

Example:

Consider Groups G1 to G4 as follows:

G1 = {0,1,2,3}

G2 = {2,3,4,5}

G3 = {3,4,6,7}

G4 = {6,7,8,9}

A combination must be formed by any and only one number of each group following the rules above mentioned in the format K(g) = {G1(n), G2(n), G3(n), G4(n)}.

Thus:

K(g) = {0,2,3,6} is a valid combination;

K(g) = {2,2,3,6} is an INVALID combination since it repeats the same number from groups G1 and G2;

K(g) = {3,2,3,6} is an INVALID combination since it Both repeats the same number from groups G1 and G3, and also has a Lower number from G2, not following the crescent sequence.

Note: the numbers never repeat themselves inside the same group.

For few and small groups like these, it is quite possible to achive the total combinations manually, but i'm searching for any insight that makes it possible to calculate the total combinations for n groups with n numbers before generating the combinations.

To find all the combinations is not so hard with Excel, Excel/VBA, or any other tool, but in a scenario where the result would be Millions of combinations, i need to know this result in advance.

Math Formula (for noob, please), Excel Formula, VBA code (without nested loops), they're all welcome.

And the formula must be applicable in any other scenario which follows these rules.

Thanks in advance for any help.

Answer 1

You may want to make a directed acyclic graph out of those groups, with "initial node" $I$, pointing to all elements in $G_1$ as nodes, which then each point to all strictly bigger elements in $G_2$, which then each point to all strictly bigger elements in $G_3$ etc. - finally all elements in $G_4$ point to the "final node" $F$.

So in your example, the graph would have 18 vertices ($I, F$ and four vertices per each of the $G_i$'s, and, if I am not mistaken, some $45$ edges.

Now what you are asking for is the number of paths from $I$ to $F$. I've just very quickly looked it up and found e.g. https://cs.stackexchange.com/q/3078 from the Computer Science StackExchange site. Hope it helps.