I was solving a question where I had to find the number of numbers of length N without having any consecutive zeros from the set [0,K-1] for any K.

I came up with the following equation using exclusion principle:-

$ count(N,K)=K^N - \sum _{i=2}^N\:K^{\left(N-i\right)}\left(N+1-i\right)$

My question : Is the equation correct and does the series converge to a single value if N = $\inf$ ?


I am subtracting all ways in which consecutive 0s can occur. For eg for 2 consecutive 0s, I bunch the two 0s up as 1. Now, I have N-1 remaining places from which I select 1 place in (N-1) ways. The remaining N-2 places (after un-bunching up the two 0s) have $\left(N-2\right)^{K-1}$ choices ( excluding zero and also repetition of other digits is allowed)
I repeat the process for 3 consecutive 0s, 4 consecutive 0s up to N consecutive 0s. i is the number of consecutive 0s

  • $\begingroup$ It would significantly ease the work for everyone in validating your equation if you included your derivation in detail of the equation, lest everyone end up just redoing your work and wasting time. It would also make it easier to critique your approach, correct misconceptions, and so on. $\endgroup$ – Eevee Trainer Apr 10 at 8:50
  • $\begingroup$ Added my method to approach this question. Also clarified purpose of i $\endgroup$ – le Professeur Apr 10 at 9:00
  • $\begingroup$ Are these numbers written in binary form? decimal form? $\endgroup$ – N. F. Taussig Apr 10 at 14:35
  • $\begingroup$ Decimal numbers.. from 0 to K-1 for any positive integer K which is greater than 0 $\endgroup$ – le Professeur Apr 10 at 15:59
  • $\begingroup$ Shouldn't it be $K^N$, instead of $N^K$? $\endgroup$ – Mike Earnest Apr 11 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.