Simultaneous lcms

Question

Suppose that we have some finite number of $k$-tuples then we define the lcm of two of these tuples to be the tuple of lcms of the co-ordinates. E.g. $[(9, 10), (5, 18)] = ([9, 5], [10, 18]) = (45, 90)$. Suppose further that these tuples are all tuples which multiply to the same squarefree number $d$ (in the above case this would be $90$ which isn't squarefree, but just run with it).

Fix some $k$-tuple $\textbf{n} = (n_1, n_2, \ldots, n_k)$ such that $n_i \mid d$ for all $i$. How many solutions are there, for each $r$, to

\begin{equation} \operatorname{lcm}\limits_{1 \leq i \leq r}\textbf{m}_i = \textbf{n} \end{equation}

where the $\textbf{m}_i$ are distinct $k$-tuples whose components multiply to give $d$?

It should surely be something which depends only on $\omega(d)$; $r$; and the greatest common divisor of the combinations of the $n_i$. For example, if $\textbf{n} = (6, 6, 6)$ and $d = 6$ then there are no pairs of $3$-tuples satisfying the above conditions such that their lowest common multiple is $(6, 6, 6)$. On the other hand, if $r = 3$ then there are five combinations: \begin{align} (1, 1, 6) (1, 6, 1) (6, 1, 1)\\ (1, 2, 3) (1, 3, 2) (6, 1, 1)\\ (1, 2, 3) (3, 1, 2) (2, 3, 1)\\ (2, 1, 3) (1, 3, 2) (3, 2, 1)\\ (2, 1, 3) (3, 1, 2) (1, 6, 1) \end{align}

EDIT: I should have included $(1, 1, 6)(2, 3, 1)(3, 2, 1)$ so there are $6$ different combinations.

Answer 1

For each prime $p|d$, let $q_p$ be the number of $n_i$ with $p|n_i$. Then the number of ordered but not necessarily distinct solutions $(m_1,\dots,m_r)$ is given by $$f(r)=\prod_{p|d} S(r,q_p)\cdot q_p!,$$ where $S(,)$ are Stirling numbers of the second kind.

To get number of ordered solutions with pairwise distinct $m_i$, we can use inclusion-exclusion: $$\sum_{j=0}^r s(r,j)\cdot f(j),$$ where $s(,)$ are Stirling numbers of the first kind with sign.

To get the number of unordered solutions, it remains to divide the last expression by $r!$.

Combining all together, we get that the number of unordered pairwise distinct solutions $\{m_1,\dots,m_r\}$ equals: $$\frac{1}{r!}\sum_{j=0}^r s(r,j)\cdot \prod_{p|d} S(j,q_p)\cdot q_p!.$$

Answer 2

For squarefree $d$, we can translate this into a design problem. Given an $r$ by $c$ array (which correspond to your $r$ many $k$-tuples, but I use $c$ instead of $k$), you need to divide the $k$ distinct prime factors of $d$ into sets such that

• each row is a partition of the set of $k$ factors
• each column is a cover, so the union of the column members is the set of $k$ factors.

As a result of this, you need $r \geq c$ for things to work. Calling each such arrangement a column-labelled design (so that counting might be easier, we consider column swaps of distinct columns different answers), your question is how many distinct column-labelled designs are there. (If row-order is important, then we label the rows as well.)

If $r=c\leq k$, an obvious subset of solutions stems from breaking the set of divisors into a set of size $r$ and use that to generate a latin square of size $r$, and then divide the remaining subset $S$ of $k-r$ factors in a way consistent with the constraints. One way is to assign the subset $S$ to each array element which is part of a transversal, that is a subset of the array which has exactly one array location in each row and one in each column.

If $k \gt r \gt c$, you can do some repetition of a latin square of size $c$ as above, but to make things interesting, you can sprinkle $S$ across each additional row as you please, since the first $c$ rows already constitute a cover. You can even do this with $r \gt k$, but to avoid repeating rows, $r$ should be less than some function of $k-c$, probably something like partition($k-c$).

If $k \lt c$, things get a little more interesting, as some of the array elements in each row will have to be empty. You might be able to "color" the multiset of factors union a multiset of 1's and then pretend $k \geq c$, but to enumerate distinct cases you will have to remove the colors later and it is unclear to me how this will effect the counting.

If you manage to enumerate what you want with $d$ squarefree, I will be surprised if $d$ nonsquarefree presents any serious challenge. Just handling the cases above is hard enough.

Gerhard "Definitely Not A Professional Combinatorialist" Paseman, 2015.07.01