1

In the proof of No-Free-Lunch Theorem from the book Understanding Machine Learning: From Theory to Algorithms Cambridge University Press, p.37-38, the author wrote:

Let $C$ be a subset of the domain set $\mathcal{X}$ of size $2m$.

... There are $k = (2m)^{m}$ possible sequences of m examples from $C$.

I don't understand why the author came up with the number $k=(2m)^{m}$, my calculation turns out to be:

$$ \begin{align}C(2m, m)& = \frac{(2m)!}{m!(2m-m)!} \\& =\frac{(2m)!}{m!m!} \end{align}$$

And it doesn't come any close to $(2m)^{m}$ at all?

Tran Khanh
  • 177
  • 6

1 Answers1

2

Your expression is "how many ways can I choose m unique elements from a list of 2m unique elements"

The author's expression is "how many unique sequences of length m can I construct from a list of 2m unique elements"

Let's take a small example. With m=2, and 2m elements {A, B, C, D}.

Your expression evaluates as 6, and those are the selections. AB, AC, AD, BC, BD, CD. No repetition, no permutations.

The author's expression evaluates as 16, and the sequences are AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD. Repetition included, all permutations separate.

Neil Slater
  • 33,739
  • 3
  • 47
  • 66