Pretty straight forward, yet I didn't find how to approach such a problem. I tried constructing a solution from the reverse problem (Given a DAG count the number of paths between node 1 and node n), but It got me nowhere
2
-
$\begingroup$ How is $k$ related to $n$? $\endgroup$– Ben BarberCommented Sep 11, 2018 at 20:27
-
$\begingroup$ K and n are two indépendant variables $\endgroup$– Ahmed BennejiCommented Sep 11, 2018 at 23:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
I'll assume $1,2,\ldots,n$ are in topological order.
The solution is trivial for $n=1$ and doesn't exist for $n=2$ and $n=3$.
For $n=4$ use a transitive tournament and all paths: 14, 124, 134, 1234.
For $n>4$ take the solution for $n-1$ and apply it to vertices $2,\ldots,n$. Then add edges 12 and 1$n$.
OOPS, as Ben Barber suggested this is just the solution for $k=n$.
answered Sep 11, 2018 at 12:52
-
$\begingroup$ And how do I decompose k into a sum of those numbers ? plus why do you think there's no solution for n = 2 and n = 3 ? we can take n = 3 and we have a solution for k = 1 (straight line 1-2-3), and k = 2 (the straight line plus an edge from node 1 to node 3), and the same answer for n = 2 and k = 1. $\endgroup$ Commented Sep 11, 2018 at 13:05
-
$\begingroup$
$\endgroup$
2
So why isn't anyone suggesting the obvious? k edges from 1 to vertices 2 through k+1, and then either a path from 2 to n, or all remaining edges from every other vertex to n?
Gerhard "Am I Not Understanding This?" Paseman, 2018.09.11.
answered Sep 12, 2018 at 4:14
-
$\begingroup$ And if all edges are needed to be directed, certainly there are tournaments which give the solution? Gerhard "That Might Be Somewhat Harder" Paseman, 2018.09.11. $\endgroup$ Commented Sep 12, 2018 at 4:19
-
$\begingroup$ I don't quite understand but I suspect you are assuming $k\le n$. The number of paths can be as high as $2^{n-2}$. Also there is only one tournament which is a DAG so it can't make many different path counts. $\endgroup$ Commented Sep 12, 2018 at 10:56