As Henrick notes, permutation is a mathematical term for a function (or map; these two words are essentially synonymous in mathematics) that rearranges the elements of its domain so that exactly one input is mapped to each output.
In other words, a function $f$ from a set $S$ to $S$ is a permutation if and only if:
- no two inputs are mapped to the same output: $f(x) = f(y) \implies x = y$, and
- some input is mapped to every output: for all $y \in S$ there exists $x \in S$ such that $f(x) = y$.
For finite sets $S$, these two conditions are in fact equivalent: either one implies the other. This is easy to see using a counting argument: since the number of possible inputs equals the number of possible outputs, if any two inputs are mapped to the same output, there must be at least one output which is left without any corresponding input, and vice versa.
(In fact, some mathematicians prefer to reserve the word "permutation" only for the case where the domain is finite, and use the word "bijection" for the more general case described above; others treat the two words as more or less synonymous. Also, in some branches of mathematics, a permutation of an $n$-element set $S$ is commonly defined as a function from the set $\{1, 2, \dotsc, n\}$ to $S$, rather than from $S$ to $S$. However, these variations in usage don't really make any significant difference for most purposes, certainly not in cryptography.)
A useful mathematical property of permutations is that they are uniquely invertible: that is, given a permutation $f: S \to S$, there exists a unique permutation $g: S \to S$ such that $g(f(x)) = x$ for all $x \in S$.
The number of different permutations of an $n$-element set $S$ — that is, functions $f: S \to S$ which satisfy the definition above — is $k! = 1 \times 2 \times 3 \times \dotsb \times n$. A random permutation of a set $S$ is simply a function chosen uniformly at random from the set of these $n!$ possible permutations of $S$.
For cryptography, the significance of random permutations is that they are ideal ciphers for messages in the set $S$: the invertibility means that a message encrypted using the permutation $f$ can be decrypted using the corresponding inverse permutation $g$, and if $f$ is chosen randomly from the set of all permutations of $S$, the encryption $y = f(x)$ of any given message $x \in S$ will also be uniformly random, and thus provides no information about the original message $x$ to anyone who does not know $f$.
For small sets $S$, it's possible to examine all the possible permutations of $S$ one by one, but as the size of the set grows, the number of possible permutations quickly becomes truly enormous, and it becomes meaningful to speak of pseudorandom permutations. These are functions chosen from some smaller (but still very large) subset of the full set of permutations of $S$, but in such a way that there is (hopefully) no way for anyone to efficiently distinguish a permutation randomly chosen from the subset from a truly random permutation chosen from the full set of permutations of $S$.
A common type of pseudorandom permutations in cryptography are block ciphers. These are permutations of $b$-bit bitstrings, for some fixed number $b$, where the mapping of inputs to output is determined in some complicated way by a $k$-bit bitstring called the key. (Block ciphers are normally also constructed in such a way that the inverse permutation can also be easily computed based on the key.)
Typical values for $b$ and $k$ might be, say, 128 bits each. Now, clearly, the number of possible keys, $2^{128}$ (which generally equals the number of distinct permutations achievable using a given cipher algorithm, assuming that the cipher has no equivalent keys) is a vanishingly small fraction of the total number $(2^{128})! \approx 2^{2^{133}} \approx 2^{1.3 \times 10^{40}}$ of possible permutations of 128-bit bitstrings. However, it's still a huge number: if we had a billion ($10^9$) computers, each running at 1 THz with one instruction per cycle, it would still take 10 billion years for these computers just to execute $2^{128}$ instructions. Thus, it's completely impossible to tell if a permutation is chosen from a $2^{128}$-element subset or from the full set of $(2^{128})!$ permutations of $128$-bit bitstrings just by comparing it with each of the permutations in the subset in turn; and we hope that, for modern block ciphers like AES, there is also no other, significantly more efficient way to distinguish them from a random permutation than such a "brute force" attack.
OK, so that's what a permutation is and how they're used in cryptography. What about hashes? A hash function is a map from the infinite set of all bitstrings of any length to the finite set of bitstrings of length $b$ for some fixed number $b$. Thus, a hash cannot be a permutation (in any sense of the word): the set of possible inputs of a hash is strictly larger than the set of possible outputs, and thus it must map multiple inputs (in fact, infinitely many of them) to the same output.
In particular, this means that a hash function cannot be invertible, since, at least for some outputs, there's no way to tell which of the many possible equivalent inputs produced that output. Even if we restrict the inputs to bitstrings of some constant length $\ell$, this holds whenever $\ell > b$ (and is likely to hold even for somewhat shorter inputs).
Hashes are closely related to message authentication codes (MACs), which can, in some ways, be viewed as families of hash functions, where the choice of the specific function from the family is determined by some secret key — just like a block cipher is a family of permutations, from which one permutation of chosen by a key. In this sense, secure MACs can be seen as pseudorandom functions, which resemble truly randomly chosen functions from their respective input set to their output set in the same way as pseudorandom permutations resemble truly random permutations.
(Actually, the usual definition of a secure MAC doesn't really require complete pseudorandomness, but merely "unforgeability". However, any pseudorandom function from the set of all bitstrings to a set of fixed-length ones does satisfy the definition of a secure MAC, even if not all MACs are necessarily pseudorandom functions.)
However, what we normally require from cryptographic hash functions is both something more and something less than pseudorandomness. This is because hash functions differ from MACs in that they have no secret key, and so anyone can calculate the same hash for a given input equally well. In particular, this means that it's trivially easy to distinguish any given hash from a random function just by comparing the outputs to those of a known instance of the same hash function.
Instead, what we typically require from cryptographic hash functions is resistance to collision and preimage attacks. That is, even an attacker who knows how the hash function is calculated, and can calculate the hash for any input they want, should be practically unable to either:
- find an input that hashes to a given output value (first preimage resistance),
- find another input that hashes to the same output as a given input (second preimage resistance), or
- find any two inputs that hash to the same output (collision resistance).
So, no, a hash is never a permutation — and, other than that, the two concepts really don't have much to do with each other at all.
