Enumeration formulas involving partitions
Christian G. Bower
bowerc at usa.net
Tue May 6 01:40:39 CEST 2008
small values when first imagining a new structure, but they can become
Return-Path: <njas at research.att.com>
X-Ids: 165
Date: Tue, 6 May 2008 09:24:08 -0400
From: "N. J. A. Sloane" <njas at research.att.com>
Message-Id: <200805061324.m46DO8fX005408 at prim.research.att.com>
Reply-To: njas at research.att.com
X-Mailer: mailx (AT&T/BSD) 9.9 2008-02-12
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: jvospost2 at yahoo.com, mathar at strw.leidenuniv.nl,
maximilian.hasler at gmail.com, njas at research.att.com
Subject: Re: A104533 == A129682
Cc: arndt at jjj.de, seqfan at ext.jussieu.fr
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.165]); Tue, 06 May 2008 15:24:11 +0200 (CEST)
X-Virus-Scanned: ClamAV 0.92/7040/Tue May 6 03:52:15 2008 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at jchkmail.jussieu.fr with ID 48205BFA.002 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)!
X-j-chkmail-Enveloppe: 48205BFA.002/192.20.225.112/mail-dark.research.att.com/mail-yellow.research.att.com/<njas at research.att.com>
X-j-chkmail-Score: MSGID : 48205BFA.002 on jchkmail.jussieu.fr : j-chkmail score : XXX : R=. U=. O=. B=0.552 -> S=0.552
X-j-chkmail-Status: Unsure
Return-Path: <webonfim at bol.com.br>
X-Ids: 166
Date: Tue, 6 May 2008 23:27:06 -0300
Message-Id: <K0H856$1572FF66BFC7638742505FFE656B3A29 at bol.com.br>
Subject: Enumeration formulas using partitions
MIME-Version: 1.0
X-Sensitivity: 3
Content-Type: multipart/alternative;
boundary="_=__=_XaM3_.1210127226.2A.72374.42.25448.52.42.007.694409443"
From: "webonfim" <webonfim at bol.com.br>
To: "seqfan" <seqfan at ext.jussieu.fr>
X-XaM3-API-Version: 4.3(R1) (B10)
X-SenderIP: 189.71.169.56
X-SIG5: 8914f755a8e75bb4d807c36bb05b9b26
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.166]); Wed, 07 May 2008 04:27:10 +0200 (CEST)
X-Virus-Scanned: ClamAV 0.92/7043/Tue May 6 23:56:43 2008 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at jchkmail.jussieu.fr with ID 4821137D.000 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)!
X-j-chkmail-Enveloppe: 4821137D.000/200.221.4.107/relay3.bol.com.br/relay3.bol.com.br/<webonfim at bol.com.br>
X-j-chkmail-Score: MSGID : 4821137D.000 on jchkmail.jussieu.fr : j-chkmail score : X : R=. U=. O=. B=0.200 -> S=0.200
X-j-chkmail-Status: Ham
--_=__=_XaM3_.1210127226.2A.72374.42.25448.52.42.007.694409443
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable
Answer to Christian
I will try to use PARI. Thanks for the comments about PARI and "mathematic=
al software".
I have a partition generator program so I let the computer do the work. For=
n <=3D50, the program runs in a fraction of a second. For large n, say n >=
300 it is not practical to use it. One advantage of those partition formul=
as is that they are very simple to implement in any language. More easy in =
"mathematical software" I think.
It appears that it is obvious that a single transform applied to a sequence=
cannot give combinatorial objects with components of two types, so my ques=
tion "about two types of components" appears to be absurd. Of course a form=
ula involving transformations of two (or more) sequences can count objects =
with components of several types.
--------------------------
To "all seqfans"
Since those partition formulas are a way to generate new sequences from kno=
wn ones, they can be viewed as transforms. For me now it is not easy to ans=
wer those questions:
Is it fruitful to consider those formulas as transforms? (I think yes, but.=
..)
The formulas are equivalent to the EULERi and LOG transforms?
They resolve only a subset of the problems that can be resolved by those tr=
ansforms?
They are equivalent to several transforms?
While I wait some help, I am reading about transforms. I began with
"Some Easily Derivable Integer Sequences" of JIS, and I plan to look at the
related work by N.J.A.Sloane referenced in this paper of JIS.
--_=__=_XaM3_.1210127226.2A.72374.42.25448.52.42.007.694409443
Content-Type: text/html; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable
<DIV style=3D"FONT-SIZE: 12px; FONT-FAMILY: verdana, arial">
<DIV>Answer to Christian</DIV>
<DIV> </DIV>
<DIV>I will try to use PARI. Thanks for the comments about PARI and "=
mathematical software".</DIV>
<DIV> </DIV>
<DIV>I have a partition generator program so I let the computer do the work=
. For n <=3D50, the program runs in a fraction of a second. For large n,=
say n > 300 it is not practical to use it. One advantage of those parti=
tion formulas is that they are very simple to implement in any language. Mo=
re easy in "mathematical software" I think.</DIV>
<DIV> </DIV>
<DIV>It appears that it is obvious that a single transform applied to a seq=
uence cannot give combinatorial objects with components of two types, so my=
question "about two types of components" appears to be absurd. Of course a=
formula involving transformations of two (or more) sequences can count obj=
ects with components of several types.</DIV>
<DIV>--------------------------</DIV>
<DIV> </DIV>
<DIV>To "all seqfans"</DIV>
<DIV> </DIV>
<DIV>Since those partition formulas are a way to generate new sequences fro=
m known ones, they can be viewed as transforms. For me now it is not e=
asy to answer those questions:</DIV>
<DIV> </DIV>
<DIV>Is it fruitful to consider those formulas as transforms? (I think yes,=
but...)<BR></DIV>
<DIV>The formulas are equivalent to the EULERi and LOG transforms?<BR></DIV>
<DIV>They resolve only a subset of the problems that can be resolved by tho=
se transforms?<BR></DIV>
<DIV>They are equivalent to several transforms?</DIV>
<DIV> </DIV>
<DIV>While I wait some help, I am reading about transforms. I began with<BR=
>"Some Easily Derivable Integer Sequences" of JIS, and I plan to look at th=
e<BR>related work by N.J.A.Sloane referenced in this paper of JIS.</DIV>
<DIV> </DIV></DIV>
--_=__=_XaM3_.1210127226.2A.72374.42.25448.52.42.007.694409443--
> To "all seqfans"
> Since those partition formulas are a way to generate new sequences
> from known ones, they can be viewed as transforms. For me now it
> is not easy to answer those questions:
> Is it fruitful to consider those formulas as transforms?
> (I think yes, but...)
> The formulas are equivalent to the EULERi and LOG transforms?
> They resolve only a subset of the problems that can be resolved
> by those transforms?
> They are equivalent to several transforms?
Without access to H&P, I can only go by your examples and based on those,
I would say the partition formulas you are using are equivalent to
the EULERi and LOG transforms.
I feel compelled to take a rare step into the realm of mathematical
philosophy; you've been warned.
A transform is basically a function of sequences. A thing that maps one
One can multiply through successive addition, the way they taught
you in school or some fancy method in a high speed computer chip. As
long as it gives the same answer, it's multiplication. The same is true
of any of these transforms.
What you have shown in the examples is the same mapping as the transforms,
Just as a new student may benefit from a demonstration of multiplication
as successive addition before learning a more efficient algorithm, I
think there may be benefits to presenting these transforms through
partition formulas, perhaps on a webpage illustrating this connection
would be nice if someone wanted to create one. Maybe it could be hosted
at the OEIS or a math site like mathworld.
When I started playing with these formulas in the 90s, I wrote programs
to implement them that involved enumerating all partitions before I
read about more efficient techniques. The techniques should be easy
enough to implement in any programming language.
> While I wait some help, I am reading about transforms. I began with
> "Some Easily Derivable Integer Sequences" of JIS, and I plan to look at the
> related work by N.J.A.Sloane referenced in this paper of JIS.
I hope you get a chance to look at the Bernstein/Sloane paper.
I believe it was the paper that gave many of those transforms
their names. (It was one of those referenced in the JIS paper)
http://www.research.att.com/~njas/doc/eigen.pdf
Also check the Millar/Sloane/Young paper. (not referenced in that
JIS paper)
http://www.research.att.com/~njas/doc/bous.pdf
Christian
More information about the SeqFan
mailing list