Graphical basis partitions (Q1268118)

A sequence \(\lambda= (\lambda_1,\dots,\lambda_t)\) with all its `parts' \(\lambda_i\) natural and such that \(\lambda_1\geq\cdots\geq \lambda_t\) together with \(|\lambda|= \lambda_1+\cdots+ \lambda_t= n\), is called a partition of \(n\) and denoted \(\lambda\vdash n\). Let \({\mathfrak P}(n)\) be the set of all partitions of \(n\) and define \({\mathfrak P}(0)= \{\widehat 1\}\) where \(\widehat 1\) is the empty partition. Further, let \(p(n)= |{\mathfrak P}(n)|\). A partition \(\lambda\vdash n\) is called graphical if there exists a simple (undirected) graph with degree sequence \(\lambda\). Denote by \({\mathfrak G}(n)\) the set of all graphical partitions of an (even) number \(n\), and let \(g(n)= |{\mathfrak G}(n)|\). There is known an open question posed by H. Wilf, whether the limit \(\lim_{n\to\infty} {g(n)\over p(n)}\) exists and equals \(0\). However, it is known that \(\varlimsup_{n\to\infty} {g(n)\over p(n)}\leq{1\over 4}\); see \textit{C. Rousseau} and \textit{F. Ali} [Congr. Numerantium 104, 150-160 (1994; Zbl 0836.05006)]. The authors investigate this ratio using the Nash-Williams criterion for a partition \(\lambda\vdash n\) to be graphical. For a given partition \(\lambda= (\lambda_1,\dots, \lambda_t)\) let \(\lambda^*= (\lambda^*_1,\dots, \lambda^*_s)\) be its conjugate partition (i.e., \(s=\lambda_1\) and \(\lambda^*_j\) is defined as the number of dots in the \(j\)th column of the Ferrers diagram for \(\lambda\)) and let \(d\) denote the length of a side of the Durfree square in the Ferrers diagram for \(\lambda\). The rank vector of \(\lambda\) has been defined by \textit{H. Gupta} [Fibonacci Q. 16, 548-552 (1978; Zbl 0399.10017)] as the vector \(\overline r(\lambda)= (r_1,\dots, r_d)\) with \(r_i= \lambda_i- \lambda^*_i\) \((i= 1,\dots, d)\). According to the Nash-Williams criterion, for a partition \(\lambda\) to be graphical it is necessary and sufficient that \(\sum^k_{i= 1}(r_i+ 1)\leq 0\) for each \(k\in \{1,2,\dots, d\}\). A partition \(\lambda\in{\mathfrak P}(n)\) is called basic if \(|\lambda|= \min\{|\pi|: \pi\in{\mathfrak P}(n)\) and \(\overline r(\pi)=\overline r(\lambda)\}\). H. Gupta (loc. cit.) has shown that among all partitions with the same rank vector \(\overline r= (r_1,\dots, r_d)\) there exists just one with minimum weight; denote it by \(\pi(\overline r)\). The weight of \(\pi(\overline r)\) is given by \(n(\overline r)= d^2+ d\cdot| r_d|+ \sum^{d- 1}_{i= 1} i\cdot| r_i- r_{i+1}|\). The number of partitions in \({\mathfrak P}(n)\) having a given rank vector \(\overline r\), equals \(p(m,d)\), where \(m={1\over 2}(n-|\pi|)\) and \(p(u,v)\) denotes the total number of partitions of \(n\) into \(u\) parts of size at most \(v\). Denote by \({\mathfrak B}(n)\) the set of all basic partitions of \(n\) and let \({\mathfrak H}(n)\) be the subset of graphical partitions in \({\mathfrak B}(n)\). Further, let \(b(n)= |{\mathfrak B}(n)|\) and \(h(n)=|{\mathfrak H}(n)|\). In the paper a recurrence for calculating \(h(n)\) is found. Numerical experiments \((n\leq 200)\) have the authors given some new ground to pose the question whether the limits for both ratios \({h(n)\over b(n)}\) and \({g(n)\over p(n)}\) exist when \(n\to\infty\) and they both are equal to \(0\). To get insight into the asymptotic behaviour of these ratios, the authors' advice is to use the corresponding generating functions. The authors also show how to generate efficiently the set \({\mathfrak B}(n)\) and how to modify their algorithm to get the subset \({\mathfrak H}(n)\).