No label defined (Q4552229)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1792637
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1792637 |
Statements
29 August 2002
0 references
domination number
0 references
independent set
0 references
binary tree
0 references
generating function
0 references
0.9593526
0 references
0.95649207
0 references
0.95334685
0 references
0.9262742
0 references
0.9175796
0 references
0.9142368
0 references
0.9083306
0 references
0.89908826
0 references
0.8974453
0 references
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.
0 references