| Author |
Message |
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. |
|
| Back to top |
|
 |
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 |
|
| Back to top |
|
|
Mitch
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.
|
- 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 |
|
|
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. |
|
| Back to top |
|
|
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. |
|
| Back to top |
|
|
Mitch
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 |
|
| Back to top |
|
|
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 |
|
| Back to top |
|
|
Mitch
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:
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
|
| 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 |
|
| Back to top |
|
|
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. |
|
| Back to top |
|
|
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. |
|
| Back to top |
|
|
Mitch
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 |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
