Combinatorial puzzle

Question

Let $\pi$ be a set of ordered pairs of natural numbers, $\pi = \lbrace (n_1,n_2) \dots (n_k ,n_{k+1})\rbrace$ (a "set of pairs").

Let $\cup \pi$ be the set $\lbrace n_1 n_2 \dots n_k n_{k+1}\rbrace$ of numbers occuring in $\pi$.

Define a set of pairs to be minimal when $\cup \pi$ starts with 1 and has no gaps, i.e. when

• $1 \in \cup \pi$

• $n \in \cup \pi \wedge (\exists m \in \cup \pi)\ m > n \rightarrow n+1 \in \cup \pi$

There are three minimal sets of pairs of size 1: $\lbrace (1,1)\rbrace$, $\lbrace (1,2)\rbrace$, $\lbrace (2,1)\rbrace$.

There are 22 36 minimal sets of pairs of size 2, among others

$\lbrace (1,1)(1,2)\rbrace$ $\lbrace (1,1)(2,1)\rbrace$ $\lbrace (1,1)(2,2)\rbrace$ $\lbrace (1,1)(2,3)\rbrace$ $\lbrace (1,1)(3,2)\rbrace$

$\lbrace (1,2)(2,1)\rbrace$ $\lbrace (1,2)(2,2)\rbrace\dots\lbrace (1,2)(4,3)\rbrace$

$\lbrace (2,1)(2,2)\rbrace$ $\lbrace (2,1)(1,3)\rbrace\dots\lbrace (2,1)(4,3)\rbrace$

How many minimal sets of pairs of size $n$ are there?

Is there a closed formula? A generating function? An OEIS sequence?

Answer 1

There are $\binom{m^2}{n}$ unrestricted sets of pairs of size $n$ with maximum element no greater than $m$.

To exclude the non-minimal sets, we can use use inclusion-exclusion to give the number of minimal sets $$ M_n \;=\; \sum_{m=\lceil\sqrt{n}\rceil}^{2n} \sum_{i=0}^{\lfloor m-\sqrt{n}\rfloor} (-1)^i \binom{m}{i} \binom{(m-i)^2}{n}. $$ This gives the sequence 1, 3, 36, 744, 21606, 807912, 36948912, 1997801520, ... which seems to match A173217 in OEIS. Here are the 36 minimal sets of size 2:

       {11 12}   {11 21}   {11 22}   {12 21}   {12 22}   {21 22}
       {11 23}   {11 32}   {12 13}   {12 23}   {12 31}   {12 32}    
       {12 33}   {13 21}   {13 22}   {13 23}   {13 32}   {21 23}    
       {21 31}   {21 32}   {21 33}   {22 31}   {23 31}   {31 32} 
       {12 34}   {12 43}   {13 24}   {13 42}   {14 23}   {14 32}    
       {21 34}   {21 43}   {23 41}   {24 31}   {31 42}   {32 41}

Minimal sets of size $n$ are in bijection with labelled digraphs with $n$ edges and no vertices of degree zero, in which loops are permitted but not duplicate edges. Here are the digraphs with 2 edges:

$\qquad\qquad$

According to OEIS, the sequence has o.g.f. $$ M(z)\;=\;\sum_{k=0}^{\infty}2^{-k-1}(1+z)^{k^2} $$ and hence $$ M_n\;=\;\sum_{k=0}^{\infty}2^{-k-1}\binom{k^2}{n}. $$ At present, I can't see how to prove that the OEIS o.g.f. is correct for the number of minimal sets (or digraphs).