My professor gave some problems for those of us that think we will go on to graduate school or take graduate enumeration. I've done pretty well on the rest, but can't figure out what these are asking. I guess I'm not really looking for help on how to solve them, although I will appreciate hints, but I was wondering if anyone could point me to a book or a pdf I could read up on some of the ideas in these problems I've never seen described/defined prior to this. Or if you could give better definitions yourself. Anything will be appreciated.
Enumeration Exercises
- Thread starter SamuelB
- Start date
I assume your professor distributed these because they require some more thought than other exercises you are assigned. As I assume these are recreational for you, what have you thought of?
For number 1, you might want to take notice of Pascal's triangle, or discover the symmetry and increasing/decreasing nature of the choose function. Since s<t≤⌈n/2⌉, you can conclude (tn)−(sn)≥0 where equality will hold if t=(n+1)/2, t−s=1 and n is odd. For a subset of size s there are at least half the elements in [n] to play with to turn it into a subset of order t.
As far as resources, I have seen similar problems in several kinds of books from different disciplines. Books on elementary number theory, combinatorics or discrete mathematics are your best bets. Permutations are covered in overwhelming detail in Abstract Algebra by Dummit and Foote, but require knowledge of group theory.
For number 1, you might want to take notice of Pascal's triangle, or discover the symmetry and increasing/decreasing nature of the choose function. Since s<t≤⌈n/2⌉, you can conclude (tn)−(sn)≥0 where equality will hold if t=(n+1)/2, t−s=1 and n is odd. For a subset of size s there are at least half the elements in [n] to play with to turn it into a subset of order t.
As far as resources, I have seen similar problems in several kinds of books from different disciplines. Books on elementary number theory, combinatorics or discrete mathematics are your best bets. Permutations are covered in overwhelming detail in Abstract Algebra by Dummit and Foote, but require knowledge of group theory.
Last edited:
Thanks for that help. It started me thinking about it a little more. I looked through an algebra book too to get some ideas on that problem.
My problems with 2 is that I really do not understand what it is asking. The second sentence in number 2 reads to me like "P is decreasing if every P is decreasing," and that doesn't make sense to me. I think I'm just misunderstanding the question.
Number 3, I cannot think of a good way to count these.
My problem is that these do not really relate to what we have done in class. We have not built up to these problems, so I cannot look through anything we've done and figure them out. The other ones were similar to problems I've seen.
My problems with 2 is that I really do not understand what it is asking. The second sentence in number 2 reads to me like "P is decreasing if every P is decreasing," and that doesn't make sense to me. I think I'm just misunderstanding the question.
Number 3, I cannot think of a good way to count these.
My problem is that these do not really relate to what we have done in class. We have not built up to these problems, so I cannot look through anything we've done and figure them out. The other ones were similar to problems I've seen.
So, I've done some more work with problem 2 and thought about it a little differently. I have tried examples, just to get an idea of what I am doing. If I have a finite number of elements in S and it is strictly increasing then the decreasing partition would be each of them partitioned separately. The maximum length of the increasing subsequence would have to be the minimum size of a decreasing partition.
I do not know how to translate this to other ideas.
I do not know how to translate this to other ideas.