login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Irregular triangle read by rows: T(n,k) = number of initially connected tournaments on n elements with k primary ascents.
1

%I #13 Sep 01 2020 18:42:08

%S 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,

%T 187,796,2134,3968,5400,5541,4347,2611,1188,399,94,14,1

%N Irregular triangle read by rows: T(n,k) = number of initially connected tournaments on n elements with k primary ascents.

%C This continues the enumeration of certain tournaments from A337271.

%C 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.

%C It is a "primary ascent" if it's an ascent for which i and j belong to the same "initially connected component".

%C 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.

%C The rows of this triangle are the coefficients of the polynomials g[n] (or g(n)) defined in the Mma code.

%F See Mma code.

%e Triangle begins:

%e 1,

%e 0,1,

%e 0,1,2,1,

%e 0,1,7,13,11,5,1,

%e 0,1,14,64,144,192,167,98,38,9,1,

%e 0,1,23,187,796,2134,3968,5400,5541,4347,2611,1188,399,94,14,1,

%e ...

%e For example, there are 7 initially connected tournaments on 4 elements with 2 ascents; they're the tournaments whose ascents are

%e 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.

%e Notice that this sequence has no row 0.

%t (* first create the Gaussian binomial coefficients {n\choose k}_q *)

%t gb[n_,k_]:=gb[n,k]=Expand[q^k gb[n-1,k]+gb[n-1,k-1]]

%t gb[n_,0]:=1

%t gb[0,k_]:=0

%t (* now define the gf for a single component *)

%t 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}]]

%t (* now define the gf for a full tournament *)

%t h[n_]:=n!Coefficient[Series[Exp[Sum[g[k]z^k/k!,{k,n}]],{z,0,n}],z,n]

%t (* The elements of row n are the coefficients of g[n]. *)

%Y Cf. A337271.

%K nonn,tabf,more

%O 0,6

%A _N. J. A. Sloane_, Sep 01 2020, based on a communication from _Don Knuth_, Aug 25 2020