Integer partitioning

507 Views Asked by At

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?

2

There are 2 best solutions below

0
On BEST ANSWER

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}$.

2
On

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\;.$$