Timeline for How many words are there such that some word $X$ is subsequence of them?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2016 at 18:13 | comment | added | Nate Eldredge | @MatthewQuartz: Note that this is a research level site, so you should expect answers to assume a research level knowledge of a field. If that's not what you want, then math.stackexchange.com might be a better site for your question. | |
| Oct 15, 2016 at 17:30 | comment | added | Benjamin Steinberg | I do these kinds of things by generating functions. Maybe somebody else can give the recursion explicitly. | |
| Oct 15, 2016 at 16:49 | comment | added | Matthew Quartz | Could you please provide some explanation which would require only basic understanding of combinatorics? | |
| Oct 15, 2016 at 15:02 | comment | added | Matthew Quartz | Thank you for your answer, but I really don't understand it, because it is so complex to me, because I don't know much about generating functions. I don't need explicit formula, some kind of recursion would suffice. | |
| Oct 15, 2016 at 15:00 | vote | accept | Matthew Quartz | ||
| Oct 15, 2016 at 16:14 | |||||
| Oct 15, 2016 at 14:48 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
added 333 characters in body
|
| Oct 15, 2016 at 14:38 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
added 236 characters in body
|
| Oct 15, 2016 at 14:25 | comment | added | Benjamin Steinberg | Keeping my notation, draw a digraph with $k+1$ nodes with a $m-1$-loops at each node except the last, which has $m$ loops, and an arc from node $i$ to node $i+1$. The edge from $i$ to $i+1$ is labelled by letter $i$ of $w$. The loops are labelled by the remaining letters. Then I claim that words containing $w$ as a subsequence are in bijection with labels of directed paths from node $1$ to node $k+1$ which is bijection with directed paths from node $1$ to node $k+1$. One counts these using the transfer method in Stanley's book. | |
| Oct 15, 2016 at 14:19 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
added 1 character in body
|
| Oct 15, 2016 at 14:19 | comment | added | Benjamin Steinberg | You can set up a linear system of difference equations | |
| Oct 15, 2016 at 14:14 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
added 136 characters in body
|
| Oct 15, 2016 at 14:13 | comment | added | Matthew Quartz | Is there any other way not requiring knowledge about automatons? I know nothing about it. | |
| Oct 15, 2016 at 14:09 | history | answered | Benjamin Steinberg | CC BY-SA 3.0 |