n-bit。未満の任意の制限以下のワード内のバイナリビットパターンの数をカウントするアルゴリズムを探しています2^n。1-bitさらに、すべての組み合わせ、組み合わせなどのカウントを生成したいと思います2-bit。明らかに、制限がの場合、組み合わせ2^nがあります。ただし、制限が課せられた場合、それらの可能な組み合わせのすべてが有効であるとは限りません（課された制限よりも少ない）。2^n(C(n,1) 1-bit combinations plus C(n,2) 2-bit plus C(n,3) 3-bit and so on)
たとえば、と言いn=4ます。16の可能なビットパターンがあり、そのうち15は1つ以上を含みます1-bits。10の制限が課された場合、10を超えるパターンはカウントに含まれません。したがって、シングルビットパターンの場合、有効なパターンは0001、、、、0010および0100です1000。2ビットパターンは、、、、0011に0101なり0110ます1001。パターン1010と1100は10を超えるため、カウントされません。唯一の3ビットビットは0111、唯一の4ビットパターン1111が制限を超えている間です。
Fが私のカウント関数である場合、10未満の1ビットF(4,10,1)のパターンの数は4を返しますが、6の場合は4を返します。の実際の値は大きくなる可能性があるため（40またはビット）、可能なパターンを列挙します。制限に対してテストし、有効なものを数えることは実用的ではありません。4-bitF(4,10,2)C(4,2)n
これを効率的に行う方法について何かアイデアはありますか？