problem in permutation question.

Question

Find the number of hexadecimal numbers containing at maximum 16 hexadecimal digits with all of the digits 0,1, and A present at least once? Give your answer as a hexadecimal number.

Answer 1

The answer is a little different depending on whether we assume that (a) the hex numbers are of full length $16$, with a front padding of $0$'s for small numbers or (b) the length is allowed to be variable, with only $0$ beginning with $0$.

We solve the problem under interpretation (a), and then the ugly modification for interpretation (b).

Interpretation (a): Instead of length $16$, it is visually easier to deal with length $n$. There are $16^n$ numbers in total. We must remove the bad numbers, in which one at least of $0$, $1$, or $A$ is missing. This wlll be done by the Method of Inclusion/Exclusion.

There are $15^n$ numbers with $0$ missing, and we have the same number with $1$ missing, and with $A$ missing. But if calculate the sum $15^n+15^n+15^n$, we will count twice the ones in which $0$ and $1$ are missing, also $0$ and $A$, also $1$ and $A$. There are $14^n$ of each kind. But if we subtract $3\cdot 14^n$, we will have subtracted one too many times the ones in which $0$, $1$, and $A$ are all missing. There are $13^n$ of these. So the total number of bads is $3\cdot 15^n-3\cdot 14^n+13^n$.

Interpretation (b): The length of a good number is $3$ to $16$. For any $k$, there are $(15)(16^{k-1})$ numbers. Again, we count the bads. There are two kinds of bads: (i) bads that start with $1$ or $A$ and (ii) all the others.

To count the bads that start with $1$ or $A$, there are $2$ choices for the first leftmost) digit. For every such choice, say first digit $1$, a bad is something that is missing one of $0$ or $A$ or both. There are $15^{k-1}$ that avoid $0$, $15^{k-1}$ that avoid $A$. Adding double counts the $14^{k-1}$ that avoid both. So the total of type (i) is $(2)(15^{k-1}+15^{k-1}-14^{k-1})$.

To count the bads that start with neither $1$ nor $A$, there are $13$ ways to start. For each of these ways, we count the bads in exactly the same way as we solved the (a) interpretation. We get a total of $(13)(3\cdot 15^{k-1}-3\cdot 14^{k-1}+13^{k-1})$.

Remembering that everything of length $1$ and $2$ is automatically bad, we get a full count of the bads by summing, $k=3$ to $n$. If we feel like it, we can simplify, since our sums are finite geometric series.

Answer 2

I would solve it with coupled recurrences. Let $S(n)$ be the number of strings of length $n$ with none of $0,1,A$, $T(n)$ the number of strings with (any number of) only one of $0,1,A$, $U(n)$ with two, and $V(n)$ with three. You want the sum from 3 to 16 of $V(n)$

The starting conditions are $S(1)=13, T(1)=3, U(1)=0, V(1)=0$ as there are thirteen one digit strings that are not $0,1,A$ and three that are. Then $S(n)=13S(n-1)$ because you can get an $S$ string one longer by adding any digit except $0,1,A$. What is the recurrence for $T(n)$. You can get a $T$ string by starting with a $T$ string and adding (what?) or by starting with an $S$ string and adding (what)? You can do these calculations easily in a spreadsheet.