Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-01-25 12:56:51

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

A multivariable gf

s = {12, 7, 10, 9, 7, 13, 11, 9, 8, 13, 10, 10, 8, 11, 11, 9, 7, 11, 9, 12}

How many combinations can be made, when 6 numbers are picked from s without replacement and the total of all 6 is less than or equal to 60?

We can think of this as solving 7a+8b+9c+10d+11e+12f+13g <=60 and a+b+c+d+e+f+g=6 with the conditions a,b,c,d,e,f,g>=0. This suggests a multivariable gf approach. For that we would need all the coefficients of

To get them we need to do some summation manipulations to form the gf.

This is the gf

Now that we have the gf we can compute the coefficients using M but I liked using the summation form instead.

gf = Expand[Sum[(x*y^7)^a, {a, 0, 3}] Sum[(x*y^8)^b, {b, 0, 2}] Sum[(x*y^9)^c, {c, 0, 4}] Sum[(x*y^10)^d, {d, 0, 3}] Sum[(x*y^11)^ e, {e, 0, 4}] Sum[(x*y^12)^f, {f, 0, 2}] Sum[(x*y^13)^g, {g, 0, 2}]];
(Cases[(List @@ gf), x^6 y^n_ /; n <= 60]) /. x -> 1 /. y -> 1 // Total
Cases[(List @@ gf), a_*x^6 y^n_ /; n <= 60] /. x -> 1 /.y -> 1 // Total

Adding them up we get 353.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#2 2015-01-25 13:57:01

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,018

Re: A multivariable gf

Thanks so much for this. I was trying to figure out a GF for this problem, but got nowhere.

By the way, I think \vdots might look better.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#3 2015-01-25 13:59:13

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

Re: A multivariable gf

There is a nice pdf that I downloaded that showed me how.

Where should I put the cdots?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#4 2015-01-25 14:06:47

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,018

Re: A multivariable gf

I like the idea of one variable tracking which numbers were picked and the other how many of each was taken.

Not \cdots but \vdots. Right beneath the second line of LaTeX, instead of those three dots.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#5 2015-01-25 14:09:25

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

Re: A multivariable gf

I like the idea of one variable tracking which numbers were picked and the other how many of each was taken.

That type problem had me stumped for many years but now it seems obvious.

Oh you mean vertical dots.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#6 2015-01-27 00:06:24

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,429
Website

Re: A multivariable gf

I am wondering what tactical advantage a gf has...

49ef3419_o.png

Last edited by Agnishom (2015-01-27 00:07:20)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#7 2015-01-27 04:48:43

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

Re: A multivariable gf

I am wondering what tactical advantage a gf has...

A gf turns a combinatorics problem into a computational one. This idea is one of the cornerstones of EM.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#8 2015-01-27 05:11:21

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,429
Website

Re: A multivariable gf

What is your fast algorithm to compute the required coefficient?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#9 2015-01-27 05:27:28

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

Re: A multivariable gf

In this problem, or in general?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#10 2015-01-27 05:36:58

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,429
Website

Re: A multivariable gf

In this problem?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#11 2015-01-27 05:39:44

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

Re: A multivariable gf

There are at least 3 ways that M can get at these coefficients, one is already posted.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#12 2015-01-27 05:46:42

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,429
Website

Re: A multivariable gf

How does M get them?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#13 2015-01-27 05:53:40

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 107,133

Re: A multivariable gf

One way uses the series instead see post #1.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB