I could use some help devising a formula for the following problem:

A ship has 7 ballast tanks. Each tank can hold up to 20 units of
water. The ship can only handle at most 100 units of water in the
tanks at once. The ship does not need to carry 100 units of water as
ballast, and a tank can be full, empty, or partially filled. The ship
needs a minimum of 20 units of water to keep itself stable.

~~

This is not a school question, but a logic/statistics type question I
devised of myself to help me learn more about math.

I realize that there is usage of pascals triangle on the formula, but
is there a way to write out a formula to work this problem? Or failing
that is there a way to devise the answer with a series of formulas for
individual aspects? Well I know the answer to the second is true.. but
the way I have seems rather time consuming.

I am trying to find out how many possible different loads of units of
water there are, and how this can be calculated.

Horseman <michae... at (no spam) gmail.com> writes:
Well the answer lies inside 20 per 5 all combinations, then
20,20,20,20,19,1 in all tank combinations, 20,20,20,20,18,2 and
20,20,20,20,18,1,1 and so forth. It can be worked out. There is most
assuredly a finite number to this, and I suspect it's less than a
billion total outcomes, therefore it is eminently solvable. Do not
assume units can be decimalled out, they are full units of 1. Just as
ships in real life wont worry about a drop, or a pound of water in a
ballast tank for being to small to worry about measuring for purposes
of staying afloat, we need not count the individual water atoms in an
unknown sized ship :P

Instead we can merely worry about a vague measure called a unit which
is always a whole number :P

Phil has already shown you how to solve this problem.  It's just that
he started doing it with increments of 10 units.  You just have to do
the same thing with increments of 1 unit.

To recap:

You have seven variables which can take on the integer values between
0 and 20 inclusive.  You ask how many combinations there are, such
that the sum of the seven variables is between 20 and 100, inclusive.

Let c(k) be the number of combinations of the seven variables whose
sum is k.  So the answer to your problem is:

  Sum[c(k), 20 <= k <= 100]

Sums of combinations generally have simple forms when you count all
the cases.  For example,

  Sum[c(k), 0 <= k <= 140] is 21^7 = 1801088541

because each of the seven variables has 21 possible values.  This
number is larger than the answer to your problem because it counts the
cases where k < 20 or k > 100.  Still, most of these combinations have
20 <= k <= 100, so this is the first hint that your suspicion that the
number of combinations is less than a billion is incorrect.  (I'm
using the U.S. definition of 1 billion = 10^9 = 1000000000.  I note
that you are posting from the state of Oregon.)

Rather than count the cases 20 <= k <= 100, it is easier to start with
all the cases 0 <= k <= 140 and subtract the cases 0 <= k < 20 and 100
k <= 140.

First, lets subtract the cases where 0 <= k < 20:

  Sum[c(k), 20 <= k <= 140] = 1801088541 - Sum[c(k), 0 <= k < 20]

Let's look at c(k) for small values of k:

  c(0) = 1
  c(1) = 7
  c(2) = 28

For c(2), there are 7 ways of choosing the same variable, and 21 ways
of choosing two different variables (7*6, divided by two because
you've counted them twice).

  c(3) = 84

Compare with Pascal's triangle.  Do you see the pattern that's
developing?  These numbers are coming from a diagonal row.  As long as
k <= 20, c(k) = ch(k+6,6).  (Here ch(n,m) = n!/((n-m)!m!) is the
binomial coefficient which is the number of combinations of "n"
objects, taken "m" at a time.  I chose "ch" as an abbreviation for
"choose".)

It turns out that there is a simple formula for summing terms like
ch(k+6,6):

  Sum[ch(k+6,6), 0 <= k <= t] = ch(t+7,7)

So our first calculation is:

  Sum[c(k), 20 <= k <= 140]  =  1801088541 - Sum[c(k), 0 <= k < 20]

                             =  1801088541 - Sum[ch(k+6,6), 0 <= k <= 19]

                             =  1801088541 - ch(26,7)

                             =  1800430741

Now lets subtract the cases where 100 < k <= 140:

  Sum[c(k), 20 <= k <= 100] = 1800430741 - Sum[c(k), 100 < k <= 140]

First, notice that c(k) is symmetric:

  c(0) = c(140) = 1

because there is only one way to have all the variables be zero and
there is only one way to have all the variables be twenty.

  c(1) = c(139) = 7

because there are seven ways to choose a variable to be one (with the
rest being zero) and there are seven ways to choose a variable to be
nineteen (with the rest being twenty).  Similarly, c(2) = c(138), c(3)
= c(137), etc.  So instead of calculating Sum[c(k), 100 < k <= 140],
we can calculate Sum[c(k), 0 <= k < 40].

Sum[c(k), 20 <= k <= 100]  =  1800430741 - Sum[c(k), 100 < k <= 140]

                           =  1800430741 - Sum[c(k), 0 <= k < 40]

This is nice because we already have a formula c(k) as long as k <> 20.  We are limited to k <= 20 because when we developed this formula,
we didn't limit individual variables to 20.  As long as k <= 20, we
are safe because if the sum of the variables is no more than 20, each
of the variables is no more than 20.  When k = 21, the formula c(k) > ch(k+6,6) no longer holds. because ch(k+6,6) includes the seven extra
combinations: (21,0,0,0,0,0,0), (0,21,0,0,0,0,0), etc.

  So c(21) = ch(27,6) - 7.

All the values of c(k) for 21 <= k < 42 can be developed by letting

  c(k) = ch(k+6,6) - d(k)

where d(k) is the number of illegal combinations, i.e. the number of
combinations which sum to k, but have a variable which is more than
20.  In fact, for k < 42, one and only one of the variables will have
the value 21 or more.  You can therefore count these illegal
combinations by looking at all the legal combinations which sum to
(k-21).  For each one of these, you can create seven different unique
combinations which sum to k by adding 21, in turn, to each of the
seven variables.

  So d(k) = 7 * c(k-21) for 21 <= k < 42

We can now write:

  Sum[c(k), 0 <= k < 40]  =  Sum[ch(k+6,6), 0 <= k < 40] -
                             Sum[d(k), 21 <= k < 40]

                          =  Sum[ch(k+6,6), 0 <= k < 40] -
                             7*Sum[c(k), 0 <= k < 19]

                          =  Sum[ch(k+6,6), 0 <= k < 40] -
                             7*Sum[ch(k+6,6), 0 <= k < 19]

                          =  ch(46,7) - 7*ch(25,7)

                          =  50159780

The answer to your problem is:

Sum[c(k), 20 <= k <= 100]  =  1800430741 - Sum[c(k), 0 <= k < 40]

                           =  1800430741 - 50159780

                           =  1750270961

To summarize the arithmetic which produced this number:

  21^7 - ch(26,7) - ch(46,7) + 7*ch(25,7)  =  1750270961

Scott
--
Scott Hemphill  hemph... at (no spam) alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear

Well the answer lies inside 20 per 5 all combinations, then
20,20,20,20,19,1 in all tank combinations, 20,20,20,20,18,2 and
20,20,20,20,18,1,1 and so forth. It can be worked out. There is most
assuredly a finite number to this, and I suspect it's less than a
billion total outcomes, therefore it is eminently solvable. Do not
assume units can be decimalled out, they are full units of 1. Just as
ships in real life wont worry about a drop, or a pound of water in a
ballast tank for being to small to worry about measuring for purposes
of staying afloat, we need not count the individual water atoms in an
unknown sized ship :P

Instead we can merely worry about a vague measure called a unit which
is always a whole number

The answer to your problem is:
21^7 - ch(26,7) - ch(46,7) + 7*ch(25,7) = 1750270961

Scott Hemphill wrote:
The answer to your problem is:
21^7 - ch(26,7) - ch(46,7) + 7*ch(25,7) = 1750270961

Here is a somewhat less elegant solution to the problem. More details
of the underlying math can be found in Fryer & Berman, Introduction to
Combinatorics, Academic Press 1972, especially chapter 4. AFAIK it's
out of print, but maybe it's available on the web somewhere.

7 ch[86, 7] + ch[107, 7]

Let c(k) be the number of combinations of the seven variables whose
sum is k.  So the answer to your problem is:

  Sum[c(k), 20 <= k <= 100]

We can now write:

  Sum[c(k), 0 <= k < 40]  =  Sum[ch(k+6,6), 0 <= k < 40] -
                             Sum[d(k), 21 <= k < 40]

                          =  Sum[ch(k+6,6), 0 <= k < 40] -
                             7*Sum[c(k), 0 <= k < 19]

                          =  Sum[ch(k+6,6), 0 <= k < 40] -
                             7*Sum[ch(k+6,6), 0 <= k < 19]

                          =  ch(46,7) - 7*ch(25,7)

                          =  50159780

The answer to your problem is:

Sum[c(k), 20 <= k <= 100]  =  1800430741 - Sum[c(k), 0 <= k < 40]

                           =  1800430741 - 50159780

                           =  1750270961

To summarize the arithmetic which produced this number:

  21^7 - ch(26,7) - ch(46,7) + 7*ch(25,7)  =  1750270961

I am going to admit I am a bit lost... What is c representing here?


Let c(k) be the number of combinations of the seven variables whose
sum is k.  So the answer to your problem is:

  Sum[c(k), 20 <= k <= 100]

So that when I do this math in excel, how do I represent Sum[ch(k
+6,6), 0 <= k < 40] - Sum[d(k), 21 <= k < 40] ??
Sums are easy enough, and k is easy enough, but ch? Less than equals
to is easy also... just representing c and ch is making me scratch my
head (admittedly poor sleep last few days, hence my lack of replies)

We can now write:

  Sum[c(k), 0 <= k < 40]  =  Sum[ch(k+6,6), 0 <= k < 40] -
                             Sum[d(k), 21 <= k < 40]

                          =  Sum[ch(k+6,6), 0 <= k < 40] -
                             7*Sum[c(k), 0 <= k < 19]

                          =  Sum[ch(k+6,6), 0 <= k < 40] -
                             7*Sum[ch(k+6,6), 0 <= k < 19]

                          =  ch(46,7) - 7*ch(25,7)

                          =  50159780

The answer to your problem is:

Sum[c(k), 20 <= k <= 100]  =  1800430741 - Sum[c(k), 0 <= k < 40]

                           =  1800430741 - 50159780

                           =  1750270961

This formula does look promising, but I admit that it's a bit past my
skills. I have yet to use (#,#) expressions and I do not know how to
use these properly. Could you assist in my understanding?

To summarize the arithmetic which produced this number:

  21^7 - ch(26,7) - ch(46,7) + 7*ch(25,7)  =  1750270961

Sorry if I seem ignorant.. I grew up in a poor area and have no formal
math education, so sometimes there is a glaring difference between
what I know and what I would like to know, as well as a difference
between what I can work out and write versus how others work out and
write math