Permutation representation of group different definitions? I'm just starting a course on representation theory and I'm confused by this definition of permutation representation:
Given a finite set $X$ and a field $k$, we can form the vector space $kX$ of functions $X$ to $k$, with pointwise operations. Then an action of a group $G$ on $X$ induces a representation $\rho:G\rightarrow \text{Aut}(kX)$ via $\rho(g)(f)(x)=f(g^{-1}x),$ for $g\in G, f\in kX, x\in X.$ This is the permutation representation of $G$ on $X$.
In previous courses, given an action of a group $G$ on a finite set $X$, we've seen a homomorphism $G\rightarrow \text{Sym}(X)$ is induced, and called this the permutation representation of $G$.
The setup seems entirely too similar for these notions to be unrelated, but I don't understand what the connection between the two is. Also, is there a good reason for calling the $G\rightarrow \text{Sym}(X)$ homomorphism a representation, even though we have no vector space structure in this case?
Thanks.
 A: You're entirely right in noticing this connection, and this is one place (of many) where some category theory makes the reason for the connection obvious.
We can represent a group $G$ as a category with one object (see here, for instance), call it $BG$. When we do this, a group action $G \curvearrowright X$ is exactly a functor $\alpha : BG \to \mathsf{Set}$ with the unique object in $BG$ sent to $X$.
More generally, if $X$ is an object of a category $\mathcal{C}$, then an action of $G$ on $X$ is a functor $\alpha : BG \to \mathcal{C}$ where the unique object is sent to $X$. For example, this gives continuous actions or smooth actions, by taking $\mathcal{C}$ to be the category of topological or smooth spaces, respectively, or linear actions (which we usually call representations) by taking $\mathcal{C}$ to be a category of modules or vector spaces.
So now say we have an action of $G$ on a set $X$, that is, we have a functor $\alpha : BG \to \mathsf{Set}$. Recall there are also functors $\mathsf{Set} \to k\text{Vect}$ sending a set $X$ to a certain $k$ vector space!

*

*We can send a set $X$ to the vector space $k^X$ of functions $X \to k$, with pointwise operations. Notice this is contravariant (do you see why?)

*We can send a set $X$ to the vector space $kX$ whose basis is given by elements of $X$.
Notice this is covariant (again, do you see why?)

But now, since a group action (or a representation) is a functor out of $BG$, we can turn our action of $G$ on $X$ into an action of $G$ on $k^X$ (or $kX$): Compose the functors!
$$
BG^\text{op} \overset{\alpha^\text{op}}{\longrightarrow} \mathsf{Set}^\text{op} \overset{k^{-}}{\longrightarrow} k\text{Vect}
$$
$$
BG \overset{\alpha}{\longrightarrow} \mathsf{Set} \overset{k[-]}{\longrightarrow} k\text{Vect}
$$
Now, you're considering the first case. Notice, because $k^{-}$ is a contravariant functor that we had to take the opposite of our action $\alpha$ from $BG$ to $\mathsf{Set}$. As a quick exercise, you should convince yourself that this "opposite"-ness is the reason
$(gf)(x) = f(g^{-1}x)$.
We could also consider the second case, and for completeness, I'll say something about it.
The idea here is that each $x \in X$ is a basis element of $kX$. So each function $g \cdot - : X \to X$ extends linearly to a map on $kX$. Notice when we take this definition, because $k[-]$ is covariant, we don't have to worry about inverting $g$:
$$
g(x_1 + x_2) = gx_1 + gx_2
$$

As for why we call both of these things "representations", as I understand it, we historically thought of groups $G$ defined axiomatically as "abstract groups", and we used the word "representation" to indicate that we were representing an abstract group by something "concrete", like a group of symmetries of some object, a group of matrices, etc. This is why
the theorem that each $G$ embeds into a symmetric group is sometimes called
Cayley's Representation Theorem. Nowadays, though, we usually think of linear representations (that is, actions of $G$ on some module or vector space) when we think of representation theory, and so I believe this older terminology is falling out of fashion.

I hope this helps ^_^
A: I think I figured it out, in case anyone is interested in future.
The vector space $kX$ defined above has a basis $\{\delta_x:x\in X\},$ where $\delta_x(y)=\delta_{xy}.$ Now notice that with the representation $\rho$ defined above, we have $$\rho(g)\delta_x(y)=\delta_x(g^{-1}y)=\delta_{x,g^{-1}y}=\delta_{gx,y}=\delta_{gx}(y),$$ and hence $\rho(g)(\delta_x)=\delta_{gx}.$
With this in mind, we can see that each $g$ really does behave like a permutation of the elements of $X$, namely by its effect on the basis of $kX.$
