Discrete mathematics

kappa_am · 2016-01-09 20:50:41

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.

bobbym · 2016-01-09 21:22:11

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

kappa_am · 2016-01-10 06:30:31

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

bobbym · 2016-01-10 08:05:41

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.

Relentless · 2016-01-10 08:11:48

That is extremely cool.

But how did you "generate" the first line?

bobbym · 2016-01-10 08:15:49

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

Relentless · 2016-01-10 08:17:34

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)

bobbym · 2016-01-10 08:19:39

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.)

kappa_am · 2016-01-10 08:31:17

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.

bobbym · 2016-01-10 08:33:38

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.

kappa_am · 2016-01-10 08:47:54

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)

bobbym · 2016-01-10 08:54:10

10 microseconds is very very fast. Machine language fast.

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

kappa_am · 2016-01-10 09:05:58

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

bobbym · 2016-01-10 09:10:54

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.

kappa_am · 2016-01-10 09:38:46

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

Enjoy your meal

bobbym · 2016-01-10 10:50:12

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

kappa_am · 2016-01-10 11:24:31

it is MOSFET, controlled by micro controller.

bobbym · 2016-01-10 11:44:54

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

kappa_am · 2016-01-10 11:55:23

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.

bobbym · 2016-01-10 13:45:25

How many integers are we talking about in your set?

kappa_am · 2016-01-10 13:49:45

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

bobbym · 2016-01-10 14:51:10

20 - 25 numbers in the set?

kappa_am · 2016-01-10 16:47:02

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

bobbym · 2016-01-10 16:50:10

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?

kappa_am · 2016-01-10 17:16:01

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)

Math Is Fun Forum

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

Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

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

Re: Discrete mathematics

Board footer