A350609 Triangle read by rows: T(n,k) (n >= 1, 1 <= k <= n) = number of subdigraphs of the transitive tournament on n nodes that have k weak components.

1, 1, 1, 4, 2, 2, 31, 15, 10, 8, 474, 228, 162, 96, 64, 14357, 7057, 5242, 3296, 1792, 1024, 865024, 438662, 342394, 222720, 130048, 65536, 32768, 103931595, 54542867, 44669602, 30110848, 18337792, 10027008, 4718592, 2097152, 24935913222, 13548525896, 11608243634, 8093078016, 5130403840, 2945449984, 1518338048, 671088640, 268435456

Offset

1,4

Comments

The sum of row n is 2^(n*(n-1)/2) = A006125(n).

For references and links see A350608.

Links

Don Knuth, Rows n = 1..16, flattened

Example

For example, the entries for n=3 are {4,2,2}, because the empty subgraph and the subgraphs with a single arc have 1 weak component {123}; 1->2,1->3 and 1->3,2->3 have 2 weak components (namely {1,23} and {12,3}); finally 1->2,2->3 and 1->2,1->3,2->3 have 3 weak components (namely {1,2,3}).
Triangle T(n,k) begins:
       1;
       1,      1;
       4,      2,      2;
      31,     15,     10,      8;
     474,    228,    162,     96,     64;
   14357,   7057,   5242,   3296,   1792,  1024;
  865024, 438662, 342394, 222720, 130048, 65536, 32768;
  ...

Crossrefs

Column k=1 gives A350608.

Main diagonal gives A006125(n-1).

Cf. A350610.

Sequence in context: A199221 A096870 A350149 * A261253 A328334 A359060

Adjacent sequences: A350606 A350607 A350608 * A350610 A350611 A350612

Keyword

nonn,tabl

Author

Don Knuth, Jan 16 2022

Status

approved