What is this numerically-generated function?

Question

This question is an "outgrowth" of https://math.stackexchange.com/questions/4380919/ which led to a numerically-generated two-parameter function $f_b(n)$, where $b$ is the number base $2,3,4,\ldots$, and $n$ is as follows, paraphrasing the original question...

What is the number of $n$-character words consisting of $0$'s and $1$'s (and etc for bases greater than $2$) such that the number of $1$'s, counting from the left, is at all times greater than the number of $0$'s? When $b\gt2$, the number of $1$'s is greater than the combined number of all other digits. (Note: the original question only asked about the $b=2$ case.)

I couldn't see how to rigorously set up the problem and derive a solution. So instead, I just programmed the problem, generating the following sequences for different bases

       n: 1  2  3   4   5    6    7     8      9     10      11      12
  base 2: 1, 1, 2,  3,  6,  10,  20,   35,    70,   126,    252,    462
  base 3: 1, 1, 3,  5, 15,  29,  87,  181,   543,  1181,   3543,   7941
  base 4: 1, 1, 4,  7, 28,  58, 232,  523,  2092,  4966,  19864,  48838
  base 5: 1, 1, 5,  9, 45,  97, 485, 1145,  5725, 14289,  71445, 185193
  base 6: 1, 1, 6, 11, 66, 146, 876, 2131, 12786, 32966, 197796

Googling those sequences immediately finds

  base 2: https://oeis.org/A001405
  base 3: https://oeis.org/A126087
  base 4: https://oeis.org/A128386
  base 5: https://oeis.org/A121724
  base 6: ????? (couldn't google anything for the b=6 sequence)

For base 2, that straightforward oeis answer is simply the binomial coefficient $f_2(n)=\left(n-1 \atop \lfloor\frac{n-1}2\rfloor\right)$ (which immediately answered the original question).   But then we get entirely different mathematical functions for each different base $b$. At least I'm not seeing any sensible relationship between them.

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,5$ (and for $b=6$ 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,5$ functions are just special cases. Anyway, that's the conjecture I'm asking about, and suggesting might be worth investigating further.

And in case it's of any interest the small C program is below. To generate results for base $b$ between $n_1\le n\le n_2$ run it with the three command-line arguments   n1  n2  b   (note that it just uses $32$-bit signed ints, so run it with $b^{n_2}\lt2^{31}$)

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

int main ( int argc, char *argv[] ) {
  int         n1 = ( argc>1? atoi(argv[1]) :    1 ),
              n2 = ( argc>2? atoi(argv[2]) :   10 ),
            base = ( argc>3? atoi(argv[3]) :    2 );
  int  n = n1;
  int ipow(), binky(), nwords=0, ichar=0, iword=0,
      isprefmax(char*,char,int), imax[99],nmax[99],nprintmax=1;
  char *itoa(), basechars[99] =
      "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#$*";
  for ( n=n1; n<=n2; n++ ) {
    nwords = ipow(base,n);  nprintmax = 1;
    for ( ichar=0; ichar<base; ichar++ ) imax[ichar] = 0;
    for ( iword=0; iword<nwords; iword++ ) {
      char *aword = itoa(iword,base,n);
      for ( ichar=0; ichar<base; ichar++ )
        if ( isprefmax(aword,basechars[ichar],base) ) imax[ichar] += 1; }
    printf("n=%2d, nwords=%8d,  #max=", n,nwords);
    for ( ichar=1; ichar<base; ichar++ )
      if ( imax[ichar] != imax[ichar-1] ) nprintmax=base;
    nmax[n] = (nprintmax==1?imax[0]:-999);
    for ( ichar=0; ichar<nprintmax; ichar++ ) printf("%6d",imax[ichar]);
    if (base==2) printf(",  (%2d,%2d)=%6d", n-1,(n-1)/2,binky(n-1,(n-1)/2));
    printf("\n");
    } /* --- end-of-for(n) --- */
    for ( n=n1; n<=n2; n++ ) printf("%d%s",nmax[n],(n<n2?", ":"\n"));
  exit(0); }

int  isprefmax ( char *a, char c, int base ) {
  int i=0, nc=0, nother=0, ichar=0;  int ismax=0;
  char basechars[99] =
      "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#$*";
  if ( a == NULL ) goto end_of_job;
  for ( i=0; a[i]!='\000'; i++ ) {
    if ( a[i] == c ) nc++; else nother++;
    if ( nother >= nc ) goto end_of_job; }
  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 ); }

int binky ( int n, int k ) {
  /* --- allocations and declarations --- */
  int   this_binky= (-1),               /* init for error */
        binky_max = INT_MAX/2;          /* assert binky <= binky_max */
  /* --- check args for "convergence" --- */
  if ( n<k || k<0 ) return ( -1 );      /* argument error */
  if ( n==k                             /* default=1 if n == k */
  ||   n<1 || k<1 ) return (  1 );      /* default=1 if n or k == 0 */
  /* --- recurse (in case one curse isn't enough) --- */
  this_binky = binky(n-1,k-1) + binky(n-1,k);
  if ( this_binky > binky_max ) this_binky = (-1); /* overflow check??? */
  return ( this_binky );
  } /* --- end-of-function binky() --- */

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

Answer 1

First, we notice that the first character must be 1. Let's take it off and focus on the remaining $n-1$ characters, where the number of 1's in each prefix must be at least as many as the number of the other $b-1$ digits.

Replacing each 1 with [ and each other digit with ], we get a truncated Dyck word, where a few ]]...] at the end are truncated. The number of such words with $n-1-k$ [ and $k$ ] equals $\frac{n-2k}{n}\binom{n}{k} = \binom{n}{k} - 2\binom{n-1}{k-1}$. It remains to distribute $b-1$ digits $\ne 1$ among the $k$ positions, resulting in the formula: \begin{split} f_b(n) &= \sum_{k=0}^{\lfloor (n-1)/2\rfloor} \frac{n-2k}{n}\binom{n}{k} (b-1)^k \\ &= \sum_{k=0}^{\lfloor (n-1)/2\rfloor} \left( \binom{n}{k} - 2\binom{n-1}{k-1}\right) (b-1)^k. \end{split}

I doubt there is a simple expression for $b>2$, but the generating function can be derived from here.