1
$\begingroup$

Problem. A "passphrase" consists of 10 distinct characters, chosen from the set $S = \{A,B,C,D,E,a,b,c,d,e\}$ (clearly, then, each letter in $S$ must appear exactly once in every possible passphrase). How many possible unique passphrases are there such that the letter $A$ preceds the first appearance of any lowercase letter?

Solution. I'm not quite sure how to approach this. Here's how I think of it:

We're effectively being asked "in how many permutations of $S = \{A,B,C,D,E,a,b,c,d,e\}$ does $A$ come before all lowercase letters?"

A passphrase looks something like this: _ _ _ _ A _ _ _ _ _ .

There are $10$ possible "locations" of $A$. Give each location an index, and call the location of $A$ by index $i$.

The preceding spaces may be filled in any of $_5P_{i-1}$ ways, and the spaces following $A$ may be filled in any of $_{10 - (i-1)}P_{10 - i}$ ways (?).

I'm not sure where to go from here. I feel as though there must be a simpler way to re-frame the problem.

$\endgroup$

2 Answers 2

7
$\begingroup$

Alternative approach.

The chance that the 1st element in $\{A,a,b,c,d,e\}$ to appear in a string is $A$ is $(1/6).$

Therefore, the number of satisfying strings must be
$\displaystyle \frac{10!}{6}.$


Addendum
Response to PGTK's comment question.
The answer that I gave is actually an abbreviated version of the following, more long-winded analysis:

Let Constraint-1 represent the constraint that within a passphrase, $A$ must precede each of $\{a,b,c,d,e\}$.

If Constraint-1 is ignored, there are $(10!)$ possible (unique) passphrases.

I claim that of these $(10!)$ passphrases, exactly $(1/6)$ of them will satisfy Constraint-1.

$\underline{\text{Proof of Claim}}$
Partition the set of $(10!)$ passphrases into $\displaystyle \frac{10!}{6!}$ different subsets, based on which of the $(10)$ positions are assigned to each of $B,C,D,E$. Note that:

  • Each of the possible passphrases will belong to exactly one of the $\displaystyle \frac{10!}{6!}$ subsets.

Now, the question is begged, within a specific subset of passphrases, what fraction of the elements in this subset satisfy Constraint-1?

First of all, let subset $S_1$ denote the subset of passphrases whose first $(4)$ characters are $B,C,D,E$, in that order. What fraction of the passphrases in $S_1$ will satisfy Constraint-1?

Every passphrase in $S_1$, will have the elements $A,a,b,c,d,e$ in some order in positions $(5)$ through $(10)$ (inclusive). Clearly a passphrase that is in $S_1$ will satisfy Constraint-1 if and only if the character $A$ occurs specifically in position $(5)$. By symmetry, exactly $(1/6)$ of the passphrases in $S_1$ will have the character $A$ occurring in position $(5)$ rather than any of the positions $(6), (7), (8), (9),$ or $(10)$.

Therefore, focusing only on the subset $S_1$, exactly $(1/6)$ of the passphrases in $S_1$ will satisfy Constraint-1.

Now, for $\displaystyle k \in \left\{ ~1, 2, 3, \cdots, \frac{10!}{6!} ~\right\}$, consider the subset $S_k$ of passphrases, that correspond to some specific fixed positions from $(1)$ through $(10)$ being assigned to each of $B,C,D,E$.

This means that with respect to subset $S_k$, there are exactly $6$ fixed positions such that for each passphrase in $S_k$, none of the characters $B,C,D,E$ are assigned to any of these $6$ positions.

With focusing staying in subset $S_k$, let $p_1, p_2, p_3, p_4, p_5, p_6$ denote these $6$ positions, in ascending order. That is, the number assigned to position $p_1$ is smaller than any of the numbers assigned to the positions $p_2, p_3, p_4, p_5,$ or $p_6$.

As $S_k$ is defined, for each passphrase in $S_k$, the characters $A, a, b, c, d, e$ will be assigned to the positions $p_1, p_2, p_3, p_4, p_5, p_6$ in some order. How many of the passphrases in subset $S_k$ will satisfy Constraint-1?

Clearly, in $S_k$, Constraint-1 will be satisfied if and only if the character $A$ is assigned to position $p_1$. Further, by symmetry, exactly $(1/6)$ of the passphrases in subset $S_k$ will have the character $A$ assigned to position $p_1$, rather than any of other positions $p_2, p_3, p_4, p_5,$ or $p_6$.

Note that the above analysis applies to any subset $S_k$, where $k$ is any element in $\displaystyle \left\{ ~1, 2, 3, \cdots, \frac{10!}{6!} ~\right\}.$

So, in each subset of passphrases, Constraint-1 is satisfied by exactly $(1/6)$ of the passphrases in that subset. Therefore, Constraint-1 is satisfied by exactly $(1/6)$ of all of the possible passphrases.

$\endgroup$
3
  • $\begingroup$ making use of probability... clever guy ! +1 $\endgroup$ Commented Sep 16, 2021 at 20:21
  • $\begingroup$ I am baffled. Right from start, this answer looks wrong to me because you refer to {A, a, b, c, d, e} with merely 6 elements! But undeniably, this ISN'T the original set S in the problem that has 10 elements! So how can you simply work with {A, b, c, d, e} and ignore S? $\endgroup$
    – user53259
    Commented Jan 3, 2022 at 6:55
  • $\begingroup$ @PGTK See the just added Addendum to my answer. $\endgroup$ Commented Jan 3, 2022 at 13:28
4
$\begingroup$

There are $10$ ways to place the B, $9$ ways to place the C, $8$ ways to place the $D$, and $7$ ways to place the E. The A must go in the first of the remaining six locations. The five lowercase letters can be arranged in the remaining five positions in $5!$ ways. Hence, there are $$10 \cdot 9 \cdot 8 \cdot 7 \cdot 5!$$ arrangements in which the A precedes all five lowercase letters.

$\endgroup$
4
  • $\begingroup$ very nice done +1 $\endgroup$ Commented Sep 16, 2021 at 20:11
  • $\begingroup$ I am baffled. Can you assist please? A can antecede the B, C, D, E. One example is {A, a, b, c, d, e, B, C, D, E}. Here A is first! Thus 10 ways to place A! Why did you start with "10 ways to place the B [...] 7 ways to place the E"? $\endgroup$
    – user53259
    Commented Jan 3, 2022 at 6:57
  • $\begingroup$ @PGTK The only requirement is that $A$ precede each of the five lowercase letters. I chose to place $B$, $C$, $D$, and $E$ before I placed the $A$ since that forces $A$ to go in the first open position. I then arranged the vowels in the remaining five positions. Notice that we do not have ten ways to place the $A$ since it must precede each of the five lowercase letters. $\endgroup$ Commented Jan 3, 2022 at 16:24
  • $\begingroup$ @PGTK Another way to approach this problem is to first select six positions for the $A$ and the five lowercase letters. The $A$ must go in the first of those six selected positions. The five lowercase letters can be arranged in the remaining five selected positions in $5!$ ways. The four other uppercase letters can be arranged in the remaining four positions in $4!$ ways. Hence, there are $\binom{10}{6}5!4!$ admissible arrangements. $\endgroup$ Commented Jan 3, 2022 at 16:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .