Register to reply

Does this equation have a name?

by gamow99
Tags: equation
Share this thread:
gamow99
#1
Sep3-14, 06:07 PM
P: 4
I'm trying to figure out how many times my computer will have to loop through an array. I'm building a logic calculator so it's checking contradictions. If there are four sentences, a b c d, then one has to check the following combinations to see if there is a contradiction

ab
ac
ad
bc
bd
cd

The equation seems to be, let n = the number of sentences:

(n - 1) + (n - 2) + (n - 3)

But that's not a good equation because it does not inform us how many things to add together.

If there are six sentences then the equation would be

(n - 1) + (n - 2) + (n - 3) + (n - 4) + (n - 5)

There has to be a better way to write that equation.
Phys.Org News Partner Mathematics news on Phys.org
Researcher figures out how sharks manage to act like math geniuses
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
jz92wjaz
#2
Sep3-14, 06:28 PM
jz92wjaz's Avatar
P: 45
In probability, it looks like it would be written as 4 choose 2, meaning that you have 4 sentences and choose 2 of them. The equation gives the number of unique results (ab is the same as ba). Google "Combination".
...
#3
Sep6-14, 01:36 PM
P: 9
Hey, computer scientist here. Cool project you're working on. I stumbled across this pattern while messing around with tabular K-map simplification (boolean logic):

You have 4 variables (but this can be generalized to n variables) and are trying to find the total number of associative expressions such that AB = BA. (Looping through for A AND B as well as B AND A would be inefficient)

This problem is analogous to finding the number of lines between a given number of points (see below). The formula is
$$
\frac{n^2-n}{2}
$$

Send me a PM: I'd like to take a closer look at your logic calculator.




*plus sign changed to minus sign as per jz92's post
Attached Thumbnails
3case.png   4case.png  

jz92wjaz
#4
Sep6-14, 03:46 PM
jz92wjaz's Avatar
P: 45
Does this equation have a name?

The general equation for evaluating the number of unique combinations when you select k items from a set of n items is:

$$
\frac{n!}{(n-k)!*k!}
$$

n choose 2 is
$$
\frac{n!}{(n-2)!*2!}
$$
Simplified, it is:
$$
\frac{n^2-n}{2}
$$

Comparing each combination of 2, where there are 4 sentences, comes out to a total of (16-4)/2, or 6 comparisons. This, of course, requires that the loops are set up in a way that you never test the same combination twice.


Register to reply

Related Discussions
Relationship between Simple Harmonic Motion Equation and Wave Equation General Math 1
Legendre equation , the Bessel equation and Sturm Liouville equation Calculus 4
Solutions to Cubic equation that dont diverge when reduced to linear equation General Math 1
Deriving equation for ideal fluid flow problem (~bernoulli equation) Introductory Physics Homework 0
Deriving the continuity equation from the Dirac equation (Relativistic Quantum) Advanced Physics Homework 3