Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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