A046858 Irregular triangle read by rows: T(n,k) = number of directed graphs-with-loops with n nodes and k arcs (n >= 0, 0 <= k <= n^2).

1, 1, 1, 1, 2, 4, 2, 1, 1, 2, 8, 17, 24, 24, 17, 8, 2, 1, 1, 2, 9, 32, 95, 203, 373, 515, 584, 515, 373, 203, 95, 32, 9, 2, 1, 1, 2, 9, 36, 157, 549, 1692, 4374, 9626, 17874, 28373, 38486, 44805, 44805, 38486, 28373, 17874, 9626, 4374, 1692, 549, 157, 36, 9, 2, 1, 1

Offset

0,5

Comments

Equivalently, T(n,k) = number of relations on n-set with strength k (n >= 0, 0<=k<=n^2).

References

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

Links

Table of n, a(n) for n=0..61.

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

Example

Triangle begins:
[1],
[1, 1],
[1, 2, 4, 2, 1],
[1, 2, 8, 17, 24, 24, 17, 8, 2, 1],
[1, 2, 9, 32, 95, 203, 373, 515, 584, 515, 373, 203, 95, 32, 9, 2, 1] (the last batch giving the numbers of directed graphs with loops on 4 nodes and from 0 to 16 arcs).

Mathematica

Needs["Combinatorica`"]; Join[{{1}, {1, 1}}, CoefficientList[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n], Ordered], Permutations[Range[n^2-n+1, n^2]], 2], s]/.Table[s[i]->1+x^i, {i, 1, n^2-n}], {n, 2, 7}], x]]//Grid (* Geoffrey Critzer, Sep 29 2012 *)

Crossrefs

Cf. A000595.

Sequence in context: A344637 A201558 A052285 * A225812 A132823 A059317

Adjacent sequences: A046855 A046856 A046857 * A046859 A046860 A046861

Keyword

nonn,tabf,nice

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Feb 07 2000

Edited by N. J. A. Sloane Apr 16 2008 at the suggestion of Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 24 2008

Status

approved