Originators: K. Brooks Reid and Michael Santana (presented by Michael Santana - REGS 2011)
Definitions: A tournament is an orientation of a complete graph. A tournament is transitive if it has no cycles. The vertices of a transitive tournament can be placed vertically so that all the arcs are directed downward. A source (respectively, a sink) is a vertex whose in-degree (respectively, out-degree) is zero. In such vertical arrangement of a transitive tournament, the unique source and unique sink are located at the top and bottom of the arrangement, respectively.
Question: How many sets of edges in a transitive tournament on $n$ vertices decompose into $k$ arc-disjoint paths from the source to the sink?
Background: This problem is equivalent to finding the number of "$k$-upset forms" of order $n$. Brualdi and Li [BL] introduced upset tournaments in terms of tournament matrices and characterized them in terms of their score sequences. They also showed that the number of 1-upset forms is $2^{n-2}$. Poet and Shader [PS] defined upset tournaments in terms of their score sequences and characterized them in terms of their structure. In the same paper, they proved that the number of non-isomorphic upset tournaments of order $n$ is $2^{n-4}$. Santana [S] extended the definition and characterization to $k$-upset tournaments and attempted to count the $k$-upset forms for $k$ at least 2. With help from the Online Encyclopedia of Integer Sequences [OEIS], he showed that the number of 2-upset forms of order $n$ satisfies the recurrence $a_n = 4a_{n-1} - 2a_{n-2}$. He also showed that the number of non-isomorphic $k$-upset tournaments of order $n$ is one-fourth the number of $k$-upset forms of order $n$ when $k\ne(n-1)/2$.
Comments: Gregory Puleo and Dan Cranston derived recurrences for $k\in\{3,4,5\}$. For example, for $k=3$ the counting sequence satisfies $a_n=8a_{n-1}-16a_{n-2}+10a_{n-3}$. It is fairly certain that for every $k$ a recurrence can be found from the characteristic equation of a matrix for a particular system of recurrences of order 1.
References:
[BL] Brualdi, Richard and Li, Qiao. The interchange graph of tournaments
with the same score vector. Progress in graph theory (Waterloo, Ont., 1982),
129-151, Academic Press, Toronto, ON, 1984.
[PS] Poet, Jeffrey and Shader, Bryan. Score certificate numbers of upset
tournaments. Discrete Appl. Math. 103 (2000), 177-189.
[S] Santana, Michael. Two investigations on tournaments: intersection spectra
and score sequences. Master's thesis, California State University San Marcos
(2011).
[OEIS] Sloane, Neil. The On-Line Encyclopedia of Integer Sequences, published
electronically at http://oeis.org, 2011, Sequence A007070.