[seqfan] Re: New or old seq: The maximum number of shift-minimal winning coalitions, 'On Dedekind's problem for complete simple games'
franktaw at netscape.net
franktaw at netscape.net
Tue Jan 19 16:13:18 CET 2010
That "maximal coefficient of Product_{k<=n} (x^k+1)." is the same as
"maximal number of subsets of {1,2,...,n} that share the same sum" is
trivial. That this is the same as "number of solutions to +- 1 +- 2 +-
3 +- ... +- n = 0 or 1.", as asserted by A025591's description, is not
trivial, but not very difficult.
So we have our answer to the original question: this should be added as
a comment to the existing sequence. Both the Kurz and Tautenhahn paper
and the Krohn and Sudhoelter paper cited below should be referenced
there.
Franklin T. Adams-Watters
-----Original Message-----
From: Sascha Kurz <sascha.kurz at uni-bayreuth.de>
2) Directly determining some more values of the maximum number of
shift-minimal winning coalitions is not that easy. Without using any
further tricks cliquer (http://users.tkk.fi/pat/cliquer.html - a
software
package for finding cliques) will take too long.
But, Krohn and Sudhoelter have shown in "Directed majority games" (on
pages 196-198, using a result from RP Stanley "Weyl groups, the hard
Lefschetz Theorem, and the Sperner property", 1980) that the maximum
number of shift-minimal winning coalitions equals is the maximal number
of
subsets of {1,2,...,n} that share the same sum.
Checking numerically whether A025591 equals indeed the maximal number of
subsets of {1,2,...,n} that share the same sum (as the comment says)
should be easy. As I understand it, a proof for the latter equality is
contained in Theorem 2.1 of Dorin Andrica and Ioan Tomescu, On an
Integer
Sequence Related to a Product..., Journal of Integer Sequences, Vol. 5
(2002), Article 02.2.4
Best wishes,
Sascha
Am Di, 19.01.2010, 06:03, schrieb franktaw at netscape.net:
> 1) The comment in A025591, "If k is allowed to approach infinity, this
> gives the partition numbers A000009. " is not correct. The maximum
of this
> sequence comes (after the first few values) from a power of x greater
than
> n. It would be appropriate to have a cross reference to A000009.
>
>
> 2) It would really help if two more values were calculated for the
> game-theoretic sequence (one would be useful, but less good). If two
more
> values match, I would just add a comment "It appears that this is the
same
> as ...", and include the reference. If they don't match, of course,
you
> have your answer.
>
> Equally good, of course, would be a proof that the sequences are the
> same. You might try emailing the authors and see if they can prove
> equality. I'm sure they would love to be able to publish it.
>
> Failing either of the above, I would add it as a new sequence, with
> appropriate cross-refs to and from A025591. If even one more value
can be
> found to match, I would probably favor just adding a comment (as
above).
>
> Neil might give different answers; this is not an authoritative
> response.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Jonathan Post <jvospost3 at gmail.com>
>
>
> 1, 1, 2, 2, 3, 5, 8, 14, 23, 40, 70, 124, 221, 397, 722
>
>
> Table 1. The maximum number of shift-minimal winning coalitions.
>
>
> p.5 of http://arxiv.org/abs/1001.3045 On Dedekind's problem for
complete
> simple games Authors: Sascha Kurz, Nikolas Tautenhahn
> Comments: 13 pages, 1 figure, 6 tables, submitted to ISSAC 2010
> Subjects: Combinatorics (math.CO)
>
>
> We combine the parametric Barvinok algorithm with a generation
> algorithm for a finite list of suitably chosen discrete sub-cases on
the
> enumeration of complete simple games, i.e. a special subclass of
monotone
> Boolean functions. Recently, Freixas et al. have proven an
> enumeration formula for complete simple games with two types of
voters. We
> will provide a shorter proof and an enumeration formula for complete
> simple games with two shift-minimal winning coalitions.
>
> I note that this (except for a-0) agrees with
> A025591 Maximal coefficient of Product_{k<=n} (x^k+1). Number
of
> solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.
>
> So is this a new seq, or a comment on an old one?
More information about the SeqFan
mailing list