2
$\begingroup$

I'm computing Whitney numbers of the Divisor lattice of an integer $n = \prod_{p \mid n} p^{\text{ord}_{p}(n)} = p_1^{n_1} \cdots p_{q}^{n_{q}}$ using the formula quoted in Erdos and Szekely's "Pseudo-LYM inequalities and AZ identities" (immediately after Theorem 3.3) found here, \begin{align} N_{l} = \sum_{k_1 + \cdots + k_q = l} \binom{n_1}{k_1} \cdots \binom{n_q}{k_q}. \end{align} The sum is over the non-negative solutions of the linear Diophantine $k_1 + \cdots + k_q = l$, where $l$ is the rank and $0 \leq k_i \leq n_i$, where $n_i$ is the $i^{\text{th}}$ exponents of the prime decomposition $n$. The integer $l$ runs from $0$ to $\Omega(n) = \sum_{p \mid n} \text{ord}_p(n)$.

For $n = 2^{2} 5$, the known sequence of Whitney numbers is $\{1, 2, 2, 1\}$ with corresponding divisors $\{ \{1 \}, \{2, 5 \}, \{4, 10 \}, \{20 \} \}$. Using the formula above, I compute $\{1, 3, 3, 1\}$, as there are two solutions of the linear equation for $l = 1$ and three for $l = 2$, namely, $(0,1)$, $(1,0)$ and $(0,2)$, $(1,1)$, $(2,0)$, yielding \begin{align} \binom{2}{0} \binom{1}{1} + \binom{2}{1} \binom{1}{0} = \binom{2}{0} \binom{1}{2} + \binom{2}{1} \binom{1}{1} + \binom{2}{2} \binom{1}{0} = 3. \end{align} In fact, for any $n$, the formula above just computes $\binom{\Omega(n)}{l}$. Where is the over-counting? Should there be another restriction on the sum or is the formula just incorrect as stated?

1 Answers 1

1

The formula is incorrect as stated. It treats equal prime factors as distinct, and the result is simply $\binom{\Omega(n)}l$, the number of $l$-elements subsets of the (distinct) prime factors. The correct Whitney number is the sum over $1$ instead of the product of binomial coefficients; see here.