Problem concerned with A018819

[franktaw at netscape.net]

I can show that this holds, using the recursion  a(2m+1) = a(2m),
a(2m) = a(2m-1)+a(m).

First, the Perm function is A048996/A072811 (depending on whether
you take your permutations in A&S or Mma order).  As noted in
A072811, this is the multinomial coefficient (A036038/A078760) of
the signature (A115621) of the partition.  And a multinomial
coefficient is odd iff when the parts are written in binary and summed,
no carry occurs.

In other words, the multiplicities of the parts, added in binary, must
not produce any carries when added in binary.

It follows that any such partition will have at most one part with odd
multiplicity.  Incrementing the size of one such part, or adding a part
of size 1 if there is no such part, gives a partition of n+1 that has 
one
part with odd multiplicity, and has the requisite property.  (For
example, in the partition [3^5], 3 is present an odd number of times,
so we increment one of the 3's, giving [4,3^4].)  This generates all
such partitions of n+1 that have a part with odd multiplicity (simply
reduce one part with odd multiplicity, eliminating it if it was 1).  If
n = 2m, the parts with all multiplicities even are the partitions of 
this
sort of m, with all multiplicities doubled.  Q.E.D.

We can establish a correspondence as follows: starting with a
partition with an odd number of permutations, take the conjugate.
Now divide each part into powers of two using its binary
representation.  For example, starting with [5,2^4], the conjugate
is [5^2,1^3]; splitting each 5 into 4 and 1 gives the binary partition
[4^2,1^5].

(This correspondence was derived by comparing the induction above
with the one in A018819.)

Franklin T. Adams-Watters

-----Original Message-----
From: Vladeta Jovovic <vladeta at EUnet.yu>

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?

________________________________________________________________________
Check Out the new free AIM(R) Mail -- Unlimited storage and 
industry-leading spam and email virus protection.