umsh1ume's blog

A counting problem
By umsh1ume, history, 8 years ago, In English

In how many ways can we make n digit number from 1,2 and 3 such that no continuous triplet has distinct integers.Ex: 21231122 will not be counted but 22113311122 will be. i.e. 123 or 321 or 312 or 213 or 132 or 231 should not be present in the number

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It is a classic dp problem. Define dp(x,y,i) as the number of ways to get a number, which ends in ...xy and has i digits i.e. its last two digits are x and y, with the properties you said. Now, you can easily get the answer. For example, dp(1,2,n) = dp(1,1,n — 1) + dp(2, 1, n — 1). (Think about it, it is not that hard). Finally, the answer will be sum of dp(x,y,n) where x and y are numbers from 1 to 3.

→ Reply