6
$\begingroup$

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!

  • 0
    @yunone: Yes, and I also realized that I should have edited my comment so as to say $x_i \neq x_j \Longleftrightarrow i \neq j$, but I can't anymore.2011-02-23

1 Answers 1

2

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)!}. $

  • 0
    Oh, I got it! Thanks for exposing it.2011-02-23