Listing all monotone increasing binary digits

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.

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

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.

• thats really an excellent way. Just the all zero sequence is missing. then the total number will be also $2111$. – Seyhmus Güngören Sep 22 '18 at 23:11
• monotoneTuples[0, 31, 1] this is killing my mathematica) – Seyhmus Güngören Sep 23 '18 at 22:04
• @SeyhmusGüngören It takes 550GB to store a 2^31 by 32 array of integers, so that's why your computer is unhappy. – Carl Woll Sep 24 '18 at 0:39
• maybe it could be nicer if your comment would be told to me by Mathematica itself? – Seyhmus Güngören Sep 24 '18 at 13:44
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]