<p>The numbers you are describing correspond to <a href="https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics" rel="nofollow">Dyck words</a>. Pt 2 of <a href="http://arxiv.org/pdf/1002.2625," rel="nofollow">Kasa 2009</a> gives a simple algorithm for enumerating them in lexicographic order. Its references should be helpful if you want to do any further reading.</p>

<p>As an aside (and be warned I'm half asleep as I write this, so it might be wrong), the wikipedia article notes that the number of Dyck words of length <code>2n</code> is the <code>n</code> th Catalan number, <code>C(n)</code>. You might want to find the smallest <code>n</code> such that <code>C(n)</code> is larger than the <code>k</code> you're looking for, and then enumerate Dyck words starting from <code>X^n Y^n</code>.</p>
Algorithm for finding kth binary number with certain properties
<p>Let's assume we will consider binary numbers which has length <code>2n</code> and <code>n</code> might be about <code>1000</code>. We are looking for <code>kth</code> number (k is limited by <code>10^9</code>) which has following properties:</p>

<ul>
<li>Amount of <code>1's</code> is equal to amount of <code>0's</code> what can be described as following: <code>#(1) = #(0)</code></li>
<li>Every prefix of this number has to contain atleast as much <code>0's</code> as <code>1's</code>. It might be easier to understand it after negating the sentence, which is: There is no prefix which would contain more <code>1's</code> than <code>0's</code>.</li>
</ul>

<p>And basically that's it.
So to make it clear let's do some example:
<code>n=2</code>, <code>k=2</code>
we have to take binary number of length <code>2n</code>:</p>

<pre><code>0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...
</code></pre>

<p>And now we have to find <code>2nd</code> number which fulfill those two requirements. So we see <code>0011</code> is the first one, and <code>0101</code> is second one.
If we change <code>k=3</code>, then answer doesn't exist since there are number which have same amount of opposite bits, but for <code>0110</code>, there is prefix <code>011</code> so number doesn't fulfill second constraint and same would be with all numbers which has <code>1</code> as most significant bit.</p>

<p><strong>So what I did so far to find algorithm?</strong></p>

<p>Well my first idea was to generate all possible bits settings, and check whether it has those two properties, but generate them all would take <code>O(2^(2n))</code> which is not an option for <code>n=1000</code>.</p>

<p>Additionally I realize there is no need to check all numbers which are smaller than <code>0011</code> for <code>n=2</code>, <code>000111</code> for <code>n=3</code>, and so on... frankly speaking those which half of most significant bits remains "untouched" because those numbers have no possibility to fulfill <code>#(1) = #(0)</code> condition. Using that I can reduce <code>n</code> by half, but it doesn't help much. Instead of 2 * forever I have forever running algorithm. It's still <code>O(2^n)</code> complexity, which is way too big.</p>

<p>Any idea for algorithm?</p>

<p><strong>Conclusion</strong></p>

<p>This text has been created as a result of my thoughts after reading Andy Jones post.</p>

<p>First of all I wouldn't post code I have used since it's point 6 in following document from Andy's post <a href="http://arxiv.org/pdf/1002.2625," rel="nofollow">Kasa 2009</a>. All you have to do is consider <code>nr</code> as that what I described as <code>k</code>. Unranking Dyck words algorithm, would help us find out answer much faster. However it has one bottleneck.</p>

<pre><code>while (k &gt;= C(n-i,j))
</code></pre>

<p>Considering that <code>n &lt;= 1000</code>, Catalan number can be quite huge, even <code>C(999,999)</code>. We can use some big number arithmetic, but on the other hand I came up with little trick to overpass it and use standard integer.</p>

<p>We don't want to know how big actually Catalan number is as long as it's bigger than <code>k</code>. So now we will create Catalan numbers caching partial sums in <code>n x n</code> table.</p>

<pre><code>...                                     ...
5 |                              42     ...
4 |                        14    42     ...
3 |                   5    14    28     ...
2 |             2     5     9    14     ...
1 |       1     2     3     4     5     ...
0 | 1     1     1     1     1     1     ...
   ----------------------------------   ...
    0     1     2     3     4     5     ...
</code></pre>

<p>To generate it is quite trivial:</p>

<pre><code>C(x,0) = 1
C(x,y) = C(x,y-1) + C(x-1,y)  where y &gt; 0 &amp;&amp; y &lt; x
C(x,y) = C(x,y-1) where x == y
</code></pre>

<p>So what we can see only this:</p>

<pre><code>C(x,y) = C(x,y-1) + C(x-1,y)  where y &gt; 0 &amp;&amp; y &lt; x
</code></pre>

<p>can cause overflow.</p>

<p><strong>Let's stop at this point and provide definition.</strong></p>

<p><code>k-flow</code> - it's not real overflow of integer but rather information that value of <code>C(x,y)</code> is bigger than <code>k</code>.</p>

<p>My idea is to check after each running of above formula whether <code>C(x,y)</code> is grater than <code>k</code> or any of sum components is <code>-1</code>. If it is we put <code>-1</code> instead, which would act as a marker, that <code>k-flow</code> has happened. I guess it quite obvious that if <code>k-flow</code> number is sum up with any positive number it's still be <code>k-flowed</code> in particular sum of 2 <code>k-flowed</code> numbers is <code>k-flowed</code>.</p>

<p>The last what we have to prove is that there is no possibility to create real overflow. Real overflow might only happen if we sum up <code>a + b</code> which non of them is <code>k-flowed</code> but as sum they generated the real overflow.</p>

<p>Of course it's impossible since maximum value can be described as <code>a + b &lt;= 2 * k &lt;= 2*10^9 &lt;= 2,147,483,647</code> where last value in this inequality is value of int with sign. I assume also that int has 32 bits, as in my case.</p>