A277219 Triangle read by rows: T(n,k) is the number of independent sets of size k over all simple labeled graphs on n nodes, n>=0, 0<=k<=n.

1, 1, 1, 2, 4, 1, 8, 24, 12, 1, 64, 256, 192, 32, 1, 1024, 5120, 5120, 1280, 80, 1, 32768, 196608, 245760, 81920, 7680, 192, 1, 2097152, 14680064, 22020096, 9175040, 1146880, 43008, 448, 1, 268435456, 2147483648, 3758096384, 1879048192, 293601280, 14680064, 229376, 1024, 1

Offset

0,4

Comments

Equivalently, T(n,k) is the number of size k cliques over all simple labeled graphs on n vertices.

Links

Robert Israel, Table of n, a(n) for n = 0..3402 (rows 0 to 81, flattened)

Formula

T(n,k) = 2^binomial(n,2)*binomial(n,k)/2^binomial(k,2).

Example

Triangle begins:
1;
1,     1;
2,     4,      1;
8,     24,     12,     1;
64,    256,    192,    32,    1;
1024,  5120,   5120,   1280,  80,   1;
32768, 196608, 245760, 81920, 7680, 192, 1;
...

Maple

seq(seq(2^(n*(n-1)/2-k*(k-1)/2)*binomial(n, k), k=0..n), n=0..10); # Robert Israel, Oct 06 2016

Mathematica

Table[Table[2^Binomial[n, 2] Binomial[n, k]/2^Binomial[k, 2], {k, 0, n}], {n, 0, 7}] // Grid

Crossrefs

Cf. A079491 (row sums), A006125 (column k=0), A095340 (column k=1), A095351 (column k = 2).

Sequence in context: A354866 A233034 A204132 * A204135 A077387 A057551

Adjacent sequences: A277216 A277217 A277218 * A277220 A277221 A277222

Keyword

nonn,tabl

Author

Geoffrey Critzer, Oct 05 2016

Status

approved