# How to prove that if $\#A = n$, then $\#A^{k} = n^{k}$? And what about the formula $\frac{n!}{(n-k)!}$?

I'm starting a mini-course on Combinatorics and, although I can "see" the results, I'm having difficulties proving them.

For instance,

Being $\#A = n \in \mathbb{N}$, prove that $\#A^{k} = n^{k}$, for $k \in \mathbb{N}$.

I understand that $A^{k} = \{(x_1, \ldots, x_k) : x_i \in A\}$, and that we have $n \times n \ldots \times n$ ($k$ times) possible layouts for a sequence like $(x_1, \ldots, x_k)$, but I don't know what to use to prove the result.

Can you suggest some plan? If possible, could it be an advice that would give me traction to prove the following related results?

Thanks for the time of took to read my question. I highly appreciate it.

Update: Since this question is so straightforward (see comments), and was only presented with the intent of getting acquainted with the tools of the trade, I shall move on to another result I wish I can prove.

Prove that the number of elements in $\{(x_1, \ldots, x_k) : x_i \in A, i \in \{1, \ldots, k\}, x_i \neq x_j \Longleftrightarrow i \neq j, j \in \{1, \ldots, k\}\}$ is given by the formula $\frac{n!}{(n-k)!}$.

Thanks for your replies so far!

-
What is $\#A$? Is it the number of elements in the set $A$? – Ross Millikan Feb 23 '11 at 21:57
Maybe I'm unclear, but don't you have the answer already? You say you have $n\times n\cdots\times n$ ($k$ times), which is the same as saying there are $n^k$ possibilities for the $(x_1,\dots,x_k)$? Since each is different, and this encompasses all possibilities, that shows $\#A^k=n^k$ by the multiplication principle. – yunone Feb 23 '11 at 21:59
@Ross Millikan: Yes, with $\#A$ I mean the number of elements in $A$. Isn't that the common notation, or I have been wrong all this time? – Marla Feb 23 '11 at 22:00
@yunone: My teacher accepted the answer, but I can't help but feel this is a bit of a messy response. What is your opinion? – Marla Feb 23 '11 at 22:02
@Maria: I have usually seen $|A|$, but I think some books use $\#A$. I just wanted to make sure. – Ross Millikan Feb 23 '11 at 22:02

To address the second question, the set in question is the number of elements of $A^k$ such that no two entries are the same. Since $A$ has $n$ elements, you then have $n$ choices for the first entry, and $n-1$ choices for the second entry, as you cannot choose the element which you placed in the first entry. You then have $n-2$ choices for the third entry, $\dots$, $n-(k-1)=n-k+1$ choices for the the $k^{\text{th}}$ entry, for the same reasoning. But notice $$n(n-1)(n-2)\cdots(n-k+1)=\frac{n(n-1)\cdots(n-k+1)(n-k)\cdots 1}{(n-k)\cdots 1}=\frac{n!}{(n-k)!}.$$