Given N switches, how many combinations are there where no more and no fewer than m switches are turned on?

Question

I realize this question has probably been asked before, but at my level of combinatorics I wasn't able to recognize it.

I used switches just as an example, obviously bits or some other abstract could be used. But basically what I want to know is

Given 2^N combinations of switches being on or off, how can you find the subset where m switches are turned on? Where 0 ≤ m ≤ N.

For example, if you have 4 switches (N) and were required to have any combination of 3 switches turned on (m), the solution would be 4 because of the 2^4 (32) possible combinations of the switches there are only 4 which have only 3 switches turned on.

What I really want is to come up with some formula that takes N and m and gives the length of the subset mentioned above. I feel like induction could be used for find the formula and prove it, but I haven't had any luck yet.

Thanks in advance for the help!

PS This is not a HW problem or something, I'm just honestly curious about the solution and have been thinking it over all morning.

Answer 1

Consider a binary string of length n

First, your task is to choose a position to set a bit to 1.
How many ways can you choose a bit from the available n unset bits? (n ways)

After that, your task is to choose a position to set another bit to 1.
How many ways can you choose a bit from the remaining n-1 unset bits? (n-1 ways)

See any pattern?

---

If the length of the string is 10,
and if you want to set exactly 4 of the bits to 1,
it seems you can do it in 10*9*8*7 ways. But...