1

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.

Priya Vaidyanathan
  • 11
  • 1
    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. – N. F. Taussig Sep 02 '19 at 20:36
  • 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? – Jaap Scherphuis Sep 03 '19 at 09:21
  • 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. – Peter Taylor Sep 03 '19 at 11:22
  • @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? – Priya Vaidyanathan Sep 03 '19 at 14:26
  • @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 – Priya Vaidyanathan Sep 03 '19 at 14:43
  • The programming answer would be similar to a basic mathematical answer, although in terms of loops rather than generating functions. But from looking up a couple of small examples in OEIS, the cleanest mathematical treatment might go through inverting Riordan arrays. – Peter Taylor Sep 03 '19 at 14:48
  • I see. I thought the counters were reset for each block of A's. Anyway, for p=1 there is an exact formula, because you get the Catalan numbers. For other p, the argument at that link does not work unfortunately. – Jaap Scherphuis Sep 03 '19 at 15:15
  • @JaapScherphuis, no. For $p=1$ you get A001405. To get the Catalan numbers it would be necessary to add a restriction that the word must contain $\frac{n}{1+p}$ Bs. – Peter Taylor Sep 03 '19 at 15:20
  • @PeterTaylor Oh yes, you're quite right. – Jaap Scherphuis Sep 03 '19 at 15:25

0 Answers0