Answers.Body: <p>Your expression is &quot;how many ways can I choose m unique elements from a list of 2m unique elements&quot;</p>
  <p>The author's expression is &quot;how many unique sequences of length m can I construct from a list of 2m unique elements&quot;</p>
  <p>Let's take a small example. With m=2, and 2m elements {A, B, C, D}.</p>
  <p>Your expression evaluates as 6, and those are the selections. AB, AC, AD, BC, BD, CD. No repetition, no permutations.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-10T07:31:46.383Z
Answers.LastActivityDate: 2023-10-10T07:31:46.383Z
Answers.UserDisplayName: Neil Slater
Body: <p>In the proof of <em>No-Free-Lunch</em> Theorem from the book <em>Understanding Machine Learning: From Theory to Algorithms</em> Cambridge University Press, p.37-38, the author wrote:</p>
  <blockquote>
  <p>Let <span class="math-container">$C$</span> be a subset of the domain set <span class="math-container">$\mathcal{X}$</span> of size <span class="math-container">$2m$</span>.</p>
  <p>...
  There are <span class="math-container">$k = (2m)^{m}$</span> possible sequences of m examples from <span class="math-container">$C$</span>.</p>
  </blockquote>
  <p>I don't understand why the author came up with the number <span class="math-container">$k=(2m)^{m}$</span>, my calculation turns out to be:</p>
  <p><span class="math-container">$$
  \begin{align}C(2m, m)&amp; = \frac{(2m)!}{m!(2m-m)!}
  \\&amp; =\frac{(2m)!}{m!m!}
  \end{align}$$</span></p>
  <p>And it doesn't come any close to <span class="math-container">$(2m)^{m}$</span> at all?</p>
  
Tags: <computational-learning-theory><sample-complexity><no-free-lunch-theorems>
Title: No-Free-Lunch: Calculation of the number of sequences of examples of size $m$
UserDisplayName: Tran Khanh
ThreadText: # No-Free-Lunch: Calculation of the number of sequences of examples of size $m$
  
  (Asked by: username_0 on 2023-10-10)
  
  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?
  
  **Tags:** computational-learning-theory, sample-complexity, no-free-lunch-theorems
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-10-10. Score: 2 | Accepted answer
  
  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.
  
  
  ---
  
  