A (probably wrong) conjecture

[Max Alekseyev]

Actually, the conjecture is correct.
Without "1+", which will stand for the zero value of the product, it
can be formulated as follows:

*Theorem 1*. The number of distinct *nonzero* values of Product_{q is
a part of Q} (q-1), where Q ranges over all partitions of n, is equal
to the number of partitions P of n into parts of the form p+1 where
p=1, p=4, or p is a prime except p=11.

First off, notice that every number of the form x*y+1 where x>1 and
y>1 are integers, except x=y=2, can be represented in the form
(x+1)+(y+1)+(1+1)*k where k is a non-negative integer. Therefore,
every part of Q of the form x*y+1 where x>1, y>1, except x=y=2, can be
sub-partitioned into the parts x+1, y+1, and k parts equal 1+1=2 such
that the product Product_{q is a part of Q} (q-1) remains the same.
Therefore, Theorem 1 is equivalent to:

*Theorem 2*. The number of distinct values of Product_{q+1 is a part
of Q} q, where Q ranges over all partitions of n into parts of the
form q+1 where q is a prime, q=1, or q=4, is equal to the number of
partitions P of n into parts of the form p+1 where p=1, p=4, or p is a
prime except p=11.

The proof of Theorem 2 is split into two Lemmas:

Lemma 3. The number of distinct values of Product_{q+1 is a part of Q}
q, where Q ranges over all partitions of n into parts of the form q+1
where q is a prime, q=1, or q=4, is equal to the number of partitions
Q' of n into the same parts that do not contain a sub-partition
{5,5,2}.

Proof of Lemma 3. Note that each sub-partition {5,5,2} in Q can be
replaced with {3,3,3,3} so that the resulting partition will remain a
partition of n with the same value of Product_{q+1 is a part of Q} q.
After a finite number of such replacements we get a partition Q'
without sub-partitions {5,5,2}.
To finish the proof it is enough to notice that no two different
partitions of Q'-type (i.e., without sub-partitions {5,5,2}) can have
the same value of Product_{q+1 is a part of Q} q.
QED

Lemma 4. The number of partitions Q' of n into parts of the form q+1
where q is a prime, q=1, or q=4, without sub-partition {5,5,2} is
equal to the number of partitions P of n into parts of the form p+1
where p=1, p=4, or p is a prime except p=11.

Proof of Lemma 4. There is one-to-one correspondence between the
partitions of Q'-type and P-type: to get P from Q' one needs to
replace of each sub-partition {12} with {5,5,2}; to get Q' from P one
needs to replace of each sub-partition {5,5,2} with {12}.
QED

Regards,
Max

On Fri, May 23, 2008 at 2:47 AM, Vladeta Jovovic <vladeta at eunet.yu> wrote:
>
>
>>
>> %I A000001
>> %S A000001
>> 1,2,2,3,3,5,4,8,7,11,11,17,16,25,24,35,35,50,49,70,69,94,96,129,129,172,174,227,232,298,303,389,396,498,513,639,655,814,834,1025
>> %N A000001 Number of distinct values of Product_{p is a part of P} (p-1)
>> when P ranges over all partitions of n.
>> %F A000001 Conjecture:  G.f. is
>> x/(1-x)+((1-x^12)/((1-x^2)*(1-x^5)))*(1/Product_{k>0} (1-x^(prime(k)+1))),
>> i.e. a(n) = 1 + number of partitions of n into parts of the form p+1, p a
>> prime, excluding 12 and including 2 and 5.
>> %Y A000001 Cf. A034891.
>> %O A000001 1
>> %K A000001 ,more,nonn,
>> %A A000001 Vladeta Jovovic (vladeta at Eunet.yu), May 23 2008
>>
>
> V.
>