I have a string with length N. I would like to know how many segmentations are possible to it. Consider the example abcdc the number of N = 5 All possible segmentations are

['abcd', 'c']
['abc', 'dc']
['abc', 'd', 'c']
['ab', 'cdc']
['ab', 'cd', 'c']
['ab', 'c', 'dc']
['ab', 'c', 'd', 'c']
['a', 'bcdc']
['a', 'bcd', 'c']
['a', 'bc', 'dc']
['a', 'bc', 'd', 'c']
['a', 'b', 'cdc']
['a', 'b', 'cd', 'c']
['a', 'b', 'c', 'dc']
['a', 'b', 'c', 'd', 'c']

Then what will happen when my N tends to infinity . Any closed form equations?


There are n-1 points where you can break the string. Each is independent of the others. Therefore there are $2^{n-1}$ possibilities to break the string.

  • $\begingroup$ What will happen when N -> Infinity ? $\endgroup$ – Karun Mar 20 '16 at 22:55
  • $\begingroup$ $\lim_{n \to \infty} 2^{n-1} = \infty$ $\endgroup$ – Kaveh Mar 20 '16 at 22:59
  • $\begingroup$ How is it possible ? $\endgroup$ – Karun Mar 20 '16 at 22:59
  • $\begingroup$ The limit of any unbounded increasing function is infinity. Ask on Mathematics if it is not clear for you. $\endgroup$ – Kaveh Mar 20 '16 at 23:02
  • $\begingroup$ Yeah. That is from limits and continuity $\endgroup$ – Karun Mar 20 '16 at 23:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.