|
I was trying to avoid making it too complicated, and this may be a language issue. The word 'random' has a strict and a loose meaning in English. The looser version means that there is some element of chance involved, it wasn't picked. In expressions such as "random variable" it is being used in this looser sense.
The stricter definition is that all possible results are equally likely (if in discrete probability) or has a uniform distribution (if in continuous probability). This is what is meant when talking about a random die, a random sample, or a random number generator.
I doubt either definition appears in a textbook, particularly in no undergrad or above level textbook. You would be better off looking in a normal English dictionary. Both definitions are used in- and outside mathematics, although in my experience, at uni level the stricter version is less common.
While "Zufall" does map onto "random" for some things it is far from perfect. I did not take a course on probability while in Germany so I am not certain on all the German terms in probability, but in conversational usage I would not translate "Zufall" or "zufaellig" as "random". A better translation of "Zufall" would be "accident" or "coincidence" or "fluke".
Side note: I'm sorry for my tone in my previous post. It was a bit terse. + Show Spoiler [Explanation] +I got annoyed by Simberto's use of "obviously". It is a pet peeve of mine when people use "obviously" (or "clearly" or any other such word) when writing about maths. It adds nothing but can be condescending. If the reader understands then they don't need to be told it is obvious, and if they don't understand then telling them it is obvious will not help them to understand.
|
In my experience "obviously" when used in a math lecture means "I don't want to prove this, do it yourself if you don't see why it is true". And i can see why it would annoy you, in fact it is a pretty common joke among the students of the maths department at my university to just randomly use "obviously" for stuff which very clearly is not obviously (Or to try to get by with not proving stuff that actually should be proven by saying it is obvious  ) to mock the professors which use it in the way you mentioned above.
I didn't intend to use it in that way, though, i wanted to use the more common meaning of "I don't think anyone would disagree"
And i think that sometimes telling someone that something is obvious may help with understanding. It means that you have to look for a simpler explanation as to why it is true. As soon as you start to need to use too many steps to figure it out, you are probably not following the right course when looking why something obvious is obvious. Most of the cases, especially when used in text books, it is infuriating. It usually takes me 20 minutes to understand the actual proof, and then another two hours to figure out why something which is called obvious is in fact obvious. And then i notice that instead of just writing that it is obvious, the author could also have use the same amount of words explaining the thing, and get pissed off.
|
This is probably way beyond anything I should be asking, but,
If I have N points on a cartesian plane,
is there a way to construct a function that describes either:
1.) all the lines between all the points
or
2.) the polygons that can be created by the points (I guess this would require more than one function....)
thanks.
|
On December 06 2017 09:43 travis wrote:
This is probably way beyond anything I should be asking, but,
If I have N points on a cartesian plane,
is there a way to construct a function that describes either:
1.) all the lines between all the points
or
2.) the polygons that can be created by the points (I guess this would require more than one function....)
thanks.
I think you should specify that question. Are you looking for an object in the shape of
f:{subsets of R^2 with N elements} -> R^2
(a1,....,aN) |-> (all points that are contained in the lines between a1,.....aN)
Because at least in theory, this is rather easy. You can define f((a1,....,aN)) by
f((a1,....,aN)) ={x in R^2| there are ai, aj, m in [0,1] such that x= ai +m*(aj-ai)}
Hope this can be understood. Havent learned how to embed tex here.
|
The question is what should map onto what with that function. If you have your points in R², and want to have a function that maps x coordinates onto the y coordinates of the lines/polygons that you have described, that is generally not possible. The reason for that is that a function of R-->R always maps one x onto exactly one y, but the lines you describe will in most cases have more than one point with the same x coordinates, but different y coordinates.
If you go more abstract, and first define a space of all possible lines in R², (Like for example by describing a line via starting and ending point, making the line basically an object of R^2xR^2), lets call it A
and then map a set of N points in R^2 (Which is an object in (R^2)^N ) onto an appropriate overspace of A, You will probably need something like A^((N-1)*N/2)
(N-1)*N/2 is the amount of lines between N points here if i am not mistaken
You can create a function f: R^2N ---> A^((N-1)*N/2) which maps (x1, y1) x....x(xN, yN) onto Line(x1,y1,x2,y2)xLine(x1,y1,x3,y3)x...xLine(xN-y,yN-1,xN,yN)
The same should be possible with polygons.
Thinking about this, this is probably way too stupid, and you should go with the above described map of R^2 ---> R^2, which also works.
|
Indeed, I should've put P(R^2) (the set of all subsets of R^2) as codomain instead of R^2 itself. I'm a bit in a hurry how, will comment later when I have more time.
|
Not quite sure what Simberto is on about. The input is clearly not R^2, but rather R^4 (x1, y1, x2, y2) for two points, R^6 for 3 points, etc., and the output are "characterizations of linepoints (or polygons)". Exactly what that's supposed to be beyond a set of points in R^2 I don't know, but lets be less restrictive and map them to equations, then we can do something like:
F(x1, y1, x2, y2) = [(y-y1)(x2-x1)=(y2-y1)(x-x1)]
if you can guarantee x1 and x2 are unequal you can rewrite this as a standard linear function, but I will leave it like this for now.
This is a general function, that for any two points will output a linear equation characterizing the line that goes through them. Now for N points, you have N^2 - N different combinations of two points, and thus you will get N^2 - N different equations as your output. I'm not quite sure what the exercise is supposed to be, but lets roll with it.
For the rest of the question, I am just as confused as ^^ those guys. You can of course, create an algorithm to find all possible triangles, quadrilaterals, etc. etc. that can be constructed for a set of N points. I'm not sure what precisely the time complexity is, but something like O(n^(n/2 +1)) is a good starting estimate: this is superexponential. So you should probably rethink why you need all possible polygons that can be drawn using N points in a plane.
As for the function representing this construction? It'd be some monstrosity of the kind f: R^2N -> P(R^2N)
|
On December 06 2017 20:50 Acrofales wrote:
Not quite sure what Simberto is on about. The input is clearly not R^2, but rather R^4 (x1, y1, x2, y2) for two points, R^6 for 3 points, etc., and the output are "characterizations of linepoints (or polygons)". Exactly what that's supposed to be beyond a set of points in R^2 I don't know, but lets be less restrictive and map them to equations, then we can do something like:
F(x1, y1, x2, y2) = [(y-y1)(x2-x1)=(y2-y1)(x-x1)]
if you can guarantee x1 and x2 are unequal you can rewrite this as a standard linear function, but I will leave it like this for now.
This is a general function, that for any two points will output a linear equation characterizing the line that goes through them. Now for N points, you have N^2 - N different combinations of two points, and thus you will get N^2 - N different equations as your output. I'm not quite sure what the exercise is supposed to be, but lets roll with it.
For the rest of the question, I am just as confused as ^^ those guys. You can of course, create an algorithm to find all possible triangles, quadrilaterals, etc. etc. that can be constructed for a set of N points. I'm not sure what precisely the time complexity is, but something like O(n^(n/2 +1)) is a good starting estimate: this is superexponential. So you should probably rethink why you need all possible polygons that can be drawn using N points in a plane.
As for the function representing this construction? It'd be some monstrosity of the kind f: R^2N -> P(R^2N)
I wanted to basically say the same thing as you. You can't solve this as the graph of a function R-->R
You can define a function as Mafe did, which maps from P(R²)--->P(R²).
Or you can define a function as i did, from R^2N---> R^((N-1)N/2). A problem i just noticed is that in this case, the order of the points in space and the order of the resulting lines are both relevant, which they don't actually need to be. Mafes solution is definitively more elegant.
I should note to my defense that i am currently sick and my brain feels muddy.
|
Maybe he is not looking for a function but a parametrization. Before we discuss any further he should provide more detail.
|
Sorry for not replying. You guys pretty much covered what I needed, and I moved on.
I do have a new question, you guys might find interesting.
Let's say I have a set of n numbers. I have a target, which is the sum of all n numbers.
Now let's say I create a new set with every k-combination of numbers. So, (n choose k) combinations. In this instance, let's say I choose 4. So I have (n choose 4) combinations made up of my n numbers.
How many combinations are there of my (n choose 4) combinations, that can equal my target sum?
Is there a general formula or easy way to calculate how many combinations can equal a target sum n, with any (n choose k) combinations?
Thank you!
edit: I should be more specific. I am asking about how many permutations there are to reach the sum, not combinations. Which makes me ask, is the answer (n/4)! ?
edit2: nope.. it couldn't be. Is it (n/4)!*(n choose 4) ? This is mindbending.
|
Clarification question:
S is the sum of all of your n numbers.
M is the sum of k <= n numbers.
You are looking for the amount of picks for which M=S for a given k?
If you have only positive numbers, that amount of combinations (lets call it q) is 0 if k <n, because any sum of k numbers will always be smaller than the sum of those numbers + n-k additional positive numbers. If k=n, q=1.
If you also allow 0 in your base set, the amount of combinations depends on how many 0 are in there.
If you also allow negative numbers, i doubt that there is a general solution. It depends on how many combinations of numbers there are which cancel out, and is gonna get complicated.
|
We started with a set of numbers (1, 2, .... n), where the elements increment by 1, sequentially. The elements are positive integers, starting at 1.
We have a target, S, which is the sum of all numbers in this set.
We take this set, and we create (n choose k) unique combinations.
We now have a set with n choose k combinations in it:
example, k = 4
our set: ((1,2,3,4),(1,2,11,n)...(11,23,73,88)...(7,55,386,n)) etc etc
Each element of this set has a value that is equal to the sum of the elements of the set.
So, (1,2,3,4) has a value of 11. (7,55,386,n) has a value of (448+n)
How many permutations are there by which we can take k elements from our new set, and reach our target sum S?
How many combinations are there? (probably the question I care more about)
Additional constraint:
How many permutations are there by which we can take k elements from our new set, in which every every element of every set is unique?
Thanks!
Edit: Sorry, I am back from lunch. I am less rushed now, and have edited my post to be specific.
|
Ah, i understand now.
That is a way more interesting question.
My first guess is to start categorizing stuff.
The target sum in your case is simply (n+1)n/2
If we start categorizing the sums in your second set, we need to take a look at how often each sum appears.
You have 1 times (k+1)k/2,
1 times 1+2+3+5 in the example, so one times (k+1)k/2 + 1
2 times 1+2+3+6=1+2+4+5, so two times (k+1)k/2+2 and so on
maybe it helps to see what different sums one gets in what amount to figure stuff out? Not really at a conclusion yet, and also gonna eat stuff now?
But i am still not convinced that there is a simple answer. Even for very small numbers, the stuff fluctuates pretty hard.
n=3, k=1 has one solution (k=1 and k=n always means there is only one solution since both sets are equal)
n=3, k=2 has none (second set is (1;2) (1;3) and (2;3)
n=4, k=1 has one solution
n=4, k=2 has three solutions, (1;2) (1;3) (1;4) (2;3) (2;4) (3;4), each of which has each number of the base set exactly once in it.
n=4, k=3 has no solutions
If there is a general solution, it would have to factor in things like how easily k fits into n.
|
Well, I calculated the solution as
((n choose k) * ((n-k) choose k))/(n/k) combinations that will equal our sum,
(n choose k) is based on each individual starting element, and then ((n-k) choose k) are the combinations of what is left that can be combined with the starting element to form the sum. But then this all must be divided by (n/k), otherwise we will repeat with starting elements that have already been used in a previous combination.
and then permutations would be equal to combinations * k!, which is the possible orderings of the given combination.
so yeah, I did this and then I realized I wasn't considering duplication of elements. For example, making a sum of 45 with
(1,2,3),(6,7,8),(1,8,9)
so I will be impressed if anyone can solve how many combinations there are that don't include repeats.
(I'll also be impressed if I didn't screw up my above conclusions)
|
I guess it could be said that when you have a combination, like above, trying to reach 45 with 3 combinations of 3 numbers, with no repeats, then you must use every number in n once.
so we can say there is 9 choose 3 possibilities for set 1. Then 6 choose 3 possibilities for set 2. Then only 1 possibility for set 3.
So instead of ((n choose k) * ((n-k) choose k))/k
It needs to be [the product from i = 0 to n/3 of: ((n-3i) choose k) ]/(n/k) ?
Does this look right?
|
That sounds correct, but it only solves that questions of what to do without allowing doubles.
And you can further simplify your result.
n choose k = n!/(k! (n-k)!)
n-k choose k = (n-k)! / k! (n-2k)!
n-2k choose k = (n-2k)! / k! (n-3k)!
with the last factor being
n-(n/k - 1)k choose k = (n-(n/k-1)k)! / k! (n-n)!
so with all the (n-ik)! dropping from your product, that only leaves
n!/((n/k)k!) or k*n!/n*k!
Edit which is (n-1)! / (k-1)! /Edit
Edit2 Crap i suck at calculating, it is actually n! / k!^(n/k) /Edit2
Could be that i am missing something, but that should generally work for your result
And i have no idea how to solve the general problem, or if it is even possible. With the above simplification of only choosing once, any problem where k does not divide n has 0 solutions.
|
I'm not sure what you want. Is it this?
![[image loading]](https://i.imgur.com/VNJD568.gif)
And then you want to know how many such B there are. Is that right?
If so, then for k = 1 there are no solutions, since the highest number you can pick is B = {n} and that is not big enough.
But your number of combinations would be (using your first try)
((n choose 1) * ((n-1) choose 1))/(n/1)
= n * (n-1) / n
= n-1
If you don't want repeated elements (in the elements of B) then it can only possibly work if k is the square root of n. Since you can only include every number once, you need to have all of the numbers. At which point the question becomes 'how many ways are there of splitting k^2 elements into k sets, each of size k.'
The answer to that is ![[image loading]](https://i.imgur.com/ZB04Ww1.gif)
because you have k^2! ways of listing 1 , ... , k^2 and then you say the first k are the first set, the second k the second, etc. But then I don't care about the order within the first k, so I divide by k!. I have to do this for all k sets of k, which leads to (k!)^k. Finally, I can swap the first set of k with the second set of k, etc. which gives another k! factor on the bottom.
Although, I think I have screwed that up...
|
@Travis, while my combinatorics is far from amazing, this question looks quite hellish XD
Part of my motivation for this is that this turns into (or at least looks like it) a partition problem, and even finding the partitions of S with no constraints is tricksy.
However your fully constrained question looks a lot more achievable. If both of your k's are the same (so each combination mini-sum is of a k subset of (1, 2, ..., n) and you now want to take k of these k-subsets, and add all k mini-sums to get a total of S) and S is the sum from 1 to n, then you have a situation where you will need have each element of (1, 2, ..., n) appear exactly once.
This is because, as per uniqueness, you can't repeat any number, so you need every number from 1 to n to appear in exactly one combination. (Again hoping I'm reading your question right).
This leads to the following observation: your constrained question only has ANY solution when n = k^2. (k subsets, each of k elements, all elements unique). Because if not, you can't even partition all of (1, 2, ..., n) across the k-subsets taken.
So the problem reduces to all the ways of arranging (1,2, ..., n), in k boxes, each box having k elements. But these arrangements correspond one to one with permutations of (1, 2,..., n). (*)
Which is not particularly interesting
Which leads me to conclude I have misread something :| Although your additional constraint may be strong enough that this must be the case.
If this wasn't at all clear I can type something up in LaTeX that is a bit less of a mess.
EDIT: to see (*), first note that, when we "remove" the boxes, we can't possibly get an arrangement that isn't already a permutation of (1,2,...,n), and that if we "impose" the boxes, every permutation of (1,2,...,n) is also a different box arrangement. Although I'm more dubious on this than I'd like =/
EDIT 2: RIP, no. This assumes permutations all the way through, not permutations of the set of combinations. So... I lie. I'll leave it up but I lie. The previous answer explains this better and gives an answer I can't yet see to be wrong.
|
On December 15 2017 04:38 Melliflue wrote:I'm not sure what you want. Is it this? And then you want to know how many such B there are. Is that right? If so, then for k = 1 there are no solutions, since the highest number you can pick is B = { n} and that is not big enough. .
there is a miscommunication here. we make n choose k combinations, but these combinations are of size n/k, not of size k.
so for k = 1, we would a single set of (1,2,3...n) which would be our single solution.
|
On December 15 2017 07:21 travis wrote:Show nested quote +On December 15 2017 04:38 Melliflue wrote:I'm not sure what you want. Is it this? And then you want to know how many such B there are. Is that right? If so, then for k = 1 there are no solutions, since the highest number you can pick is B = { n} and that is not big enough. . there is a miscommunication here. we make n choose k combinations, but these combinations are of size n/k, not of size k. so for k = 1, we would a single set of (1,2,3...n) which would be our single solution.
The reasoning for needing all numbers from 1 to n appearing exactly once still holds, so I think you can easily adapt the solution here.
You will still have k of the combinations appearing (to get each element exactly once, you need exactly k subsets of size n/k), whose order we do not care about. And each combination now has n/k elements, and again, we do not care about the order of elements within the combination.
So I think this works?
![[image loading]](http://rogercortesi.com/eqn/tempimagedir/eqn2830.png)
EDIT: If you *do* care about the orders of the combinations (but not the elements within them), then just don't divide by the k!
EDIT 2: WTF the site I'm using for latex images changed it.
It was n!/(((n/k)!)^k)(k!)
|
|
|
|
|
|
EPT
