0

I have 2 ordered sets: $\{A, B, C, D, E, F, G, H\}$ and $\{a, b, c, d, e, f, g, h\}$

I need to find all the ordered sets containing all $16$ of these elements, such that,

  1. The relative order of the elements in each of these two sets is preserved in the merged set (A must always occur before B and c before d, etc).
  2. A is the beginning element in all cases.

Eg: $\{A, B, C, D, E, F, G, H, a, b, c, d, e, f, g, h\}$

I tried finding them manually, but it's taking too long. Is there any Online resource that can simplify it for me because I'm working on the bigger picture and this is just a logic I'm experimenting on. Thanks.

Chiranjeev_Kumar
  • 3,061
  • 16
  • 30
Brent
  • 1

2 Answers2

1

Since A always comes first, we can leave it out of consideration. The rest consists in choosing $7$ out of the remaining $15$ slots for the capital letters, which can be done in $\binom{15}7=\frac{15!}{7!\cdot8!}=6435$ different ways. The order of the letters is then determined by your condition 1.

joriki
  • 238,052
0

The ordering is determined completely by which of the $16$ elements are capital letters. The first letter must be capital (since $A$ must begin the sequence), so the easiest way to generate all sequences is to start with a capital letter, and then generate $15$-letter sequences that contain $7$ capital letters.

Think of them as follows:

XxxxxxxxxXXXXXXX

XxxxxxxxXxXXXXXX

XxxxxxxxXXxXXXXX

$\ldots$

XXXXXXXXxxxxxxxx

There should be $\binom{15}{7} = 6435$ of them.

Brian Tung
  • 34,160