3
$\begingroup$

Suppose we have an integer $n$. I we want to partition the integer in the form of $2$ and $3$ only; i.e., $10$ can be partitioned in the form $2+2+2+2+2$ and $2+2+3+3$.

So, given an integer, how to calculate the total number of ways of doing such partitions and how many $2$'s and $3$'s are there in each of the partitions?

$\endgroup$
  • $\begingroup$ Is the ordering of the 2s and 3s relevant? Or are we just looking at quantity of each? Can you add your results for numbers up to, say, 10? $\endgroup$ – Joffan Jun 5 '15 at 18:56
  • $\begingroup$ @Joffan only quantity. $\endgroup$ – Anuj Garg Jun 15 '15 at 4:16
3
$\begingroup$

For even $n$, the number of $3$ in each partition is even. So, let $2k$ be the largest number of $3$ in the partition of even $n$, i.e. $$3\cdot 2k\le n\lt 3(2k+2)\Rightarrow k\le \frac{n}{6}\lt k+1\Rightarrow k=\left\lfloor\frac n6\right\rfloor.$$ Hence, the number of partitions of $\color{red}{\text{even}\ n}$ is $\color{red}{\left\lfloor\frac{n}{6}\right\rfloor+1}$ (note that the +1 comes from the case $k=0$).

For odd $n$, the number of $3$ in each partition is odd. So, let $2k-1$ be the largest number of $3$ in the partition of odd $n$, i.e. $$3(2k-1)\le n\lt 3(2k+1)\Rightarrow k\le \frac{n+3}{6}\lt k+1\Rightarrow k=\left\lfloor\frac{n+3}{6}\right\rfloor.$$ Hence, the number of partitions of $\color{red}{\text{odd}\ n}$ is $\color{red}{\left\lfloor\frac{n+3}{6}\right\rfloor}$.

$\endgroup$
2
$\begingroup$

The number of partitions of $n$ into parts in the set $\{2,3\}$ is the coefficient of $x^n$ in

$$\left(1+x^2+x^4+x^6+\ldots\right)\left(1+x^3+x^6+x^9+\ldots\right)=\frac1{(1-x^2)(1-x^3)}\;.$$

For $n=10$, for instance, we can ignore powers of $x$ higher than $10$, so we need only consider

$$(1+x^2+x^4+x^6+x^8+x^{10})(1+x^3+x^6+x^9)\;,$$

and by inspection the $x^{10}$ term is

$$x^4\cdot x^6+x^{10}\cdot x^0=2x^{10}\;:$$

the two partitions of $10$ that you listed in the question are the only ones.

However, we can do better. According to Wikipedia, the number of partitions of $n$ into parts of sizes $1,2$, and $3$ is the integer nearest to $\frac1{12}(n+3)^2$, i.e.,

$$\left\lfloor\frac{(n+3)^2}{12}+\frac12\right\rfloor\;;$$

call this $f(n)$, and let $g(n)$ be the number of partitions of $n$ into parts of size $2$ and $3$. Each partition of $n$ with parts in $\{1,2,3\}$ is a partition of some $k\le n$ into parts in $\{2,3\}$ together with some number of unit parts, so

$$f(n)=\sum_{k=2}^ng(k)\;,$$

and

$$g(n)=f(n)-f(n-1)=\left\lfloor\frac{(n+3)^2}{12}+\frac12\right\rfloor-\left\lfloor\frac{(n+2)^2}{12}+\frac12\right\rfloor\;.$$

As a quick check, for $n=10$ this becomes

$$\left\lfloor\frac{(13)^2}{12}+\frac12\right\rfloor-\left\lfloor\frac{(12)^2}{12}+\frac12\right\rfloor=14-12=2\;.$$

$\endgroup$
  • $\begingroup$ And how to calculate number of 2's and number of 3's in each partition? $\endgroup$ – Anuj Garg Jun 6 '15 at 4:15
  • $\begingroup$ In combinatorics what we call this type of approach? $\endgroup$ – Anuj Garg Jun 15 '15 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.