Number of $n$ lettered words made out of $n$ A's and $n$ B's with specified conditions.

Question

Number of $n$ lettered words made out of $n$ A's and $n$ B's such that the number of A's from the left is at all times greater than the number of B's from the left. String needs to contain both letters $A$ and $B$.

From my understanding there has to be a minimum value for $n$ which goes at three and includes both A and B as 3: $$AAB$$

For $n$ with a value of 4: $$AAAB$$ $$AABA$$

For $n$ with value 5: $$AAAAB$$ $$AAABA$$ $$AABAA$$ $$AAABB$$ $$AABAB$$

And so on...

From this we know that the minimum value of A in a string of $n$ letters is $\frac{(n+1)}{2}$ and a max value of B is $\frac{(n-1)}{2}$ for an odd integer $n$. A min value of A is $\frac{(n+2)}{2}$ and a max value of $\frac{(n-2)}{2}$ for an even integer $n$. And the string has to start with two A's.

.....

I am having trouble approaching the problem. Any hints appreciated(algebraic hints preferred).

Edit:

1. I seemed to have misunderstood the condition specified to be followed in chunks of $A$ and $B$. The conditions do not apply in chunks.

2. The string has to include both letters $A$ and $B$.

3. The statement "$n$ $A$'s and $n$ $B$'s" is trivial and holds not value. Only the fact that both $A$ and $B$ have to be included in the string is necessary.

Answer 1

Just to shorten my preceding answer, and to explicitly give you the mathematical expression, for words of length $n$ the answer is just the binomial coefficient $$\left(n-1 \atop \lfloor\frac{n-1}2\rfloor\right)$$ where $\lfloor\cdot\rfloor$ is just the floor function, or in this case just integer division truncating the fractional part. (And I added that to my copy of the preceding answer's code, and it indeed checks. I can re-post that code if you actually want it for anything.)

Edit --   Oops, I hadn't noticed @ayan3095's Edit to his question, where he explicitly adds the constraint "2.The string has to include both letters A and B."   So I added that constraint to the code in the preceding answer, and the new numerically-generated results are simply one less than they were without the constraint.

So the new-and-improved (but very little changed) mathematical expression is that for words of length $n$ the answer is $$\left(n-1 \atop \lfloor\frac{n-1}2\rfloor\right) - 1$$

By the way, as posted in the preceding answer, this is just (an alternative definition of) the central binomial coefficient, as discussed in detail at, e.g.,
    https://mathworld.wolfram.com/CentralBinomialCoefficient.html
    https://archive.lib.msu.edu/crcmath/math/math/c/c178.htm
And note that I never rigorously set up @ayan3095's problem and derived this solution. Instead, I just programmed the problem, generating a sequence of answers for $n=1,2,\ldots,20$ and then just googled that sequence of numbers, immediately finding the above links. Kind of like googling the answer to find the question, or something like that. So is this the new "new math"??? :)

In any case, this still leaves the issue of rigorously deriving the above answer ab initio from @ayan3095's question, which I have no idea how to approach. Maybe somebody else might care to take a stab at that.

Answer 2

>>E d i t and Answer<< --- Okay, googling the numerically-generated sequence of numbers generated below gets us to
    https://mathworld.wolfram.com/CentralBinomialCoefficient.html
where about halfway down the page you'll find
    "A less common alternative definition of the nth central binomial coefficient is...
    ...of which "the first few values are 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, ..."
So I daresay that's your answer. Or see
    https://archive.lib.msu.edu/crcmath/math/math/c/c178.htm
for a similar discussion.

More of an extended comment than an answer: if we replace A and B by 0 and 1, we're talking about binary strings, and that's easily programmed. For strings of length $n$, all we have to do is consider the 0,1-binary representation of every number $i:0\le i\lt 2^n$. And the results for $n=1\ldots20$ are

n= 1,  nwords=       2,  n0max=     1,  n1max=     1
n= 2,  nwords=       4,  n0max=     1,  n1max=     1
n= 3,  nwords=       8,  n0max=     2,  n1max=     2
n= 4,  nwords=      16,  n0max=     3,  n1max=     3
n= 5,  nwords=      32,  n0max=     6,  n1max=     6
n= 6,  nwords=      64,  n0max=    10,  n1max=    10
n= 7,  nwords=     128,  n0max=    20,  n1max=    20
n= 8,  nwords=     256,  n0max=    35,  n1max=    35
n= 9,  nwords=     512,  n0max=    70,  n1max=    70
n=10,  nwords=    1024,  n0max=   126,  n1max=   126
n=11,  nwords=    2048,  n0max=   252,  n1max=   252
n=12,  nwords=    4096,  n0max=   462,  n1max=   462
n=13,  nwords=    8192,  n0max=   924,  n1max=   924
n=14,  nwords=   16384,  n0max=  1716,  n1max=  1716
n=15,  nwords=   32768,  n0max=  3432,  n1max=  3432
n=16,  nwords=   65536,  n0max=  6435,  n1max=  6435
n=17,  nwords=  131072,  n0max= 12870,  n1max= 12870
n=18,  nwords=  262144,  n0max= 24310,  n1max= 24310
n=19,  nwords=  524288,  n0max= 48620,  n1max= 48620
n=20,  nwords= 1048576,  n0max= 92378,  n1max= 92378

n0max is the number of times 0's are greater, and just as a check it also prints the number of times 1's are greater. Silly little C program is below...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main ( int argc, char *argv[] ) {
  int n1 = ( argc>1? atoi(argv[1]) : 1 ),
      n2 = ( argc>2? atoi(argv[2]) : 10 );
  int  n = n1;
  int ipow(), nwords=0, iword=0,
      isprefmax(char*,char), n0max=0, n1max=0;
  char *itoa();
  for ( n=n1; n<=n2; n++ ) {
    nwords = ipow(2,n);
    n0max = n1max = 0;
    for ( iword=0; iword<nwords; iword++ ) {
      char *aword = itoa(iword,2,n);
      if ( isprefmax(aword,'0') ) n0max++;
      if ( isprefmax(aword,'1') ) n1max++; }
    printf("n=%2d,  nwords=%8d,  n0max=%6d,  n1max=%6d\n",
    n,nwords,n0max,n1max); }
  exit(0); }

int  isprefmax ( char *a, char c ) {
  int i=0, nc=0, nother=0;  int ismax=0;
  if ( a == NULL ) goto end_of_job;
  while ( a[i] != '\000' ) {
    if ( a[i] == c ) nc++; else nother++;
    if ( nother >= nc ) goto end_of_job;
    i++; }
  ismax = 1;
  end_of_job: return ( ismax ); }

int ipow ( int base, int exp ) {
  int basetoexp = 1;
  while ( 1 ) {
    if ( exp&1 ) basetoexp *= base;
    exp >>= 1;
    if ( !exp ) break;
    base *= base; }
  return ( basetoexp ); }

char *itoa ( int i, int base, int len ) {
  static char a[99], digits[99] = /* up to base 65 */
      "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#$*";
  int n=0, j=0,k=0;
  while ( 1 ) {
    a[n++] = digits[i%base];
    if ( (i/=base) < 1 ) break; }
  a[n] = '\000';
  for ( k=n-1,j=0; k>j; k--,j++ ) {
    char ak=a[k]; a[k]=a[j]; a[j]=ak; }
  if ( n < len ) {
    memmove(a+(len-n),a,n);
    memset(a,'0',(len-n)); }
  return ( a ); }

Answer 3

I'm posting yet another answer because I got interested in @ayan3095's problem, generalized it, and found some interesting (at least to me) results, that might be worth discussing.

Rather than just strings of length $n$ consisting of A,B, as originally asked by @ayan3095, consider strings consisting of A,B,C,.... Or, for programming purposes, strings of length $n$ in base $b$ (so $b^n$ of them). And a rather simple generalization of the program posted in my original answer accommodates this problem generalization.

And I found the results interesting because googling them came up with entirely different mathematical functions for each base $b$. If we ignore @ayan3095's constraint   2.The string has to include both letters A and B   (it just reduces all answers by $1$), then for base $b=2$ and various $n$ we've already found the original answer (an alternate form of the centarl binomial coefficient) $$f(b=2,n) = \left(n-1 \atop \lfloor\frac{n-1}2\rfloor\right)$$ And now for $b=3$ the program generates answers...

bash-5.1$ ./prefmax 1 12 3 0
n= 1, nwords=       3,  nmax=     1
n= 2, nwords=       9,  nmax=     1
n= 3, nwords=      27,  nmax=     3
n= 4, nwords=      81,  nmax=     5
n= 5, nwords=     243,  nmax=    15
n= 6, nwords=     729,  nmax=    29
n= 7, nwords=    2187,  nmax=    87
n= 8, nwords=    6561,  nmax=   181
n= 9, nwords=   19683,  nmax=   543
n=10, nwords=   59049,  nmax=  1181
n=11, nwords=  177147,  nmax=  3543
n=12, nwords=  531441,  nmax=  7941

And guess what? See
    https://oeis.org/A126087
which generates exactly our sequence, but bears no relation whatsoever (not that I can see, anyway) to our $b=2$ case giving the central binomial coefficient above.

And for $b=4$ the program gives...

bash-5.1$ ./prefmax 1 12 4 0
n= 1, nwords=       4,  nmax=     1
n= 2, nwords=      16,  nmax=     1
n= 3, nwords=      64,  nmax=     4
n= 4, nwords=     256,  nmax=     7
n= 5, nwords=    1024,  nmax=    28
n= 6, nwords=    4096,  nmax=    58
n= 7, nwords=   16384,  nmax=   232
n= 8, nwords=   65536,  nmax=   523
n= 9, nwords=  262144,  nmax=  2092
n=10, nwords= 1048576,  nmax=  4966
n=11, nwords= 4194304,  nmax= 19864
n=12, nwords=16777216,  nmax= 48838

And guess what again? See
    https://oeis.org/A128386/b128386.txt
for exactly our sequence, but this time without explanation how they derived it.

So, the overall result is that we have our $f(b,n)$, generated in exactly one numerical way, but identified with apparently entirely unrelated mathematical functions for $b=2,3,4$. And for $b=5$ I couldn't google anything. So perhaps we're looking at some new more general function, for which the already-known $b=2,3,4$ functions are just special cases. Anyway, that's the conjecture I'm suggesting might be worth investigating further.