# Permutations of a sequence

"Given a set $\{1,\ 2,\ 3,\ 4\}$, how many sequences with a length of $4$ with entries from this set have exactly one entry equal to $1$?"

Here is my work so far:
$$X = \left\{\text{sequences with length 4 from}\ \{1, 2, 3, 4\}\ \text{with exactly one entry equal to 1}\right\}$$ $$Y = \left\{\text{permutations of length 4 from}\ \{1, 2, 3, 4\}\right\}$$

By definition, $|Y| = 4\times 4\times 4\times4 = 256$.

Where do I go from here? Should I find $|X|$ as well? I think (by intuition, I haven't checked) that I need to find $|X \cap Y|$ in order to solve this problem. Is this true?

-
What do you mean when you say "By definition, $|Y|=\cdots=256$"? Seeing as $|X|$ is the answer to your problem (by your own definition), why did you define $Y$? –  wj32 Oct 10 '12 at 3:40
The cardinality of Y is 256, is it not? That is, 4*4*4*4 = 4 different ways to put a number in 4 different spots. –  user41419 Oct 10 '12 at 3:41
There are $4!=24$ permutations of the set $\{1,2,3,4\}$. You must be thinking of the number of ways to create a length 4 string from 4 possible letters. –  wj32 Oct 10 '12 at 3:44
Oh, sorry. I'm new to this, so the terminology is also new to me. What you said was what I meant, actually. –  user41419 Oct 10 '12 at 3:45

## 2 Answers

Let’s straighten out your terminology first: permutations of $\{1,2,3,4\}$ are automatically of length $4$, and there are $4!$ of them, not $4^4$; there are $4^4$ $4$-term sequences of elements of the set $\{1,2,3,4\}$.

You want nothing to do with permutations of $\{1,2,3,4\}$, and you certainly need to find $|X|$: that’s what the question asks for! To do this, note that each $4$-term sequence in $X$ can be constructed by deciding first which term of the sequence is to be the $1$ and then what members of $\{2,3,4\}$ are to be assigned to the other terms of the sequence. There are $4$ ways to choose the term that’s to be $1$. Once that’s settled, each of the other terms can be given any of $3$ values, $2,3$, or $4$, so it takes $3$ $3$-way choices to pin down the rest of the sequence. Thus, we end up with $4\cdot3\cdot3\cdot3=108$ possible sequences.

-
Thank you for the clarification! I'm new to this, so I'm still sorting out the terminology. Your explanation makes this seem much easier than I had first thought! –  user41419 Oct 10 '12 at 3:52
@user41419: You’re welcome! Elementary combinatorics problems range from quite easy, like this one, to fiendishly difficult, but if you’re just starting, you’ll probably find that most of them will succumb fairly readily if you break them down into things that you can count easily, as I did here. –  Brian M. Scott Oct 10 '12 at 3:55

The $1$ can be in any one of $4$ places. For each placement of the $1$, there are $3^3$ ways to fill in the rest of the entries.

Note that the problem did not say that the other entries are distinct. It said only that they are not $1$. So for example $4143$ is one of our sequences.

-