Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Suppose $a,b,c,d$ are positive integers and $abcd=2^8\cdot 3^8$.
We consider permutations of an $(a,b,c,d)$ solution identical.
For example, solutions $(1,1,1,2^8\cdot 3^8),(1,1,2^8\cdot 3^8,1), (1,2^8\cdot 3^8,1,1), (2^8\cdot 3^8,1,1,1)$ are considered equivalent.
How many solutions $(a,b,c,d)$ are there?
Up to ordering, there are $15$ distinct ways to partition $8$ into the sum of $4$ digits using only the numbers $\{0,\ldots,8\}$. Using a simple $4$-digit sequence to denote these partitions we have: $$ \begin{array}{ccccc} 0008 & 0017 & 0026 & 0035 & 0044\\ 0116 & 0125 & 0134 & 0224 & 0233\\ 1115 & 1124 & 1133 & 1223 & 2222 \end{array} $$ So if I choose a partition of the powers of $2$ and a partition of the powers of $3$, we would like to know how many distinct ways can I combine them in our desired product. Let's illustrate this with the choices of $0116$ for the $2$'s and $0026$ for the $3$'s. To count this, we fix the order of the $2$'s and permute the order of $3$'s in each of the possible $12$ distinct ways: $$ \begin{align*} 0116 \cdot 0026&=(00)(10)(12)(66)=2^03^0\cdot2^13^0\cdot2^13^2\cdot2^63^6\\ 0116 \cdot 0206 &= (00)(12)(10)(66) ~~(duplicate)\\ 0116 \cdot 2006 &= (02)(10)(10)(66) \\ 0116 \cdot 0062 &= (00)(10)(16)(62) \\ 0116 \cdot 0260 &= (00)(12)(16)(60) \\ 0116 \cdot 2060 &= (02)(10)(16)(60) \\ 0116 \cdot 0602 &= (00)(16)(10)(62) ~~(duplicate)\\ 0116 \cdot 0620 &= (00)(16)(12)(60) ~~(duplicate)\\ 0116 \cdot 2600 &= (02)(16)(10)(60) ~~(duplicate)\\ 0116 \cdot 6002 &= (06)(10)(10)(62) \\ 0116 \cdot 6020 &= (06)(10)(12)(60) \\ 0116 \cdot 6200 &= (06)(12)(10)(60) ~~(duplicate) \end{align*} $$ and we see that there are $7$ distinct permutations of the powers of $3$ that yield distinct products equal to $2^8\cdot 3^8$.
Calculating this for each of the $225$ possible combinations of powers of $2$ and $3$, this brute force method gives $1297$ distinct products. This approach isn't as daunting as it seems at first. Combinatorially speaking, there are only $5$ distinct types of products based on the different fixed patterns of the powers of $2$: $$ xxxx\cdot\text{ all permutations (1 of these) which produces 15 products each}\\ xxxy\cdot\text{ all permutations (2 of these) which produces 41 products each}\\ xxyy\cdot\text{ all permutations (2 of these) which produces 55 products each}\\ xyyz\cdot\text{ all permutations (8 of these) which produces 95 products each}\\ wxyz\cdot\text{ all permutations (2 of these) which produces 165 products each.} $$ Thus we have $$ 1\cdot 15+2\cdot 41+2\cdot 55+8\cdot 95+2\cdot 165=1297 $$ distinct products.
If $a_i=2^{x_i}\cdot 3^{y_i}$ then the $x_i$ as well as the $y_i$ form a partition of $8$ into four parts $\geq0$. There are $15$ such partitions. We can sort these $15$ partitions into five types according to the multiplicities of the occurring sizes as follows: $$\eqalign{1{\rm\ of\ type\ 1}:\quad &2222\cr 2{\rm\ of\ type\ 2}:\quad &8000, 5111\cr 2{\rm\ of\ type\ 3}:\quad &4400, 3311\cr 8{\rm\ of\ type\ 4}:\quad &7100, 6200, 5300, 6011, 4211, 4022, 3122, 2033\cr 2{\rm\ of\ type\ 5}:\quad &5210, 4310\cr}\tag{1}$$ We now have to determine for each choice of two types $j$ and $k$ the number $q_{jk}$ of different quadruples $(a_1,a_2,a_3,a_4)$ that can be formed by a partition of type $j$ used with base $2$ and a partition of type $k$ used with base $3$. This has to be done "by hand". The symmetric matrix $Q=\bigl[q_{jk}\bigr]$ defined in this way looks as follows: $$Q=\left[\matrix{ 1&1&1&1&1 \cr 1&2&2&3&4 \cr 1&2&3&4&6 \cr 1&3&4&7&12 \cr 1&4&6&12&24 \cr}\right]\ .$$ Let $s=[1\ 2\ 2\ 8\ 2]$ be the vector listing the cardinalities of the five types in $(1)$. Then the total number $N$ of quadruples of the described kind is given by $$N=s\>Q\>s'=1297\ .$$
The fundamental theorem of arithmetic tells us that each $a,b,c,d$ is of the form $2^n \cdot 3^m$. Consequently, $$abcd = 2^{n_a + n_b + n_c + n_d} \cdot 3^{m_a + m_b + m_c + m_d} = 2^8 \cdot 3^8.$$ The problem is reduced to finding non-negative integers $n_i$ and $m_i$ such that the sum of the $n_i = 8$, and the sum of the $m_i = 8$.
To eliminate permutations of $a,b,c,d$, let us say without loss of generality that $n_a \geq n_b \geq n_c \geq n_d$ and that in the case $n_i = n_{i+1}$, we require that $m_i \geq m_{i+1}$. i.e. we join the digits $n$ and $m$ and order the numbers $n_i m_i$ from highest to lowest; highest assigned to $a$ and lowest assigned to $d$. With these constraints, we need only count the number of choices for $n_i,m_i$.
First, take a look at this answer for an understanding of how we partition an integer $n$ into $k$ non-negative integers up to permutation of the parts. (Although I believe the recurrence relations here are written incorrectly! I've used another source for my formula.) These are called partitions. I'll denote this $p_0(k,n)$ to distinguish it from the usual notion of a partition consisting of only positive integers.
Note that a composition of an integer is the same as a partition, except that permutations are not considered equivalent.
On a case-by-case basis, I'll go through the possibilities for $(n_a,n_b,n_c,n_d)$ and reason about the corresponding choices for $m_i$. There are essentially only five cases.
$$\begin{aligned} && \text{Choices for }n_i && \text{#Choices for }m_i\\ n_a < 2 : && \textrm{no solution} && \textrm{no solution}\\ n_a = 2 : && (2,2,2,2) && p_0(4,8) && \text{The problem reduces to partitioning } 8\\ n_a = 3 : && (3,3,2,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j) && \text{Choose } j=(m_a+m_b)\text{, and then }(m_c,m_d)\\ &&(3,3,1,1) && \sum_{j=0}^8 p_0(2,j) \cdot p_0(2,8-j) && \text{Choose } j= (m_a+m_b)\\ &&(3,2,2,1) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 4 : && (4,4,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot p_0(2,8-j)\\ &&(4,3,1,0) && \frac{(8+4-1)!}{(4-1)!8!} && \text{Choose any composition of }8\\ &&(4,2,2,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ &&(4,2,1,1) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 5 : && (5,3,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ &&(5,2,1,0) && \frac{(8+4-1)!}{(4-1)!8!}\\ &&(5,1,1,1) && \sum_{j=0}^8 p_0(3,j) && \text{Choose } j=(m_b+m_c+m_d)\\ n_a = 6 : && (6,2,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ &&(6,1,1,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 7 : && (7,1,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 8 : && (8,0,0,0) && \sum_{j=0}^8 p_0(3,j) \end{aligned}$$
Adding these together, there are $1297$ choices for $a,b,c,d$ up to permutation.
Let me explain where each of these terms comes from.
$$(2,2,2,2): \quad p_0(4,8)$$
In this case, the $n_i$ are equal and so by the rules I set out at the top, we must order the $m_i$ fro highest to lowest. Consequently, we are looking for the number of unordered sums of four integers $m_i$ which make $8$. This is equal to $p_0(4,8)$.
$$(3,3,2,0): \quad \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)$$
First, we may choose the sum $(m_a+m_b)$. Since $n_a = n_b$, we have no say in how these first two $m_i$ are ordered. We must order them from highest to lowest. So we have $p_0(j,2)$ choices given that we want them to sum to $j$. After having chosen one of these, we may choose $m_c$ and $m_d$ however we please so that they sum to $8-j$. There are $1+8-j$ ways to do this.
$$(4,4,0,0): \quad \sum_{j=0}^8 p_0(2,j) \cdot p_0(2,8-j)$$
In this case, we have two pairs of $n_i$ which are equal. This means we have no say over how the corresponding pairs of $m_i$ are ordered, though we may still choose the unordered sums. First, choose what $m_a+m_b$ will sum to by picking a $j$. Then we pick which unordered sum we want to yield $m_a+m_b = j$, giving us $p_0(2,j)$ choices. After that, we still have $8-j$ left to distribute to $m_c+m_d$, again with no say over their ordering. So we have $p_0(2,8-j)$ choices for a particular $j$.
$$(4,3,1,0): \quad \frac{(8+4-1)!}{(4-1)!8!}$$
Here, each $n_i$ is distinct and so there is no ordering imposed on the $m_i$. We may choose any combination, in any order, which yields a sum of $8$.
$$(5,1,1,1): \quad \sum_{j=0}^8 p_0(3,j)$$
Because three of the $n_i$ are identical, we have no say in the ordering of their corresponding $m_i$; only the sum of $m_b+m_c+m_d$. For a given sum $j$, we have $p_0(3,j)$ such choices. A choice of $j$ obviously fixes $m_a$ too.
I'd be interested to see if there's a general formula for partitioning tuples, as this problem is equivalent to partitioning $(8,8)$ into an unordered sum of $2$-tuples.
Number of non-identical solutions is $1297$. Let's solve it!
$abcd = 2^{n_a + n_b + n_c + n_d} \cdot 3^{m_a + m_b + m_c + m_d} = 2^8 \cdot 3^8$. We need number of solutions in the form $a\ge b \ge c \ge d$. In this case there is no identical solution. By the distribution principle, number of solutions of the system $n_a + n_b + n_c + n_d=8$, $m_a + m_b + m_c + m_d=8$ is $\dbinom{11}{3}^2=27225$. But this is so big for us. Because it has some identical solutions.
1. Case: Solutions in the form $(a,a,a,b)$ and $a \ne b$. \begin{array}{lcr} 3n_a + n_b & = & 8 \\ 3m_a +m_b & = & 8 \end{array} Solutions $(n_a,n_b)=(0,8),(1,5),(2,2)$ and $(m_a,m_b)=(0,8),(1,5),(2,2)$. There are $3\cdot 3 =9$ solutions. But for $(n_a,n_b)=(m_a,m_b)=(2,2)$, we find $a=b$. So, number of the solutions $9-1=\boxed 8$.
Remember 1: This case includes $a=b=c>d$ and $a>b=c=d$ non-identical sub cases.
2. Case: Solutions in the form $(a,a,b,b)$ and $a \ne b$. \begin{array}{lcr} 2n_a + 2_b & = & 8 \\ 2m_a +2_b & = & 8 \end{array}
Solutions $(n_a,n_b)=(0,4),(1,3),(2,2),(3,1),(4,0)$ and $(m_a,m_b)=(0,4),(1,3),(2,2),(3,1),(4,0)$. There are $5\cdot 5 =25$ solutions. But for $(n_a,n_b)=(m_a,m_b)=(2,2)$, we find $a=b$. So, number of the solutions $25-1=24$.
Remember 2: This case includes $a=b>c=d$ and $a=b<c=d$ identical sub cases. So non-identicals are $\dfrac{24}{2}=\boxed{12}$.
3. Case: Solutions in the form $(a,a,b,c)$ and $a \ne b \ne c \ne a$.
\begin{array}{lcr} 2n_a + n_b +n_c & = & 8 \\ 2m_a +m_b +m_c & = & 8 \end{array}
Solutions $(n_a,n_b,n_c)=(0,8,0),\dots ,(4,0,0)$ and $(m_a,m_b,m_c)=(0,8,0),\dots ,(4,0,0)$ . There are $25\cdot 25 =625$ solutions. But;
for $(n_a,n_b),(m_a,m_b)\in \{(0,0),(1,1),(2,2)\}$, we find $a=b$. There are $3\cdot3=9$ solutions. For $(n_a,n_c),(m_a,m_c)\in \{(0,0),(1,1),(2,2)\}$, we find $a=c$. There are $3\cdot3=9$ solutions. For $(n_b,n_c),(m_b,m_c)\in \{(0,0),(1,1),(2,2),(3,3),(4,4)\}$, we find $b=c$. There are $5\cdot5=25$ solutions. Also $(n_a=n_b,n_c)=(m_a=m_b,m_c)=(2,2,2)$ count $3$times. Therefore $625-9-9-25+2=584$
Remember 3: This case includes $a=b>c>d$ and $a=b>d>c$ identical sub cases. So non-identicals are $\dfrac{584}{2}=\boxed{292}$.
The Last Case: Solutions in the form $(a,a,a,a)$. Clearly, there is only $1$ solution.
Now we can find number of solutions in the form $abcd$ that all of them different each other. Amount of these $\dfrac{27225-\binom{4}1\cdot 8 -\binom{4}2\cdot 12 -\frac{4!}{2!}\cdot 292 -1 }{4!}= 984$.
Total amount of non-identical solutions $984 + 8 +12 + 292 +1=1297$.
