Mohamed_Saad62's blog

Need help with combinatorics

By Mohamed_Saad62, history, 5 years ago, In English

Given a string consist just of the letter 'u' ,if we can consider every two adjacent 'u' -->' w' and every u can be used only once in how many ways the string can appear ?

example : uuu can be uuu or wu or u w so the answer is 3 .

I am asking this question because at the last contest I was trying to solve this problem https://codeforces.me/contest/1245/problem/C and I claim the solution is every continuous 'u' or 'n' I save in how many ways it can appear in a vector and then multiply all the numbers and this is the answer .

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Trace if you have 2,3,4,5 consecutive u or n and will observe the right pattern

It will be Fibonacci series at the end.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please tell the reason behind this fibonacci Pattern

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It_Wasnt_Me Thanks

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Let say F(n) is the amount of ways the string uuu...uu (n times) can appear. We can do two things: (1) Keep the last character as 'u': then, there are remaining n-1 characters. (2) Use the last two characters as 'w': then, there are remaining n-2 characters. Therefore: F(n) = F(n-1) + F(n-2) for n > 2. F(1) = 1, because you can't change a single 'u'. F(2) = 2, because 'uu' can be 'uu' or 'w'

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    aniervs Thanks

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    Beautiful!

    It can be generalized as, if 'uu...'(m times) is replace by 'w'.

    Then, F(n) = ̷F̷(̷n̷-̷1̷)̷ ̷+̷ ̷F̷(̷n̷-̷2̷)̷ ̷+̷ ̷.̷.̷.̷ ̷+̷ ̷F̷(̷n̷-̷m̷)̷;

    Edit : — F(n) = F(n-1) + F(n-m), look at aniervs comment below.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If 'uuu...u' (m times) is replaced by 'w'. Then we can: (1) Keep last character as 'u': there are remaining n-1 characters. (2) Use the last m characters as 'w': then, there are n-m characters. Therefore: F(n) = F(n-1) + F(n-m)

      → Reply