[seqfan] Fwd: reply from Valentin Bakoev on "Question about A000290"

[Alexander Povolotsky]

---------- Forwarded message ----------
From: Valentin Bakoev <v_bakoev at yahoo.com>
Date: Mon, Apr 20, 2009 at 9:14 AM
Subject: Re: Question about A000290
Dear
Professor Heinz,

All my
notes and comments in OEIS, that you ask me about,  are taken (or related
to, or follow directly) from my paper
“Algorithmic approach to counting of certain types m-ary partitions”,
Discrete
Mathematics, 275 (2004) pp.17-41. Naturally, many details from the paper are
omitted in my notes in OEIS - they summarize some results and relations
only.
So I refer to the paper and I recommend it to the readers who want to know
these details. I think that the paper contains the answers of all your
questions to me. Anyway, I will try to answer you shortly:
1)      My
comment about the sequence A000290 concerns the number of all partitions of
the
sum 2^2+2^2+...2^2, (n-1)-times, into powers of 2. This sum is considered as
an
expression, which addends are partitioned. *So we do not consider the
partitions
of the number, equal to the value of this expression*. This is more general
problem, as it is noted in the field “Formula” of A002577. The relation
between
it (i.e. the numbers of A002577) and the square numbers is given in the
fields
“Crossrefs” of A000290 and A002577;
2)      The
existence of an algorithm (with polynomial running-time) for computing the
members of A002577, A125792 and other sequences of the same type is derived
in
Section 4 of the paper, mentioned above. I should note, that this
running-time
is obtained towards uniform cost criterion. The reasons to accept this
criterion are discussed in the Introduction of the paper. This criterion is
enough realistic for many practical purposes, for example when:
-         the size of the input and the output
in not so large and the 64-bits architectures and arithmetic are enough for
computing of the intermediate results and the output;
-         the
number of partitions is computed by an efficient implementation of
large-integer arithmetic – as in the packages Mathematica, Maple etc.

Thank you for your attention to my notes in
OEIS!

Sincerely yours,
Valentin Bakoev
 ---------- Forwarded message ----------
From: Prof. Dr. Alois Heinz <heinz at hs-heilbronn.de>
Date: Sat, Apr 18, 2009 at 12:29 PM
Subject: [seqfan]  Question about A000290
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

Seqfans, in A000290 (The squares: a(n) = n^2.)

http://www.research.att.com/~njas/sequences/A000290

I found this comment: "a(n) is also the number of all partitions
 of the sum 2^2+2^2+...2^2, (n-1)-times, into powers of 2."
which is only partly true.

For n=3, we have the sum 2^2+2^2=8, but there are 10 (not 3^2=9)
partitions of 8 into powers of 2:

1+1+1+1+1+1+1+1, 1+1+1+1+1+1+2, 1+1+1+1+2+2, 1+1+2+2+2, 2+2+2+2,
1+1+1+1+4, 1+1+2+4, 2+2+4, 4+4, 8

Perhaps the following was meant:

"a(n+1) is also the number of partitions of 4n into the first 3 powers
of 2 (parts of size 1, 2, 4)."

As FORMULA:  a(n) = [x^(4*n)] x^4/((1-x)*(1-x^2)*(1-x^4)).

Do you agree?

Alois





_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/