exotic hearth
Can someone pls explain why the binomial coefficient in eulerian numbers closed form is (n+1 choose j) as per me it should be (n+j choose j) as (n+1 choose j) chooses distinct gaps to put dividers in from the n+1 gaps while n+j choose j lets you put multiple dividers in one gap which i think is necessary in the inclusion exclusion to filter out cases where we have two consecutive subsequences are empty. would really appreciate if you could explain what im missing.
jolly shaleBOT
small imp
you can broadly think about Eulerian numbers as follows: place k - 1 dividers and allocate each element of [n] = {1, ..., n} into one of the k 'blocks' and then rearrange the elements of each block in ascending/descending order (depending on whether your definition uses rises or falls)
there's a bit more to it but that's kind of a way to view Eulerian numbers; you should be able to find a proof of it in Bona's book Combinatorics of Permutations
exotic hearth
Ye that’s what I was doing
For permutation of n elements with k descents we will have k+1 increasing subsequences
Each of the n elements has k+1 choices for which sequence to go to
And then we do inclusion exclusion to filter out when a subsequence is empty of the minimum of the ith subsequence is greater than the max of the i-1th subsequence because we won’t get the descent we wanted in these cases
My argument was how can it be (n+1 choose j) if we have two consecutive empty subsequences since then we are choosing not distinct gaps to place the dividers. Instead we are placing two dividers in the same gap
small imp
the number of permutations of [n] with k - 1 descents is in bijection with the number of "k-augmented words" with no "extraneous dividers", where a k-augmented word is a permutation of [n] with k - 1 dividers where each block is written in increasing order
and then you're applying PIE on the number of k-augmented words, which allows dividers to be right next to each other
exotic hearth
Ye if dividers can benext to each each other then it’s (n+j choose j) instead of (n+1 choose j)
small imp
it'll be C(n + 1, j); choosing where the dividers are is equivalent to saying "find the number of j subsets of {0, 1, ..., n}" <- imagine this set as the set of all possible placements of dividers
exotic hearth
But if dividers can be next to each other then we are placing j of them in the n+1 gaps of[n] which can be done in (n+j choose j)
It’s only (n+1 choose j) if you’re saying there is max one divider in each gap
And if you have one max idk how would you account for cases with two consecutive empty subsequences
small imp
It’s only (n+1 choose j) if you’re saying there is max one divider in each gap
actually this is right
the number of permutations of [n] with k - 1 descents is equivalent to the number of words with k dividers such that each block is in increasing order and none of the dividers are "extraneous"
we call a divider extraneous if deleting it gives you one less number of dividers and each block is still in increasing order
and i think the literature calls it k-augmented words with no extraneous walls
exotic hearth
Wait what am i missing in my logic tho
small imp
it's not clear to me that putting multiple dividers in the same gap gives you permutations with k descents
well it doesn't
but it's not clear to me how that is counted when you're counting the objects you need to count
exotic hearth
Do you agree with the subsequence part