FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Combinations satisfying linear equations?
Post new topic   Reply to topic Page 1 of 1 [12 Posts] View previous topic :: View next topic
Author Message
Mitch1123
science forum beginner


Joined: 30 Nov 2005
Posts: 40

PostPosted: Fri Jun 30, 2006 2:01 pm    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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
Back to top
BDH
science forum beginner


Joined: 25 Oct 2005
Posts: 11

PostPosted: Fri Jun 30, 2006 6:39 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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.
Back to top
BDH
science forum beginner


Joined: 25 Oct 2005
Posts: 11

PostPosted: Fri Jun 30, 2006 4:16 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Fri Jun 30, 2006 2:46 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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
Back to top
Mitch1123
science forum beginner


Joined: 30 Nov 2005
Posts: 40

PostPosted: Thu Jun 29, 2006 9:28 pm    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Wed Jun 28, 2006 7:28 pm    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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
Back to top
Mitch1123
science forum beginner


Joined: 30 Nov 2005
Posts: 40

PostPosted: Wed Jun 28, 2006 1:31 pm    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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
Back to top
BDH
science forum beginner


Joined: 25 Oct 2005
Posts: 11

PostPosted: Wed Jun 28, 2006 1:05 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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.
Back to top
BDH
science forum beginner


Joined: 25 Oct 2005
Posts: 11

PostPosted: Wed Jun 28, 2006 1:03 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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.
Back to top
Mitch1123
science forum beginner


Joined: 30 Nov 2005
Posts: 40

PostPosted: Wed Jun 28, 2006 12:25 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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.

- google 'combinations repetition' ?
- 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
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Tue Jun 27, 2006 10:31 pm    Post subject: Re: Combinations satisfying linear equations? Reply with quote

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
Back to top
BDH
science forum beginner


Joined: 25 Oct 2005
Posts: 11

PostPosted: Tue Jun 27, 2006 9:58 am    Post subject: Combinations satisfying linear equations? Reply with 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.

Combinatorics doesn't seem to have the web presence of some other math.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [12 Posts] View previous topic :: View next topic
The time now is Fri Dec 14, 2018 6:15 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0184s ][ Queries: 20 (0.0031s) ][ GZIP on - Debug on ]