login
A337272
Irregular triangle read by rows: T(n,k) = number of initially connected tournaments on n elements with k primary ascents.
1
1, 0, 1, 0, 1, 2, 1, 0, 1, 7, 13, 11, 5, 1, 0, 1, 14, 64, 144, 192, 167, 98, 38, 9, 1, 0, 1, 23, 187, 796, 2134, 3968, 5400, 5541, 4347, 2611, 1188, 399, 94, 14, 1
OFFSET
0,6
COMMENTS
This continues the enumeration of certain tournaments from A337271.
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.
The rows of this triangle are the coefficients of the polynomials g[n] (or g(n)) defined in the Mma code.
FORMULA
See Mma code.
EXAMPLE
Triangle begins:
1,
0,1,
0,1,2,1,
0,1,7,13,11,5,1,
0,1,14,64,144,192,167,98,38,9,1,
0,1,23,187,796,2134,3968,5400,5541,4347,2611,1188,399,94,14,1,
...
For example, there are 7 initially connected tournaments on 4 elements with 2 ascents; they're the tournaments whose ascents are
1->2,1->4; 1->2,2->4; 1->3,1->4; 1->3,2->4; 1->3,3->4; 1->4,2->3; 1->4,2->4.
Notice that this sequence has no row 0.
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 g[n]. *)
CROSSREFS
Cf. A337271.
Sequence in context: A176887 A076422 A295861 * A373571 A058998 A085324
KEYWORD
nonn,tabf,more
AUTHOR
N. J. A. Sloane, Sep 01 2020, based on a communication from Don Knuth, Aug 25 2020
STATUS
approved