Listing all monotone increasing binary digits

Question

For $n=5$, I have $32$ binary digits and for this there are $2^{32}$ combinations. Out of this many, the interesting ones (i.e., the ones that have monotone increasing binary digits) are only about "$2111$". I know how these can be found very easily but I am missing Mathematica knowledge. Therefore I cannot complete my program.

First I need to seperate these $32$ bits according to Pascals triangle numbers. Since $n=5$, these numbers are $1,5,10,10,5,1$. Their sum is $32$ and I separate the digits accordingly. My list is as follows:

List={

{0|00000|0000000000|0000000000|00000|0}

... those who satisfy the rule below

{1|11111|1111111111|1111111111|11111|1}}

From right to the left I start with the 5 bits and take all possible combinations:

|00000|--> 00001,00010,00011...11111

This says I have the following ones in the list

{0|00000|0000000000|0000000000|00001|1,    
0|00000|0000000000|0000000000|00010|1,   
0|00000|0000000000|0000000000|00011|1,...,      
0|00000|0000000000|0000000000|11111|1}

Then I go left via keeping |11111|1 as fixed. Now I have $10$ digits and the following are the elements of the list

{0|00000|0000000000|0000000001|11111|1,    
0|00000|0000000000|0000000010|11111|1,   
0|00000|0000000000|0000000011|11111|1,...,      
0|00000|0000000000|1111111111|11111|1}

Then, I do the same thing again but fixing |1111111111|11111|1. Then the followings are the elements of the set:

{0|00000|0000000000|1111111111|11111|1,    
0|00000|0000000001|1111111111|11111|1,   
0|00000|0000000010|1111111111|11111|1,...,      
0|00000|1111111111|1111111111|11111|1}

Again the same thing and we are done:

{0|00001|1111111111|1111111111|11111|1,    
0|00010|1111111111|1111111111|11111|1,   
0|00011|1111111111|1111111111|11111|1,...,      
0|11111|1111111111|1111111111|11111|1}

So in total there are $2^5$ numbers from the first stage, From the other two stages we have $2^{10}-1$ for each and for the last stage $2^5-1$ numbers. We also have all zeros and all ones and if I calculated correctly there are $2111$ of them. I used the character "|" for separation. The final list should look like

List={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},....,{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}

I only have the following code part:

IntegerDigits[2, 2, 5]
{0, 0, 0, 1, 0}

IntegerDigits[2, 2, 10]
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0}

Using this code in a 'for loop' I can obtain such combinations but I must concatenate these to the previous bits which are all zeros and all subsequent bits which are all 1s. This is what I don't know how to do.

Answer 1

One idea is to make use of Tuples:

monotoneTuples[b_, m_, e_] := Rest @ Tuples@Join[
    ConstantArray[{0}, b],
    ConstantArray[{0,1}, m],
    ConstantArray[{1}, e]
]

monotoneTuples will create your partitioned set. For example:

Column @ monotoneTuples[5, 3, 1] //TeXForm

$\begin{array}{l} \{0,0,0,0,0,0,0,1,1\} \\ \{0,0,0,0,0,0,1,0,1\} \\ \{0,0,0,0,0,0,1,1,1\} \\ \{0,0,0,0,0,1,0,0,1\} \\ \{0,0,0,0,0,1,0,1,1\} \\ \{0,0,0,0,0,1,1,0,1\} \\ \{0,0,0,0,0,1,1,1,1\} \\ \end{array}$

Then, you can join each of these sets:

res = Join[
    monotoneTuples[31,1,0],
    monotoneTuples[26,5,1],
    monotoneTuples[16,10,6],
    monotoneTuples[6,10,16],
    monotoneTuples[1,5,26],
    monotoneTuples[0,1,31]
];
res //Length

2110

Addendum

For memory reasons, it makes sense to create a list of integers instead of a list of bit vectors, especially if you will be creating a lot of them. So, an alternative is:

monotoneIntegers[list_] := With[{a = Accumulate[Prepend[0] @ Most @ Reverse @ list]},
    Prepend[0][Join @@ (Range[2, 2^Reverse@list] 2^a - 1)]
]

For example, compare:

integers = monotoneIntegers[{1,3,2}]
bitvectors = IntegerDigits[%, 2, 6]

{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 63}

{{0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 1, 1, 1}, {0, 0, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 1}, {0, 1, 0, 0, 1, 1}, {0, 1, 0, 1, 1, 1}, {0, 1, 1, 0, 1, 1}, {0, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}}

The memory usage of the integers is much less:

ByteCount @ integers
ByteCount @ bitvectors

200

1968

and the disparity increases with more bits.

Answer 2

ClearAll[monotoneDigits]
monotoneDigits = Module[{a = Accumulate[Binomial[#, Range[-1, #]]]},
 Join[{ConstantArray[0, 2^#]}, 
  IntegerDigits[Join@@Range[2^Most[1 + a] - 1, 2^Rest[a] - 1, 2^Most[a]], 2, 2^#]]]&;

Length @ monotoneDigits[5]

2111

Rest @ monotoneDigits[5] == res (* res from Carl's answer *)

True

Length /@ (monotoneDigits /@ Range[2, 6])

{6, 17, 96, 2111, 1114238}

monotoneDigits2[3] // Column // TeXForm

$\small\begin{array}{l} \{0,0,0,0,0,0,0,0\} \\ \{0,0,0,0,0,0,0,1\} \\ \{0,0,0,0,0,0,1,1\} \\ \{0,0,0,0,0,1,0,1\} \\ \{0,0,0,0,0,1,1,1\} \\ \{0,0,0,0,1,0,0,1\} \\ \{0,0,0,0,1,0,1,1\} \\ \{0,0,0,0,1,1,0,1\} \\ \{0,0,0,0,1,1,1,1\} \\ \{0,0,0,1,1,1,1,1\} \\ \{0,0,1,0,1,1,1,1\} \\ \{0,0,1,1,1,1,1,1\} \\ \{0,1,0,0,1,1,1,1\} \\ \{0,1,0,1,1,1,1,1\} \\ \{0,1,1,0,1,1,1,1\} \\ \{0,1,1,1,1,1,1,1\} \\ \{1,1,1,1,1,1,1,1\} \\ \end{array}$

Update: An alternative using Tuples in combination with PadLeft and PadRight:

ClearAll[paddedTuples , monotoneDigits2]
paddedTuples[t_][{m_, n_}] := PadLeft[PadRight[Rest@Tuples[{0, 1}, m], 
  {Automatic, n}, 1], {Automatic, t}] 

monotoneDigits2 = Module[{a = Transpose[{#, Accumulate@#}& @ Binomial[#, Range[0, #]]]}, 
   Join @@ (paddedTuples[2^#] /@ a)]&;

monotoneDigits2[5] == res

True