I can’t wrap my head around a mathematical question regarding combinations/permutations:
1 byte can store 256 possible combinations (2^8).
2 bytes can store 65536 possible combinations (2^16).
3 bytes can store 16777216 possible combinations (2^24).
This works only, because I have all possible combinations for each byte.
Given the requirement that the bytes need to be ordered by value – meaning byte1 >= byte2 >= … >= byten – how many combinations are there for 2, 3 or more bytes?
I’m pretty sure for 2 bytes there would be 32,896 combinations, which I got to with the following function:
(combinations * (combinations + 1)) / 2
I have currently no idea how to adapt this to 3 or more bytes.
>Solution :
Note that whether you impose byte1 ≥ byte2 ≥ ...
or byte1 > byte2 > ...
will change the result.
-
For
byte1 > byte2 > ...
, with 256 different possible bytes, there are (256 choose k) different possible ordered sequences of distinct k bytes. -
For
byte1 ≥ byte2 ≥ ...
, with 256 different possible bytes, there are (256 + k – 1 choose k) different possible ordered sequences of k bytes.
Here (n choose k) is the binomial coefficient.
The result for byte1 ≥ byte2 ≥ ...
can be proven using the stars and bars method.