MHB Can You Match Partitions from Set A and Subset B?

  • Thread starter Thread starter Euge
  • Start date Start date
Euge
Gold Member
MHB
POTW Director
Messages
2,072
Reaction score
245
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 https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
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.
 
Back
Top