Skip to main content
1 of 2
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

Algorithm for $q$-Bell numbers

  • Let $T(n,k)$ be A126347 (i.e., triangle, read by rows, with row polynomials $B(n, q)$). Here $$ B(n, q) = \sum\limits_{k=0}^{n-1}\binom{n-1}{k}B(k, q)q^k, \\ B(0, q) = 1. $$
  • Start with vector $\nu$ of fixed length $m$ with elements $\nu_i=1$ (that is, $\nu = \{1,1,\dotsc,1\}$) and for $i$ from $1$ to $m-2$, for $j$ from $1$ to $i$, for $k$ from $1$ to $i-j+1$ apply $\nu_k := q\nu_k + \nu_{k+1}$. After ending these operations we need to reverse vector $\nu$.

I conjecture that after the whole transform we have $$\nu_n=B(n-1, q).$$

Here is the PARI/GP program to check it numerically:

upto1(n) = my(v1); v1 = vector(n+1, i, 0); v1[1] = 1; for(i=1, n, v1[i+1] = sum(k=0, i-1, binomial(i-1, k)*v1[k+1]*q^k)); v1
upto2(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-2, for(j=1, i, for(k=1, i-j+1, v1[k] = q*v1[k] + v1[k+1]))); Vecrev(v1)
test1(n) = upto1(n) == upto2(n+1)

Is there a way to prove it?

Notamathematician
  • 4.9k
  • 2
  • 11
  • 24