|
| |
|
|
A337271
|
|
Irregular triangle read by rows: T(n,k) = number of tournaments on n elements with k primary ascents.
|
|
1
|
|
|
|
1, 1, 1, 1, 1, 4, 2, 1, 1, 11, 18, 17, 11, 5, 1, 1, 26, 94, 159, 209, 217, 172, 98, 38, 9, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
More precisely, a tournament on {1,...,n} is a digraph with arcs between i and j for each i<j; either i->j or i<-j. The arc is an "ascent" if i->j.
It is a "primary ascent" if it's an ascent for which i and j belong to the same "initially connected component".
The initially connected components of a tournament on {1,...,n} are defined as follows: One component consists of everything reachable from 1. Remove that component; the next component, if any vertices remain, consists of everything reachable from the smallest remaining vertex. And so on.
For example, suppose n=4 and 1<-2, 1->3, 1<-4, 2->3, 2->4, 3<-4.
There are two initially connected components: {1,3} and {2,4}.
There are three ascents: 1->3, 2->3, 2->4. But only 1->3 and 2->4 are primary; 2->3 doesn't count, because 2 and 3 are in different components.
Hence this example is one of the 18 tournaments on 4 elements with 2 primary ascents.
|
|
|
LINKS
|
|
|
|
FORMULA
|
See Mma code.
|
|
|
EXAMPLE
|
Triangle begins:
1,
1,
1,1,
1,4,2,1,
1,11,18,17,11,5,1,
1,26,94,159,209,217,172,98,38,9,1,
...
|
|
|
MATHEMATICA
|
(* first create the Gaussian binomial coefficients {n\choose k}_q *)
gb[n_, k_]:=gb[n, k]=Expand[q^k gb[n-1, k]+gb[n-1, k-1]]
gb[n_, 0]:=1
gb[0, k_]:=0
(* now define the gf for a single component *)
g[n_]:=g[n]=Expand[(1+q)^Binomial[n, 2]-Sum[gb[n-1, k]g[n-k](1+q)^Binomial[k, 2], {k, n-1}]]
(* now define the gf for a full tournament *)
h[n_]:=n!Coefficient[Series[Exp[Sum[g[k]z^k/k!, {k, n}]], {z, 0, n}], z, n]
(* The elements of row n are the coefficients of h[n]; for example, h[3]=1+4q+2q^2+q^3. For g[n] see A337272.*)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
