Problem concerned with A018819

[Max Alekseyev]

On 8/7/07, Vladeta Jovovic <vladeta at eunet.yu> wrote:

> Let p be a partition of n.
>
> Define Perm(p)  to be the number of permutations on p (if we consider p as a
> multiset) or equivalently the number of compositions generated by p.
>
> Then, it seems that
>
> number of partitions p of n such that Perm(p) is odd  =  number of
> partitions of n into powers of 2  =  A018819(n) .
>
> Is there a (simple bijective) proof of this conjecture?

Let p = { 1^{k_1}, 2^{k_2}, ..., n^{k_n} } be a partition of n (i.e.,
where part i occurs k_i>=0 times). Then n = \sum_{i=1}^n i * k_i and
the number of compositions generated by p equals the multinomial
coefficient (k_1 + k_2 + ... + k_n)! / (k_1! * k_2! * ... * k_n!).
By Lucas theorem, this coefficient is odd if and only if neither pair
of k_i, k_j have a digit 1 at the same position in their binary
representations (i.e., for every i<>j, k_i AND k_j = 0 bitwise). In
other words, we represent every k_i as the sum of powers of 2
according to its binary representation:
k_i = 2^{d_{i1}} + 2^{d_{i2}} + ... + 2^{d_{im_i}},
where 0 <= d_{i1} < d_{i2} < ... < d_{im_i},
then all { d_{ij} : i=1..n, j=1..m_i } are distinct.
Therefore, the multiset q = { (2^{d_{ij}})^i : i=1..n, j=1..mi }
(where the power 2^{d_{ij}} has the multiplicity i) forms a partition
of n.

It is easy to see that the correspondence p -> q is a bijection.
Indeed, if we are given a partition q of n into powers of 2, we can
reconstruct p simply as p = { 1^{k_1}, 2^{k_2}, ..., n^{k_n} } where
k_i equals the sum of those powers from q that have the multiplicity
i.

Regards,
Max