Result: The number of compositions of 2n, say c_1+c_2+...c_k=2n, satisfy that Sum_(i=1..j) c_i
When you say directly, what do you mean? Give a bijective proof? Give a proof that both numbers satisfy the same recurrence? (The latter should be trivial, the former is the sort of thing that might be in "Proofs that Really Count", which would be a good first place to look to find how to answer your question).
You have already many papers on trees. Can you answer my following question? It may not be difficult for you.
Do you know the number of all spanning trees of a given class?https://www.researchgate.net/post/Do_you_know_the_number_of_all_spanning_trees_of_a_given_class
To Neil,
Thanks. I derived out the result from enumeration of lattice paths. But, it is not very clear from compositions of integers. So, by directly I mean directly working on compositions without translating it into another structure.
To Ricky,
Just to clarify... your example is for n=2, so 2n=4 and you found 3 compositions with the formula C(3,2). Looks like C(2n-1,n) instead of C(2n+1, n+1). Tried it too for n=3 and it gives C(5,3)=10 compositions. With no + signs to make it short : 111111, 11112, 11121, 1113, 11211, 1122, 1131, 12111, 1212 and 1221.
Thanks Christian, seems you are right. I will check the offset carefully and correct it later.
Now corrected!
To Yoshinori, it is an interesting problem, but I am sorry I do not know much about that at the moment.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics