scientific article; zbMATH DE number 1792637

From MaRDI portal
Publication:4552229





The independent domination number \(\alpha '(D)\) of a digraph \(D=(V,E)\) is the minimum cardinality of a set \(X\subset V\) such that (i) \(xy\in E\) for no \(x,y\in X\) and (ii) for every \(y\in V\backslash X\) there exists \(x\in X\) for which \(xy\in E\). Binary trees are rooted directed plane trees in which every vertex has 0 or 2 children. It is well known that the set \({\mathcal T}_n\) of binary trees with \(2n+1\) vertices has \(t_n={2n\choose n}/(n+1)\) elements. The author proves that the expected value \(\mu (2n+1)\) of \(\alpha '(T)\) over \({\mathcal T}_n\) is \(\sum (k+1)2^k(n)_k/(2n)_k\) and that \(\mu (2n+1)/(2n+1)\rightarrow 1/2\). Here \((n)_k=n(n-1)\cdots (n-k+1)\) and \(\sum \) runs over even \(k\) with \(0\leq k\leq n\). The formula \[ \sum _{n\geq 0}\mu (2n+1)t_nx^{2n+1}= 2x\cdot (1-4x^2)^{-1/2}\cdot (1+(1-4x^2)^{1/2})^{-1}\cdot (2-(1-4x^2)^{1/2})^{-1} \] is derived.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4552229)