Curry
  • Curry
No clue how to prove the following combinatorics identity.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Curry
  • Curry
1 Attachment
Curry
  • Curry
part b.
anonymous
  • anonymous
what did you get for part a)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

Curry
  • Curry
@ganeshie8
anonymous
  • anonymous
That's right - so if you take into consideration the hint given for part (b), what are your thoughts? So for example, what does the k=1 term represent?
Curry
  • Curry
Um, so if k is 1, then, we have (n-1)c1 right?
Curry
  • Curry
or are you asking for somethign else?
anonymous
  • anonymous
That's right, but what I meant was - In the context of mountain permutations, if we let k represent the location of the "peak" (the largest number in the permutation), the k=1 term is equal to 1. What do you know about the permutation if the largest number appears first?
ganeshie8
  • ganeshie8
Notice also that the sequence of numbers appearing to the left of the largest number must be in increasing order. Lets fix the position of largest number. If the position of largest number is "k", then there will be "k-1" number to the left of the largest number. How many ways can you choose "k-1" numbers form the available "n-1" numbers ? (excluding the largest number)
ganeshie8
  • ganeshie8
Btw, good job on part a! thats really clever !
Curry
  • Curry
SOrry, i'm not getting it at all.
anonymous
  • anonymous
For example, if we're dealing with a mountain permutation of size 4, if I specify that the 4 comes first, then what *must* the permutation be?
anonymous
  • anonymous
And as a follow up, if I specify that the 4 comes *second*, what are the possibilities?
Curry
  • Curry
um, for the first it'd be n-1
Curry
  • Curry
4c2
Curry
  • Curry
for the first it'd be 3*
anonymous
  • anonymous
If the 4 comes first, there is only one possibility - 4321. If the four comes second, there are now three possibilities - 1432, 2431, and 3421.
Curry
  • Curry
OOO!
Curry
  • Curry
ok that's what you mean, yes. I get that part. But, how od i relate it to the combinatorics?
anonymous
  • anonymous
If we kept going, we'd find that: -If the four comes first (k=1), there's one possible permutation -If the four comes second (k=2), there are three possible permutations -If the four comes third (k=3), there are three possible permutations -If the four comes last (k=4), there is only one possible permutation
anonymous
  • anonymous
So if I add all of those up, what am I actually counting?
Curry
  • Curry
Sorry for the delayed response. Had to do something. OO! it's pascals triangle. ok ok. So do I just use the pascal's formula here?
Curry
  • Curry
what exactly is the process to "prove" it. SHould I do induction or something else?
anonymous
  • anonymous
I don't think you're being asked for a rigorous proof - more the realization that the left hand side is simply counting the the number of mountain permutations of length n by considering each possible location of the "peak" separately, you know what I mean?
Curry
  • Curry
mhmm. But what method of proof should I use at all?
Curry
  • Curry
i feel like induction might not be the best way to go here since you said it doesn't have to be rigoruous. But we cna't just do regular algebra proof.
anonymous
  • anonymous
It's not really a proof. The answer I would give would go something like this: "The \(k^{th}\) term in the summation is the number of mountain permutations of length \(n\) that are possible if \(n\) (the largest number in the permutation) occurs in position \(k\). Because \(n\) must appear somewhere between position 1 and position \(k\), the sum over all of the terms is simply the total number of mountain permutations of length \(n\). Using a recursion relation, we found in part (a) that the total number of mountain permutations of length \(n\) is \(2^{n-1}\), so it follows that the two sides of the equation are equal."
Curry
  • Curry
Oh i see! thank you so mucch!
Curry
  • Curry
And for c, i got 6. Does that sound right?
Curry
  • Curry
wait nvm, i got c, d, and e.
anonymous
  • anonymous
In the screenshot you sent, there's only a (c), but that answer should involve \(n\).
Curry
  • Curry
gotchya. d and e were about econding and decoding this information.
Curry
  • Curry
encoding*
Curry
  • Curry
and actually, wouldn't C be n-1?
Curry
  • Curry
cause for each bit, you'd have to ask the question, does it come before or after.
anonymous
  • anonymous
Yes indeed it would. There are many ways that information could be encoded and decoded. And yes, that's an excellent way to do it.
Curry
  • Curry
and as long as you know it's before or after, you can figure out the rest and place the biggest nunmber accordingly. Since they have to be inc or dec.
Curry
  • Curry
kk thank you!
Curry
  • Curry
btw, are you a CS/CE/EE major by any chance?
anonymous
  • anonymous
No problem, I enjoyed thinking about this for awhile. No, I'm a physics PhD student, but I do specialize in computational physics and computer simulation.

Looking for something else?

Not the answer you are looking for? Search for more explanations.