Suppose we have $k$ natural numbers such as $n_1 \leq n_2 \leq n_3 \leq \ldots \leq n_k$. Is there any encoding algorithm that alllow to encode this numbers to one number with $\log_2{n_k + k \choose k}$ bits?
I tried to represent these numbers as all possible binary strings of length $n_k + k$ with k separators. Then we would have $n_k +k \choose k$ variants and for each such variant match the ordinal number. This looks rather unfortunate since we need to store a bunch of combinations of elements for only one set of numbers
Is there any better way to fit this entire set of numbers into a binary string of size $\log_2{n_k + k \choose k}$?
I will assume that natural numbers include zero, so $0\le n_1\le \dots \le n_k$. If you intended the naturals to start at one, you will need to subtract $1$ from each list item first.
First, transform your weakly increasing list $(n_1,\dots,n_k)$ into a strictly increasing list $(m_1,\dots,m_k)$, where $$ m_i=n_i+(i-1) $$ You can uniquely recover the $n$-list from the $m$-list as well. Finally, you can use use combinadics to encode the $m$-list as a number between $0$ and $\binom{m_k+1}{k}-1$. The corresponding number is $$ \binom{m_1}1+\binom{m_2}2+\dots+\binom{m_k}{k} $$ To reverse the encoding, you are given a nonnegative integer $x$, and need to find $(m_1,m_2,\dots,m_k)$. This is done as follows:
$m_k$ is the largest integer such that $\binom{m_k}k\le x.$
$m_{k-1}$ is the largest integer such that $\binom{m_{k-1}}{k-1}\le x-\binom{m_k}k.$
$m_{k-2}$ is the largest integer such that $\binom{m_{k-2}}{k-2}\le x-\binom{m_k}k-\binom{m_{k-1}}{k-1}.$
etc.