-2
$\begingroup$

In proof that algorithm output at most $2^{\varepsilon n}$ families. There are $\beta_{k-1} n$ sets along any path ever added to families. Also, there are $kn/\alpha$ families along any path. I can not understand why in this case there are $\sum_{r=1}^{\frac{kn}{\alpha}}$${\beta_{k-1} n}\choose{kn/\alpha}$ paths.

New contributor
Julia is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ You missed out on the important property that the $kn/\alpha$ families along a path refers only to the number of families created by adding petals. $\endgroup$ – Kristoffer Arnsfelt Hansen May 21 at 21:04
  • $\begingroup$ My assumption is folowing: the number of path can be find by recursion T(s,p) = T(s-1,p-1)+T(s-1,p) . s is numer of sets along any path, p is petals steps. If we add the heart we do one heart step(only one set) and number of remaining paths is T(s-1,p). If we add petals in worst case it can be only one set and number of remaining paths is T(s-1,p-1). Alltogether T(s,t)=T(s-1,p-1)+T(s-1,p). It has identity with binomial coeffitient. ${{m}\choose{b}}$, da ${{m-1}\choose{b-1}} + {{m-1}\choose{b}} = {{m}\choose{b}} $. I can't understand why the sum in front of ${\beta_{k-1} n}\choose{kn/\alpha}$ $\endgroup$ – Julia May 23 at 8:19
  • $\begingroup$ Imagine the recursion tree as a binary tree where at a given branching node the heart is added in the left child and the petals are added in the right child. A leaf of the tree is uniquely described by the root-to-leaf path which in turn is described by the the sequence of left and right children followed. Such a path is of length at most $\beta_{k-1}n$ and follows the right child at most $kn/\alpha$ times. $\endgroup$ – Kristoffer Arnsfelt Hansen yesterday

Browse other questions tagged or ask your own question.