No clue how to prove the following combinatorics identity.

- Curry

No clue how to prove the following combinatorics identity.

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- Curry

##### 1 Attachment

- Curry

part b.

- 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

@ganeshie8

- 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

Um, so if k is 1, then, we have (n-1)c1 right?

- Curry

or are you asking for somethign else?

- 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

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

Btw, good job on part a! thats really clever !

- Curry

SOrry, i'm not getting it at all.

- 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

And as a follow up, if I specify that the 4 comes *second*, what are the possibilities?

- Curry

um, for the first it'd be n-1

- Curry

4c2

- Curry

for the first it'd be 3*

- 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

OOO!

- Curry

ok that's what you mean, yes. I get that part. But, how od i relate it to the combinatorics?

- 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

So if I add all of those up, what am I actually counting?

- 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

what exactly is the process to "prove" it.
SHould I do induction or something else?

- 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

mhmm. But what method of proof should I use at all?

- 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

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

Oh i see! thank you so mucch!

- Curry

And for c, i got 6. Does that sound right?

- Curry

wait nvm, i got c, d, and e.

- anonymous

In the screenshot you sent, there's only a (c), but that answer should involve \(n\).

- Curry

gotchya. d and e were about econding and decoding this information.

- Curry

encoding*

- Curry

and actually, wouldn't C be n-1?

- Curry

cause for each bit, you'd have to ask the question, does it come before or after.

- 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

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

kk thank you!

- Curry

btw, are you a CS/CE/EE major by any chance?

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