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
    What is $\#A$? Is it the number of elements in the set $A$?2011-02-23
  • 0
    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.2011-02-23
  • 0
    @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?2011-02-23
  • 0
    @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?2011-02-23
  • 0
    @Maria: I have usually seen $|A|$, but I think some books use $\#A$. I just wanted to make sure.2011-02-23
  • 0
    @Maria: I don't see any problem with this answer, as yunone said.2011-02-23
  • 0
    @Marla, I agree with Ross and your teacher, the answer seems perfectly fine. It's a repeated application of the [rule of product](http://en.wikipedia.org/wiki/Rule_of_product) since you have $n$ ways to choose each of the $k$ entries. Maybe citing that principle will make it seem rigorous enough.2011-02-23
  • 0
    @Ross Millikan, @yunone: I guess we can accept it as it is, but since I would like to address some other results, I thought it would be best to start from the easier, just to get into the mindset, if I may say that. For example, how can we prove that $\#\{x_1, \ldots, x_k) : x_i \in A, i \in \{1, \ldots, k\}, x_i \neq x_j, j \in \{1, \ldots, k\}\} = \frac{n!}{(n - k)!}$?2011-02-23
  • 0
    @Marla, just to clarify, are you asking for the number of $(x_1,\dots, x_k)$ such that no two entries are the same? Is so, you may want to edit the main question, so that more people see your new question.2011-02-23
  • 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