Math Is Fun Forum

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

You are not logged in.

#1 2016-01-09 20:50:41

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Discrete mathematics

Hi,
I have a question about series (some members are repeated). I have a series, How can I find out if this series make all numbers up to summation of all members. Is there any formula?

for example {1, 1, 2, 4}; the subsets of this set can construct all numbers from 1 to 8.
{0, 1, 3, 4} cannot make all numbers ( 2 and 6 cannot be constructed).

question is how determine that if a set is capable to construct all numbers up to all members summation or not. a general formula would be appreciated.

Thank you.

Offline

#2 2016-01-09 21:22:11

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

These are partition problems and there are methods to determine whether or not a given set can sum to a number.


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

#3 2016-01-10 06:30:31

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

could you explain more or introduce me a reference.
your help is appreciated.

Offline

#4 2016-01-10 08:05:41

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

Hi;

It can be done with generating functions which for our purposes here are just polynomials that we multiply.

For instance:

I have the set {1,1,2,2,2,3,3,4,4,4,4}. I would like to know whether or not I can make a 19 from these numbers.

We check the coefficient of x^19 and see that it is an 8. That means there are 8 ways to make 19 using those numbers. Therefore it is possible for 19.


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

#5 2016-01-10 08:11:48

Relentless
Member
Registered: 2015-12-15
Posts: 631

Re: Discrete mathematics

That is extremely cool.

But how did you "generate" the first line?

Offline

#6 2016-01-10 08:15:49

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

Take a look at the differences in the powers for each parentheses, what do you see?


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

#7 2016-01-10 08:17:34

Relentless
Member
Registered: 2015-12-15
Posts: 631

Re: Discrete mathematics

I see the simple answer (:

Edit: Never mind, I am done asking silly questions for this morning!

Last edited by Relentless (2016-01-10 08:20:47)

Offline

#8 2016-01-10 08:19:39

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

Generating functions are a powerful technique used in combinatorics and elsewhere ( see my post in Computer mathematics, where they are used to sum a series.)


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

#9 2016-01-10 08:31:17

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

I got it. Thank you. math is always fascinating.
I need to implement this method to control a procedure (physical). It seems this requires heavy computation. Do you have any recommendation in programming this algorithm? our micro has limited computation power and I need to have efficient algorithm.

Offline

#10 2016-01-10 08:33:38

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

Even a small, old machine can do polynomial multiplication. What do you program in?

Relentless wrote:

Never mind, I am done asking silly questions for this morning!

There are no silly questions. Do not worry about that. Ask when you need help.


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

#11 2016-01-10 08:47:54

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

dsPIC30F4011. What I need is that I have to ensure that by existing number, all numbers up to summation of all members can be construct. no need to find specific number. There has to be a simple rule.
like the next number in the series be less than summation of the previous numbers. I thought a lot, but every way has a defect!!

P.S I need the answer (yes or no) in less than 10us.

Last edited by kappa_am (2016-01-10 08:50:02)

Offline

#12 2016-01-10 08:54:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

10 microseconds is very very fast. Machine language fast.

May I see a full complete example of a typical problem?


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

#13 2016-01-10 09:05:58

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

We have a series in which each number is per-unit voltage of a inverter. We have several inverters connected series to each other generating output voltage ( it look like a staircase waveform). for example 1, 1, 2, 2 means I have 4 inverter 2 with voltage 1V (per-unit) and 2 with 2V. by this inverters I can produce voltage levels from 1 up to 6. suddenly one of the inverters fails. the connection is in such a way that weight of the failed switch transfers to upper switch. suppose the third switch fails the series turns to 1, 1, 4. first I have to examine that am I able to generate all levels or not. then proceed to appropriate program. in this case I can not generate all levels. Because there is no way to generate 3.

Thanks for all your helps

Offline

#14 2016-01-10 09:10:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

Hi;

Is that the only type numbers you are dealing with 1,1,2,2?

I am getting offline for a bit, be back later. Have to eat something.


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

#15 2016-01-10 09:38:46

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

No, they can be any  positive integer number. But the failed switch is discriminated (provided by fault diagnosis system).

Enjoy your meal

Offline

#16 2016-01-10 10:50:12

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

When you say switch, is this being done by circuitry or by hand?


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

#17 2016-01-10 11:24:31

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

it is MOSFET, controlled by micro controller.

Offline

#18 2016-01-10 11:44:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

So you would need to make a circuit to do this? That is why you need a very simple formula?


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

#19 2016-01-10 11:55:23

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

actually this is a fault tolerant inverter, in which if a sub-module failed. the other modules try to maintain the performance using appropriate control. This is first step to examine that the remained operating circuit can compensate loss of that sub-module or not. Therefore, yes, simple as much as possible.

Offline

#20 2016-01-10 13:45:25

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

How many integers are we talking about in your set?


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

#21 2016-01-10 13:49:45

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

up to 20-25. However, a general formula is more desired.

Offline

#22 2016-01-10 14:51:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

20 - 25 numbers in the set?


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

#23 2016-01-10 16:47:02

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

yes. means the system has up to 25 sub-modules.

Offline

#24 2016-01-10 16:50:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete mathematics

I am afraid I do not know of anything faster than what I showed you. I do not think there is anything faster. Have you taken the problem over to the SE?


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

#25 2016-01-10 17:16:01

kappa_am
Member
Registered: 2013-12-20
Posts: 63

Re: Discrete mathematics

I kid of thinking of a solution. Lets suppose my system has M modules. each with voltage Vm. I think the system can maintain its functionality if the following conditions are true. I am not sure, please confirm.

1- for every K ( K is a number from 1 to M), there are K number of switch with weight less than 2^K
2-weight of the next switch to the failed switch, after adding weight of failed switch weight to it remain less than half of the summation of all members.

Does it work?
I am afraid, but I do not know what SE stand for.

Last edited by kappa_am (2016-01-10 17:16:25)

Offline

Board footer

Powered by FluxBB