11
$\begingroup$

Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity.

Question. Let $n!!=1!2!\cdots n!$. Is the following true? $$\det\left[I_{i+j}\right]_{i,j=0}^n=n!!$$

Improve this question
$\endgroup$
9
  • $\begingroup$ Have you check it for small $n$? $\endgroup$
    – Fedor Petrov
    Commented Feb 7, 2017 at 14:22
  • 2
    $\begingroup$ It is indeed mentioned in one of the comments of oeis.org/A000085 that "The Hankel transform of this sequence is A000178 (superfactorials)." But without source. :( $\endgroup$
    – Wolfgang
    Commented Feb 7, 2017 at 14:45
  • 1
    $\begingroup$ This article cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html mentions that A000085 is one of seven found sequences with the same Hankel transform. $\endgroup$
    – Wolfgang
    Commented Feb 7, 2017 at 14:59
  • 2
    $\begingroup$ Is there a Gessel-Lindelof-Viennot proof of this? $\endgroup$
    – Per Alexandersson
    Commented Feb 7, 2017 at 15:58
  • 2
    $\begingroup$ It suffices to prove that $a(n,0)=I_n$ if $a(n,j)$ is defined by $a(n,j)=a(n-1,j-1)+a(n-1,j)+(j+1)a(n-1,j+1)$ with $a(n,-1)=0$ and $a(0,j)=[j=0]$. $\endgroup$
    – Johann Cigler
    Commented Feb 7, 2017 at 17:04

1 Answer 1

Reset to default
7
$\begingroup$

As in arXiv:0902.1650 it suffices to show that $a(n,0)=I_n$ if $a(n,j)$ satisfies $a(n,j)=a(n-1,j-1)+a(n-1,j)+(j+1)a(n-1,j+1)$ with $a(n,-1)=0$ and $a(0,j)=[j=0]$. But it is easily verified that $a(n,j)=\binom{n}{j}I_{n-j},$ because then the above recursion reduces to $I_n=I_{n-1}+(n-1)I_{n-2}.$

Edit: Another proof along the same lines follows immediately from formula (2.7) in this paper entitled Involutions and their progenies: $\sum_k\binom{n}{k}I_{n-k} \binom{m}{k}I_{m-k} k!=I_{m+n}.$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .