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

Author

Don Knuth, Jan 16 2022

Keywords

• nonn
• tabl

Comments

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

For references and links see A350608.

Examples

			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;
  ...
		

Links

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

Crossrefs

Column k=1 gives A350608.

Main diagonal gives A006125(n-1).

Cf. A350610.