Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Number of combinations of bytes ordered by value

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?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading