17
$\begingroup$

I'm interested in pairs $A=(a_{i,j})_{i,j=0,1,\ldots}$ and $B=(b_{i,j})_{i,j=0,1,\ldots}$ of infinite matrices for which:

  • They are uni-lower-triangular, i.e., $a_{i,i}=1$ for all $i$ and $a_{i,j}=0$ for all $j>i$.
  • They are inverses, i.e. their product $AB$ is the identity.
  • The generating function of the $k$th column of $A$ is the reciprocal of the generating function of the $(k+1)$st row of $B$, that is, $$ \sum_{j=k}^{\infty}a_{j,k} \; x^{j-k}= \big(\sum_{i=0}^{k+1}b_{k+1,k+1-i} \; x^{i}\big)^{-1}.$$ Notice how for the generating function of columns we start at the $1$ on the diagonal and go down, while for the generating function of rows we start at the $1$ on the diagonal and go left (and all g.f.'s are normalized to start with the constant term).

I have a handful of examples of this occurring with matrices of combinatorial significance:

Example 1. We let $a_{i,j}=\binom{i}{j}$ and $b_{i,j}=(-1)^{i-j}\binom{i}{j}$. Note the generating function of the $k$th row of $B$ is $(1-x)^{k}$, and the generating function of the $(k-1)$th column of $A$ is $1/(1-x)^{k}$.

Example 2. We let $a_{i,j}=S(i+1,j+1)$ and $b_{i,j} = s(i+1,j+1)$, where $S(n,k)$ and $s(n,k)$ are the Stirling numbers of the 2nd and 1st kind, respectively (the shift by one is just to match my convention that indexing of rows/columns starts at $0$). This looks like $$ A = \begin{pmatrix} 1 & 0 & 0 & 0 & \cdots \\ 1 & 1 & 0 & 0 \\ 1 & 3 & 1 & 0 \\ 1 & 7 & 6 & 1 \\ \vdots & & & & \ddots \end{pmatrix} \qquad B = \begin{pmatrix} 1 & 0 & 0 & 0 & \cdots \\ -1 & 1 & 0 & 0 \\ 2 & -3 & 1 & 0 \\ -6 & 11 & -6 & 1 \\ \vdots & & & & \ddots \end{pmatrix}$$ Note that the generating function of the $k$th row of $B$ (and the reciprocal of the generating function of the $(k-1)$th column of $A$) is $(1-x)(1-2x)\cdots(1-kx)$.

Example 3. The previous examples were over $\mathbb{Z}$, this example is over $\mathbb{Z}[q]$; actually it is a $q$-analog of Example 1. We let $a_{i,j} = \binom{i}{j}_q$ be the usual $q$-binomial $\binom{i}{j}_q = \frac{(1-q^i)(1-q^{i-1})\ldots(1-q^{i-j+1})}{(1-q^j)(1-q^{j-1})\ldots(1-q)}$, and we let $b_{i,j} = (-1)^{i-j} \; q^{\binom{i-j}{2}} \; \binom{i}{j}_q$. This looks like: $$ A = \begin{pmatrix} 1 & 0 & 0 & 0 & \cdots \\ 1 & 1 & 0 & 0 \\ 1 & q+1 & 1 & 0 \\ 1 & q^{2}+q+1 & q^{2}+q+1 & 1 \\ \vdots & & & & \ddots \end{pmatrix} \qquad B = \begin{pmatrix} 1 & 0 & 0 & 0 & \cdots \\ -1 & 1 & 0 & 0 \\ q & -(q+1) & 1 & 0 \\ -q^3 & q^3+q^2+q & -(q^2+q+1) & 1 \\ \vdots & & & & \ddots \end{pmatrix}$$ Note that the generating function of the $k$th row of $B$ (and the reciprocal of the generating function of the $(k-1)$th column of $A$) is $(1-x)(1-qx)\cdots(1-q^{k-1}x)$.

Question 1. What is going on here? Why are these pairs of matrices of combinatorial sequences inverse "in two ways"? How is being inverse in one way related to being inverse in the other way?

Note that all of these examples come from sequences of uniform posets: they are the Whitney numbers of the 2nd and 1st kind of these posets. Hence, this question is related to my previous question. (But it's easy to come up with sequences of uniform posets whose matrices are not "inverse in the 2nd way.")

Also note that in all the examples, the generating function of the $(k+1)$st column of $A$ is obtained from the generating function of the $k$th column by multiplying by a simple factor; but (except for Example 1), it is not exactly the same factor every time, so these matrices are not quite Riordan arrays.

Question 2. Can you find some more examples of matrices of combinatorially significant sequences with these properties?

EDIT: One further observation is that you can take any such pair $A=(a_{i,j})$, $B=(b_{i,j})$ of matrices and get another one $A'$, $B'$ by choosing some constant $\kappa$ and setting $a'_{i,j}=\kappa^{i-j} \; a_{i,j}$, $b'_{i,j}=\kappa^{i-j} \; b_{i,j}$. So for example from the Pascal's triangle example you can (basically) get the $f$-vectors of the cross polytope this way.

$\endgroup$
2
  • 1
    $\begingroup$ Btw, the matrices of Ex. 1 contain the coefficients of two iconic Appell Sheffer polynomial sequences--the Pascal and signed Pascal row polynomials--that are an umbral inverse pair whereas those of Ex. 2 with some zero padding are for the iconic pair of binomial Sheffer sequences which are umbral inverses. That the first pair are umbral inverses is related to their moment e.g.f.s being multiplicatively inverse while for the second pair the umbral inversion is related to compositional inversion. $\endgroup$ Mar 20, 2022 at 3:23
  • $\begingroup$ There is some paper on arxiv, with focus on this. This was in the combinatorics section, appearing say in the last 14 days. Cant remember the title though... $\endgroup$ Mar 22, 2022 at 11:31

3 Answers 3

15
$\begingroup$

Following up on David's nice answer, there is a different parametrization that makes the pattern much more obvious. Namely, let $s_1,s_2,\dots$ be arbitrary, then you can write $$A=\Big(h_{i-j}(s_1,s_2,\dots, s_{j+1})\Big)_{i,j=0}^{\infty}$$ $$B=\Big((-1)^{i-j}e_{i-j}(s_1,s_2,\dots, s_{i})\Big)_{i,j=0}^{\infty}$$ And checking that the matrices and the corresponding generating functions are inverses becomes a little more clear. The $h_i, e_i$ denote the complete homogeneous and elementary symmetric functions respectively, with the convention $h_0, e_0 =1$.

$\endgroup$
2
  • 2
    $\begingroup$ This really de-mystifies it! Thanks! $\endgroup$ Mar 20, 2022 at 1:33
  • $\begingroup$ The matrix inverse is explicitly mentioned and the g.f. inverse is present but not explicitly called out in Louis Comtet, Nombres de Stirling généraux et fonctions symétriques, C. R. Acad. Sc. Paris, t. 275 (1972), Sér. A 747–750. $\endgroup$ Apr 21, 2022 at 18:06
10
$\begingroup$

I don't know, but I will point out that, if you specify the entries $A_{(i+1)i}$, then every other entry is uniquely determined by these. The property of being inverse as matrices means that the upper left $k \times k$ block of $A$ determins that upper left $k \times k$ block of $B$. On the other hand, being inverse as power series means that the upper left $k \times k$ block of $B$ determines the left $k-1$ columns of $A$, and hence determines every element in the upper left $(k+1) \times (k+1)$ block of $A$ except for $A_{(k+1)k}$.

I wrote some Mathematica code to carry out this recursion, but I didn't see any pattern in the results. In case it helps, here is the code:

a[n_] :=
 (polys = Drop[b[n - 1], 1].Table[x^(n - 2 - j), {j, 0, n - 2}];
  functions = x^(n - 3)/polys;
  earlyCols = Table[SeriesCoefficient[y, {x, 0, j}], {y, functions}, {j, 0, 
     n - 1}];
  lastCols = 
   {Table[If[i < n - 1, 0, If[i == n - 1, 1, u[n - 1]]], {i, 1, n}],
    Table[If[i < n, 0, 1], {i, 1, n}]};
  Transpose[Join[earlyCols, lastCols]]);
b[n_] := Inverse[a[n]];
a[1] = {{1}}; a[2] = {{1, 0}, {u[1], 1}};

and here are the $6 \times 6$ matrices (first $A$, then $B$):

{{1, 0, 0, 0, 0, 0}, 
{u[1], 1, 0, 0, 0, 0}, 
{u[1]^2, u[2], 1, 0, 0, 0}, 
{u[1]^3, u[1]^2 - u[1] u[2] + u[2]^2, u[3], 1, 0, 0}, 
{u[1]^4, 2 u[1]^2 u[2] - 2 u[1] u[2]^2 + u[2]^3, u[1]^2 - u[1] u[2] + u[2]^2 - u[2] u[3] + u[3]^2, u[4], 1, 0}, 
{u[1]^5, u[1]^4 - 2 u[1]^3 u[2] + 4 u[1]^2 u[2]^2 - 3 u[1] u[2]^3 + u[2]^4, u[1]^2 u[2] - u[1] u[2]^2 + u[1]^2 u[3] - u[1] u[2] u[3] + 2 u[2]^2 u[3] - 2 u[2] u[3]^2 + u[3]^3, u[1]^2 - u[1] u[2] + u[2]^2 - u[2] u[3] + u[3]^2 - u[3] u[4] + u[4]^2, u[5], 1}}

{{1, 0, 0, 0, 0, 0}, 
{-u[1], 1, 0, 0, 0, 0}, 
{-u[1]^2 + u[1] u[2], -u[2], 1, 0, 0, 0}, 
{-u[1]^2 u[2] + u[1] u[2]^2 + u[1]^2 u[3] - u[1] u[2] u[3], -u[1]^2 + u[1] u[2] - u[2]^2 + u[2] u[3], -u[3], 1, 0, 0}, 
{-u[1]^2 u[2] u[3] + u[1] u[2]^2 u[3] + u[1]^2 u[3]^2 - u[1] u[2] u[3]^2 + u[1]^2 u[2] u[4] - u[1] u[2]^2 u[4] - u[1]^2 u[3] u[4] + u[1] u[2] u[3] u[4], -u[1]^2 u[2] + u[1] u[2]^2 - u[2]^2 u[3] + u[2] u[3]^2 + u[1]^2 u[4] - u[1] u[2] u[4] + u[2]^2 u[4] - u[2] u[3] u[4], -u[1]^2 + u[1] u[2] - u[2]^2 + u[2] u[3] - u[3]^2 + u[3] u[4], -u[4], 1, 0}, 
{-u[1]^2 u[2] u[3] u[4] + u[1] u[2]^2 u[3] u[4] + u[1]^2 u[3]^2 u[4] - u[1] u[2] u[3]^2 u[4] + u[1]^2 u[2] u[4]^2 - u[1] u[2]^2 u[4]^2 - u[1]^2 u[3] u[4]^2 + u[1] u[2] u[3] u[4]^2 + u[1]^2 u[2] u[3] u[5] - u[1] u[2]^2 u[3] u[5] - u[1]^2 u[3]^2 u[5] + u[1] u[2] u[3]^2 u[5] - u[1]^2 u[2] u[4] u[5] + u[1] u[2]^2 u[4] u[5] + u[1]^2 u[3] u[4] u[5] - u[1] u[2] u[3] u[4] u[5], -u[1]^2 u[2] u[3] + u[1] u[2]^2 u[3] + u[1]^2 u[3]^2 - u[1] u[2] u[3]^2 - u[1]^2 u[3] u[4] + u[1] u[2] u[3] u[4] - u[2]^2 u[3] u[4] + u[2] u[3]^2 u[4] + u[1]^2 u[4]^2 - u[1] u[2] u[4]^2 + u[2]^2 u[4]^2 - u[2] u[3] u[4]^2 + u[1]^2 u[2] u[5] - u[1] u[2]^2 u[5] + u[2]^2 u[3] u[5] - u[2] u[3]^2 u[5] - u[1]^2 u[4] u[5] + u[1] u[2] u[4] u[5] - u[2]^2 u[4] u[5] + u[2] u[3] u[4] u[5], -u[1]^2 u[2] + u[1] u[2]^2 - u[2]^2 u[3] + u[2] u[3]^2 - u[3]^2 u[4] + u[3] u[4]^2 + u[1]^2 u[5] - u[1] u[2] u[5] + u[2]^2 u[5] - u[2] u[3] u[5] + u[3]^2 u[5] - u[3] u[4] u[5], -u[1]^2 + u[1] u[2] - u[2]^2 + u[2] u[3] - u[3]^2 + u[3] u[4] - u[4]^2 + u[4] u[5], -u[5], 1}}
$\endgroup$
1
  • $\begingroup$ Thanks for the code! It made me realize that using $a_{i+1,i} = (i+1)^2$ gives the "Type B Stirling numbers" (oeis.org/A039755). $\endgroup$ Mar 19, 2022 at 1:41
9
$\begingroup$

Gjergji Zaimi's answer appears to completely address question 1, but that leaves question 2. On the assumption that OEIS is a good place to look for known matrices of combinatorial significance, I wrote a program to scan an offline copy of the OEIS sequence data for candidate $A$ or $B$ matrices. Unsurprisingly, most of them fall into a small number of families related to binomial coefficients or Stirling numbers. There are relatively few for which both the $A$ and $B$ matrices are present.

First, for completeness, OEIS sequence numbers for those directly related to the ones mentioned in the question, and moderately direct generalisations thereof.

  • Coefficient sequence $(s, s, s, \ldots)$: when $s = 1$ we get $A = \textrm{A007318}$, Pascal's triangle, and $B = \textrm{A130595}$, signed Pascal's triangle. When $s = 0$ we get $A=B=\textrm{A023531}$, which can be interpreted as the identity matrix. For $s = 2, 3, \ldots, 15$ the $A$ matrix is in OEIS, and it's also the $B$ matrix for the negated value of $s$. These sequences are A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467.

    We can generalise further to $(s, t, t, t, \ldots)$ and find a lot of triangles in OEIS:

     s   t   A matrix   B matrix   Comments
     -2 -4              A193735
     -2 -3              A193723    Matrix product A200139 (B matrix for s=-1, t=-2) * A007318 (A matrix for s=t=1)
     -1 -3              A136158
     -3 -2              A209149
     -1 -2              A200139
      1 -2   A251634    A251636
    -10 -1              A093645    (10,1) Pascal triangle
     -9 -1              A093644    (9,1) Pascal triangle
     -8 -1              A093565    etc.
     -7 -1              A093564
     -6 -1              A093563
     -5 -1              A093562
     -4 -1              A093561
     -3 -1              A093560
     -2 -1   A103316    A029653
     -1 -1   A130595    A007318
      0 -1              A097805
      1 -1   A112468    A112467
     10 -1   A164881
     -2  0              A156319    t=0 gives subdiagonal -s and all diagonals below it are zero
     -1  0   A097807    A097806
      1  0   A000012    A167374
      2  0   A130321    A251635
      3  0   A140303
      4  0   A262616
     -1  1   A112465    A112466
      0  1   A097805
      2  1   A055248
      3  1   A106516
    100  1   A164847
      1  2   A112857
      3  2   A112626
    

    There are a handful of other sequences which are $A$ or $B$ matrices for coefficient sequences which become constant after a small number of exceptional terms:

    Coefficients         A-matrix   B-matrix   Comments
    -1,-1,-5,-5,-5,...              A107310    Not many values given and I haven't tracked down the reference, so may be a false positive
    -2,-1,0,0,...                   A167684
    0,-1,0,0,...                    A167371
    0,1,0,0,...          A123110
    1,-1,0,0,...         A135839    A071022    B-matrix relates to cellular automata
    1,0,-1,0,0,...       A071023               Relates to cellular automata
    1,1,0,0,...          A193592
    1,0,1,1,...          A135225               Pascal's triangle augmented with left column of 1s
    1,2,3,3,3,...        A250118               Set partitions avoiding 12343
    1,2,3,4,4,...        A250119               Set partitions avoiding 123454
    
  • Coefficient sequence $(1, q, q^2, q^3, \ldots)$: these are the $q$-binomial coefficients. The $A$ matrices for $q=2, 3, \ldots, 24$ are A022166 to A022188, and for $q=25$ it's A173583. The $A$ matrix for $q=-1$ is A051159, although this property is hidden in the comments. The $A$ matrices for $q=-2, -3, \ldots, -24$ are in the range A015109 to A015151, with a few other sequences interleaved. The $B$ matrix for $q=2$ is A135950.

    There are also $B$ matrices for coefficients which are scaled by $\kappa = -q$ for $q=2,3,4$, respectively A108084, A173007, A173008.

    And there are some sequences which skip the $q$ term: i.e. the coefficient sequence is $(1, q^2, q^3, \ldots)$. For $q=2,3,4$ the $A$ matrix is A176242, A176243, A176244.

  • Coefficient sequence $(s, s+k, s+2k, s+3k, \ldots)$. With $s=k=1$ this is the Stirling pair $A = \textrm{A008277}$, $B = \textrm{A008275}$. A lot of members of this family are present: those which don't have other names are usually called something like "A generalised Stirling triangle".

       k   s   A matrix   B matrix   Comments
       1  -1    A105794    A105793
       1   0    A048993    A048994   Stirling numbers with different offset
       1   1    A008277    A008275   Stirling numbers
       1   2    A143494    A049444   2-Stirling numbers
       1   3    A143495    A049458   3-Stirling numbers
       1   4    A143496    A049459   etc.
       1   5    A193685    A049460
       1   6               A051338
       1   7               A051339
       1   8               A051379
       1   9               A051380
       1  10               A051523
      -1  -4               A143493   Unsigned 4-Stirling numbers of the first kind
      -1  -3               A143492   Unsigned 3-Stirling numbers of the first kind
      -1  -2               A136124 = A143491
      -1  -1               A130534   Unsigned Stirling numbers of the first kind
      -1   0               A132393   Unsigned Stirling numbers of the first kind
      -1   1               A094645
      -1   2               A094646
       2   1    A039755    A039757   B-analogs of Stirling numbers; A matrix is Stirling-Frobenius subset numbers of order 2
       2   2    A075497    A039683
      -2  -1               A028338   Stirling-Frobenius cycle numbers of order 2
       3   1    A111577              Galton triangle
       3   2    A225468              Stirling-Frobenius subset numbers of order 3
       3   3    A075498    A051141
      -3  -1               A286718
      -3  -2               A225470   Stirling-Frobenius cycle numbers of order 3
       4   1    A111578
       4   3    A225469              Stirling-Frobenius subset numbers of order 4
       4   4    A075499    A051142
      -4  -3               A225471   Stirling-Frobenius cycle numbers of order 4
       5   1    A166973
       5   5    A075500    A051150
       6   6    A075501    A051151
       7   7    A075502    A051186
       8   8    A075503    A051187
       9   1    A166979
       9   9    A075504    A051231
      10  10    A075505    A048176
    

    Making some minor changes to the first term yields $A$-matrix Stirling differences A269952 for $(0,2,3,4,\ldots)$, and $A$-matrix A137596 (matrix product of all-ones lower-triangular matrix and triangle of Stirling numbers of the second kind) for $(1,1,2,3,4,\ldots)$.

Other families which are less directly related (although by no means unrelated in all cases) to the ones explicitly mentioned in the question are:

  • Coefficient sequences based on squares, cubes, etc.

    • Squares $(1, 4, 9, \ldots)$ has $A$-matrix A036969, "central factorial numbers $T(2n,2k)$"; and $B$-matrix A204579.
    • Squares $(0, 1, 4, 9, \ldots)$ has $A$-matrix A269945, central factorial numbers $T(2n,2k)$ with a different offset.
    • Negated squares $(0, -1, -4, -9, \ldots)$ has $B$-matrix A269944, unsigned central factorial numbers $t(2k,2k)$.
    • Odd squares $(1, 9, 25, \ldots)$ has $A$-matrix A160562, "scaled central factorial numbers".
    • Negated odd squares $(-1, -9, -25, \ldots)$ has $B$-matrix A160563, "number of (n,k)-Riordan complexes".
    • Cubes $(1, 8, 27, \ldots)$ has $A$-matrix A098436, 3rd central factorial numbers or Stirling set numbers of order 3.
    • With zero, $(0, 1, 8, 27, \ldots)$ has $A$-matrix A269948 of the same 3rd central factorial numbers offset by one.
    • Negative cubes $(0, -1, -8, -27, \ldots)$ has $B$-matrix A269947, Stirling cycle numbers of order 3.
  • Alternating sequences.

    Coefficients    A-matrix   B-matrix   Comments
    0,-1,0,-1,...              A103633    Repeated stepped binomial coefficients
    0,1,0,1,...     A103631               abs(q-Stirling2) for q=-1
    1,0,1,0,...     A065941               q-Stirling2 for q=-1; repeated stepped signed binomial coeffs
    1,2,1,2,...     A140068
    2,1,2,1,...     A140069               Binomial transform of A135225 (A-matrix of 1,0,1,1,...)
    1,-2,1,-2,...   A140166
    2,-1,2,-1,...   A140168
    1,3,1,3,...     A140070
    3,1,3,1,...     A140071
    

    Also near-alternating sequences with early exceptions:

    1,1,-1,1,-1,... A207974                Has interpretation in terms of binary strings
    1,1,0,1,0,...   A194005                Likewise; also "companion to A103631" (A-matrix of 0,1,0,1,...).
    
  • The sequence $(1,3,7,\ldots,2^k-1,\ldots)$ gives $A$-matrix A139382, $q$-Stirling2 with $q=2$.

  • Sequences $\binom{k+\alpha}{\alpha}$ or $\alpha! \binom{k+\alpha}{\alpha}$ give a few hits:

    Coefficients            A-matrix   B-matrix   Comments
    1,3,6,10,...            A080248
    2,6,12,20,...           A071951    A130559    Legendre-Stirling numbers
    0,2,6,12,20,...                    A129467    ... with different offset
    1,4,10,20,...           A080249
    6,24,60,120,...         A089504
    24,120,360,840,...      A090215
    120,720,2520,6720,...   A090217
    
  • Repeating coefficients gives other Stirling-related sequences:

    0,1,1,2,2,3,3,...       A246118               Set partitions with certain constraints
    1,1,2,2,3,3,...         A256161               Same with different offset
    0,-1,-1,-2,-2,...                  A246117    Parity-preserving permutations by number of cycles
    
  • Other sequences based on combinatorial coefficient sequences:

    Coefficients                A-matrix   B-matrix
    1,1,2,3,5,... (Fibonacci)   A111669
    1,1,3,5,11,... (Jacobsthal) A114163
    1,1,2,6,24,... (factorials)            A136457
    -1,2,-3,4,-5,6,...                     A140956    Rows are coefficients of alternating factorial polynomial
    
  • And there's a handful based on number-theoretic sequences:

    Coefficients              A-matrix   B-matrix
    2,3,5,7,... (primes)      A124960    A070918
    -1,-2,-4,-6 (1-p)                    A096294    Fraction of positive integers with exactly k of the first n primes as divisors
    1,-1,-1,0,-1,1,... (mu)   A124961
    -1,0,0,0,-9,0,0,-15,...              A109409    Coeffs of product of (x+i) for odd non-prime i
    
$\endgroup$
3
  • $\begingroup$ One more (unless I missed it on your list): plugging into $[1]_q$, $[2]_q$, etc gives so-called “$q$-Stirling numbers” $\endgroup$ Mar 22, 2022 at 11:32
  • 1
    $\begingroup$ @SamHopkins, $q$-Stirling2 is in the list for $q=-1$ and $q=2$. I was surprised not to see at least $q=3$ in there too. Since this is based on searching OEIS, it only contains numeric values rather than generic $q$-analogues. There may also be $q$-analogues for some of the other sequences (e.g. Stirling-Frobenius numbers, Legendre-Stirling numbers). $\endgroup$ Mar 22, 2022 at 11:37
  • 1
    $\begingroup$ One reason for there being so many entries in the families $(s,t,t,t,\ldots)$ and $(s,s+k,s+2k,s+3k,\ldots)$ is probably that these are precisely the matrices generated in this way which are respectively ordinary and exponential Riordan arrays. $\endgroup$ Mar 26, 2022 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.