Two proofs of the statement in A018819 that this is also the
"Number of partitions p of n such that the number of compositions generated 
by p is odd".

Max Alekseyev's proof:

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. 


Franklin T. Adams-Watters's proof:

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.)