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.