Welcome to our community

Be a part of something great, join today!

Problem Of The Week # 340 - Feb 13, 2019

Status
Not open for further replies.
  • Thread starter
  • Moderator
  • #1

Euge

MHB Global Moderator
Staff member
Jun 20, 2014
1,925
Here is this week's POTW:

-----
Given a nonempty set $A$ of positive integers, let $B$ be a subset of $A$ such that $\dfrac{m}{2}\notin A$ whenever $m\in B$. If $n$ is a positive number, prove that the partitions of $n$ into distinct parts selected from $A$ is equinumerous with the partitions of $n$ into parts selected from $B$.

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Moderator
  • #2

Euge

MHB Global Moderator
Staff member
Jun 20, 2014
1,925
No one answered this week's problem. You can read my solution below.


Let $A(n)$ represent the number of partitions of $n$ into distinct parts selected from $A$, and let $B(n)$ represent the number of partitions of $n$ into parts selected from $B$. The generating function of $A(n)$ is
$$\prod_{j \in A} (1 + q^j) = \prod_{j \in A} \frac{1-q^{2j}}{1-q^j} = \prod_{j\in A\setminus 2A} \frac{1}{1-q^j} = \prod_{j \in B} \frac{1}{1-q^j}$$ The last product is the generating function for $B(n)$. Hence, $A(n) = B(n)$ for all $n \ge 0$, as desired.
 
Status
Not open for further replies.