Suppose you have a set of 4 elements {A,B,C,D}, but without specifying their order. Now, if you want to specify which precedes which, that would mean you need to provide more information.

But at the same time, writing down the ordered list {B,C,A,D} doesn't take more text. That's probably because order is implicit when writing down things, even when I say that {A,B,C,D} is unordered, the way I write it down has order, I just tell you to ignore it.

So which is true? Does order carry additional information, and if so, why don't ordered lists take more text to describe than unordered ones?

-
See How to define the entropy of a list of numbers? -- perhaps not exactly a duplicate but close. – joriki Jan 7 '12 at 14:45
my address is $\{3412\}$ $\{ifstr\}$ street – yoyo Jan 7 '12 at 15:42

Precisely, you can order $n$ elements in $n!$ different ways, so say you got $4$ elements ${A,B,C,D}$ with no order defined. When writing them down in a particular order, the order itself defines a number from $0$ to $4! = 23$, so you basically stored $log_2 24$ additional bits.

Now when you write down unordered elements, you'll of course need to choose some order (which is "waste" information in that moment). But if you choose a particular order, you can use this to store additional information in the same message. This is actually a neat trick in steganography, i.e. sending hidden messages, in data where order is of no importance (HTML attribues are great!).

On the other hand, if order does matter, you cannot afterwards rearrange the items to store extra information or the original order is lost.

-