1
$\begingroup$

Let's say we need to create a string out of 2 characters : A and/or B, of given length n. The occurrence of A should at least be p times of b at any given instance. Eg: n=4,p=2. Valid combination :AAAA, AAAB, AABA. Note how ABAA is not the right one. What would be the logic behind this?

My approach so far: N=8,p=2. No of B = 1 or 2. 1st 2 place should always be A. Remaining places to consider :6. When No of B : 1, we have 6 combinations. AABAAAAA, AAABAAAA, AAAABAAA, AAAAABAA, AAAAAABA,AAAAAAAB.

When no of b :2, 6c2 gives 15, but only 12 of them will fit the criteria. AABBAAAA, AAABBAAA, AABABAAA : These 3 should not be considered. How to make this generic? It can be that the entire problem can be solved without combination principles too. If so what concepts can be used? Need inputs about this being the right approach and how to take it forward. Source : question found on a coding platform.

$\endgroup$
9
  • 1
    $\begingroup$ Welcome to MathSE. Please edit your question to show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site. $\endgroup$
    – N. F. Taussig
    Commented Sep 2, 2019 at 20:36
  • $\begingroup$ For N=8, P=2, and two B's, there are indeed 6C2=15 sequences that start with AA (those starting with B or AB are disallowed), but why did you not disallow AAABABAA, AAAABABA, AAAAABAB? $\endgroup$
    – Jaap Scherphuis
    Commented Sep 3, 2019 at 9:21
  • $\begingroup$ Do you actually want a mathematical answer, or a programming-oriented answer? If the latter, it might be worth asking the moderators to migrate this question to cs.stackexchange.com. For what it's worth, I suspect that a very efficient solution is possible, but proving it correct is quite involved; whereas the solution which I think is the intended one is pretty simple. $\endgroup$
    – Peter Taylor
    Commented Sep 3, 2019 at 11:22
  • $\begingroup$ @PeterTaylor, I'm interested in the basic algorithm behind it. Programming answer is nothing but the mathematical version of it, correct? Or the answer going to differ when approached programmatically? $\endgroup$
    – Priya Vaidyanathan
    Commented Sep 3, 2019 at 14:26
  • $\begingroup$ @jaap , at any given instance, number of A Should be at least P times of B. So for AAABBAAA, at index 5 we have 2 B's and 3 A's . Ideally 4 A's should be present at that instance (not overall). Hence we reject this case $\endgroup$
    – Priya Vaidyanathan
    Commented Sep 3, 2019 at 14:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .