Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
show 5 more comments

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Oh, I got it! Thanks for exposing it. –  Marla Feb 23 '11 at 22:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.