Sequence A025591 and MathSciNet
Yuval Dekel
dekelyuval at hotmail.com
Fri Dec 12 04:57:59 CET 2003
The connection is with the "subset sum problem" .
The sequence gives the maximal value that a real number is attained as a
subset sum for a set of n distinct real numbers .
The solution of the problem is that the maximum is attained by a set
proportional to {1,2,...,n} .
Regards,
Yuval
>From: Edwin Clark <eclark at math.usf.edu>
>To: Yuval Dekel <dekelyuval at hotmail.com>
>CC: njas at research.att.com, seqfan <seqfan at ext.jussieu.fr>
>Subject: Re: Sequence A025591 and MathSciNet Date: Thu, 11 Dec 2003
>21:09:14 -0500 (EST)
>On Fri, 12 Dec 2003, Yuval Dekel wrote:
>
> > If my memory is not mistaken, sequence A025591 is related to the
>following
> > paper :
> >
> > Robert A. Proctor
> > Solution of two difficult combinatorial problems with linear algebra,
> > American Mathematical Monthly 89, 721-734.
> >
> > Perhaps someone on the list with an access to MathSciNet can share with
>us
> > the abstract of this paper .
>
>Here's the abstract. I don't see the connection.
>
>MR0683197 (84f:05002)
>Proctor, Robert A.
>Solution of two difficult combinatorial problems with linear algebra.
>Amer. Math. Monthly 89 (1982), no. 10, 721--734.
>--------------------------------------------------------------------------------
>The "subset sum problem" is the problem of finding a set of $n$ distinct
>positive real numbers with as large a collection as possible of subsets
>with the same sum. The "grid shading problem" is the problem of proving
>the unimodality of the sequence $a_1,a_2,\cdots,a_{mn}$, where for fixed
>$m$ and $n,a_i$ is the number of partitions of $i$ with at most $m$ parts
>and largest part at most $n$. The grid shading problem was solved by J. J.
>Sylvester [Philos. Mag. 5 (1878), 178--188; Jbuch 10, 82] using invariant
>theory. The subset sum problem was solved by R. P. Stanley [SIAM J.
>Algebraic Discrete Math. 1 (1980), 168--184; MR 82j:20083] using the tools
>of algebraic geometry. (The answer is $\{1,2,\cdots,n\}$.)
>This expository article contains the first elementary proofs of these
>results. Only basic linear algebra is used, although the motivation for
>the proof comes from the theory of representations of the Lie algebra
>$\germ{sl}(2, C)$. The problems are restated in terms of certain posets,
>which are shown to be rank unimodal and Sperner with the help of linear
>operators on the vector spaces spanned by the pos
>
_________________________________________________________________
Tired of spam? Get advanced junk mail protection with MSN 8.
http://join.msn.com/?page=features/junkmail
More information about the SeqFan
mailing list