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 byte₁ >= byte₂ >= ... >= byte_n – 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.

CodePudding user response：

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.