Question

No clue how to prove the following combinatorics identity.

Answer 1

part b.

Answer 2

what did you get for part a)

Answer 3

@ganeshie8

Answer 4

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?

Answer 5

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

Answer 6

or are you asking for somethign else?

Answer 7

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?

Answer 8

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)

Answer 9

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

Answer 10

SOrry, i'm not getting it at all.

Answer 11

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?

Answer 12

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

Answer 13

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

Answer 14

4c2

Answer 15

for the first it'd be 3*

Answer 16

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.

Answer 17

OOO!

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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?

Answer 22

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

Answer 23

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?

Answer 24

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

Answer 25

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.

Answer 26

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

Answer 27

Oh i see! thank you so mucch!

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

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

Answer 32

encoding*

Answer 33

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

Answer 34

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

Answer 35

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.

Answer 36

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.

Answer 37

kk thank you!

Answer 38

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

Answer 39

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.