Search   Memberlist   Usergroups
 Page 1 of 1 [12 Posts]
Author Message
Mitch1123
science forum beginner

Joined: 30 Nov 2005
Posts: 40

Posted: Fri Jun 30, 2006 2:01 pm    Post subject: Re: Combinations satisfying linear equations?

Proginoskes wrote:
 Quote: Mitch wrote: BDH wrote: Exactly. Oh. Then my snap judgement would be that it is #P hard in such a general setting (which informally leads one to believe that there is no possible 'reasonable' (polysize) formula for it. Reduction from integer linear programming (or really, this -is- integer linear programming) and presuming a #P reduction from counting 3-SAT. Okay ... How about approximation? (The OP included the following.)

Oh, right. Well, there the knee-jerk response would be to model it as a
polytope and use monte carlo to approximate the volume (I really don't
know how difficult that would be... setup a bounding volume, select pts
from that see what proportion fall within the poytope/satsify the
inequalities?)

 Quote: BDH wrote: I was wondering if there was a general solution (or even approximation) for counting combinations with repetition where the element counts satisfy linear equations. Of course, if the linear equations are of a certain form, there might be a formula/procedure to count them quickly.

In some sense, if you have a fixed number of constraints and constant
coefficients, then there is a single number as an answer. I think the
heuristic would be that counting in the # of constraints would be (most
likely) exponential, and polynomial in the # of variables (the latter
meaning likely a polytime procedure/nice formula for counting).

Of course a specific example would make this discussion less
conjectural.

Mitch
BDH
science forum beginner

Joined: 25 Oct 2005
Posts: 11

Posted: Fri Jun 30, 2006 6:39 am    Post subject: Re: Combinations satisfying linear equations?

If you want intro material, I'd
 Quote: guess there's just as not much like trig or calulus, but I'd suppose as much as say topology?

Topology, at least, has more google hits and more pictures.
BDH
science forum beginner

Joined: 25 Oct 2005
Posts: 11

Posted: Fri Jun 30, 2006 4:16 am    Post subject: Re: Combinations satisfying linear equations?

 Quote: Okay ... How about approximation? (The OP included the following.) Of course, if the linear equations are of a certain form, there might be a formula/procedure to count them quickly.

Thought about it some more. Reducing the linear equations, transforming
the inequalities with them onto the free variables, and using the
transformed inequalities (or here the values they produce) as an
operator on the formula for combination with repetition for the
non-free variables, I got an asymptotic solution (I think) which will
likely have to do.
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Fri Jun 30, 2006 2:46 am    Post subject: Re: Combinations satisfying linear equations?

Mitch wrote:
 Quote: BDH wrote: Exactly. Oh. Then my snap judgement would be that it is #P hard in such a general setting (which informally leads one to believe that there is no possible 'reasonable' (polysize) formula for it. Reduction from integer linear programming (or really, this -is- integer linear programming) and presuming a #P reduction from counting 3-SAT.

Okay ... How about approximation? (The OP included the following.)

BDH wrote:
 Quote: I was wondering if there was a general solution (or even approximation) for counting combinations with repetition where the element counts satisfy linear equations.

Of course, if the linear equations are of a certain form, there might
be a formula/procedure to count them quickly.

--- Christopher Heckman
Mitch1123
science forum beginner

Joined: 30 Nov 2005
Posts: 40

Posted: Thu Jun 29, 2006 9:28 pm    Post subject: Re: Combinations satisfying linear equations?

BDH wrote:
 Quote: Exactly.

Oh. Then my snap judgement would be that it is #P hard in such a
general setting (which informally leads one to believe that there is no
possible 'reasonable' (polysize) formula for it.
Reduction from integer linear programming (or really, this -is- integer
linear programming) and presuming a #P reduction from counting 3-SAT.

Mitch
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Jun 28, 2006 7:28 pm    Post subject: Re: Combinations satisfying linear equations?

Mitch wrote:
 Quote: BDH wrote: where the element counts satisfy linear equations. Oops! I meant to say, "linear equations and inequalities." If it was just equalities, I could solve my problem by hand. Then can you be more explicit? Can you give an example? Many equations and many inequalities? Ordered, unordered, with/without replacement...etc, etc..

The original post says:

[BDH:]
 Quote: I was wondering if there was a general solution (or even approximation) for counting combinations with repetition where the element counts satisfy linear equations.

I suspect the problem in question is similar to:

How many ways are there to choose N balls, with repetition and order
not mattering, if there are x_1 balls of type 1, x_2 balls of type 2,
...., x_4 balls of type 4, where

x_1 + x_2 + x_3 <= 8
x_1 + x_4 <= 6
x_1 + 2 x_3 >= 3

are all true?

It's not clear whether the total number of balls is fixed ahead of time
or not. My first answer was assuming it wasn't, although now, I suspect
it is. It would just be a matter of throwing in some extra
inequalities:

x_1 <= 5
x_2 <= 3
x_3 <= 7
x_4 <= 8

--- Christopher Heckman
Mitch1123
science forum beginner

Joined: 30 Nov 2005
Posts: 40

Posted: Wed Jun 28, 2006 1:31 pm    Post subject: Re: Combinations satisfying linear equations?

BDH wrote:
 Quote: where the element counts satisfy linear equations. Oops! I meant to say, "linear equations and inequalities." If it was just equalities, I could solve my problem by hand.

Then can you be more explicit? Can you give an example? Many equations
and many inequalities? Ordered, unordered, with/without
replacement...etc, etc..

Mitch
BDH
science forum beginner

Joined: 25 Oct 2005
Posts: 11

Posted: Wed Jun 28, 2006 1:05 am    Post subject: Re: Combinations satisfying linear equations?

 Quote: # of solns to x_1 + x_2 + ..+ x_n = r is the same as the number of ways to place r items in n distinguishable (ordered) buckets, which is the same as the # of ways to locate n-1 1's in a 0,1 string (making n runs of 0's possibly some of zero length, the length of the first run being x_1, the total of the lengths of runs being r, so the length of the entire string is n+r-1) or

I figured as much as what I think you mean. Unfortunately, that's not
quite the problem I have.
BDH
science forum beginner

Joined: 25 Oct 2005
Posts: 11

Posted: Wed Jun 28, 2006 1:03 am    Post subject: Re: Combinations satisfying linear equations?

 Quote: where the element counts satisfy linear equations.

Oops! I meant to say, "linear equations and inequalities." If it was
just equalities, I could solve my problem by hand.
Mitch1123
science forum beginner

Joined: 30 Nov 2005
Posts: 40

Posted: Wed Jun 28, 2006 12:25 am    Post subject: Re: Combinations satisfying linear equations?

BDH wrote:
 Quote: I was wondering if there was a general solution (or even approximation) for counting combinations with repetition where the element counts satisfy linear equations.

# of solns to x_1 + x_2 + ..+ x_n = r is
the same as the number of ways to place r items in n distinguishable
(ordered) buckets, which is the same as the # of ways to locate n-1 1's
in a 0,1 string (making n runs of 0's possibly some of zero length, the
length of the first run being x_1, the total of the lengths of runs
being r, so the length of the entire string is n+r-1) or

n+r-1 \choose n-1 (i.e. binomial coefficient)

Most basic combinatorics books will have this in the earlier chapters
on permutations and combinations (in the text of as an exercise)

 Quote: Combinatorics doesn't seem to have the web presence of some other math.

- in addition to what the other respondent said, it depepends on what
you mean by web presence. if you are looking for papers, there's just
as much presence as any other subfield. If you want intro material, I'd
guess there's just as not much like trig or calulus, but I'd suppose as
much as say topology?

Mitch
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Tue Jun 27, 2006 10:31 pm    Post subject: Re: Combinations satisfying linear equations?

BDH wrote:
 Quote: I was wondering if there was a general solution (or even approximation) for counting combinations with repetition where the element counts satisfy linear equations.

I'm not aware of any such results. You could find all the integer
solutions to the linear equations, and then use the formulas for each
one.

Generating functions might be another possibility.

 Quote: Combinatorics doesn't seem to have the web presence of some other math.

Historically, combinatorics was looked down along. But along came
Computer Science and Algorithm Analysis, and combinatorics turned out
to be the best part of mathematics to use. It's a true-life "ugly
duckling" story.

--- Christopher Heckman
BDH
science forum beginner

Joined: 25 Oct 2005
Posts: 11

 Posted: Tue Jun 27, 2006 9:58 am    Post subject: Combinations satisfying linear equations? I was wondering if there was a general solution (or even approximation) for counting combinations with repetition where the element counts satisfy linear equations. Combinatorics doesn't seem to have the web presence of some other math.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [12 Posts]
 The time now is Fri Dec 14, 2018 6:15 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am approximating infinite linear programming problems diegotorquemada@yahoo.com Math 0 Mon Jul 17, 2006 10:29 am Linear algebra txtbk recommendations... Snis Pilbor Math 1 Sat Jul 15, 2006 11:40 pm Iterative solution to non-linear equations laniik Math 5 Fri Jul 14, 2006 6:38 pm How to solve linear program with matrix variable ? Fan num-analysis 4 Thu Jul 13, 2006 5:55 am