6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It appears that there are actually 36 minimal sets of size 2 (and 744 of size 3), and that the sequence matches A173217 in OEIS. $\endgroup$ – David Bevan Apr 19 '13 at 10:43
6
$\begingroup$

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$ digraphs

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).

$\endgroup$
  • $\begingroup$ I forgot to say: wonderful! $\endgroup$ – Hans-Peter Stricker Apr 25 '13 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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