A373398 Triangle read by rows: T(n, k) = number of k-element subobjects of an n-element set in the category of relations, n >= 0, 0 <= k <= n.

1, 1, 1, 1, 3, 1, 1, 7, 9, 1, 1, 15, 55, 25, 1, 1, 31, 285, 395, 65, 1, 1, 63, 1351, 5045, 2555, 161, 1, 1, 127, 6069, 56931, 78685, 15211, 385, 1, 1, 255, 26335, 592725, 2091171, 1101021, 85099, 897, 1, 1, 511, 111645, 5834515, 50334765, 67590387, 14169405, 454315, 2049, 1

Offset: 0

Author

Keith J. Bauer, Jun 03 2024

Keywords

• nonn
• easy
• tabl

Comments

A subobject of an object A is an object S equipped with a monomorphism S -> A, up to isomorphism in the category of objects equipped with such morphisms. Objects in the category of relations are sets, morphisms are relations, and composition is relation composition.

Objects and morphisms in Rel can be re-characterized as free complete join-semilattices (the power set of a set with join being union) and join-equivariant maps, respectively. Therefore, subobjects in Rel can be re-characterized as injective n X k matrices of truth values. Because every injective matrix of truth values can be shown to have pivots, subobjects can be counted via Schubert cells and this results in a family of generating functions describing the entire triangle. Short proof: if a monomorphism does not have a row consisting of all 0's except for one column in particular, then consider where it sends the column vector containing all 1's and the column vector containing all 1's but with the corresponding row flipped to 0. It cannot possibly send these vectors to two different vectors. (Here 0 and 1 represent false and true, respectively. Note that addition is logical "or" and multiplication is logical "and".)

Because Rel is self-dual, this sequence also counts quotient objects.

Entries not in the triangle's range are equal to 0 because there is no monomorphism from a k-element set to an n-element set when k > n.

All monomorphisms in Rel are regular, i.e., the equalizer of a pair of morphisms. In some categories, subobjects are taken to only be regular monomorphisms, or are at least distinguished; for example, a normal subgroup is (the domain of) a regular monomorphism in the category of groups. Because all monomorphisms in Rel are regular, there is no ambiguity in what a subobject in Rel is. See the link for a proof of this fact.

Examples

			There are 9 2-element subobjects of a 3-element set in Rel. As truth matrices:
  [1 0] [1 0] [0 0] [1 0] [0 1] [0 1] [1 1] [1 0] [1 0]
  [0 1] [0 0] [1 0] [0 1] [1 0] [0 1] [1 0] [1 1] [0 1]
  [0 0] [0 1] [0 1] [0 1] [0 1] [1 0] [0 1] [0 1] [1 1]
To convert to relations, note that each entry corresponds to whether
  [(1,1) (2,1)]
  [(1,2) (2,2)]
  [(1,3) (2,3)]
is in the relation.
Triangle starts:
  1,
  1,   1,
  1,   3,      1,
  1,   7,      9,       1,
  1,  15,     55,      25,        1,
  1,  31,    285,     395,       65,        1,
  1,  63,   1351,    5045,     2555,      161,        1,
  1, 127,   6069,   56931,    78685,    15211,      385,      1,
  1, 255,  26335,  592725,  2091171,  1101021,    85099,    897,    1,
  1, 511, 111645, 5834515, 50334765, 67590387, 14169405, 454315, 2049, 1,
  ...
		

Links

• Keith J. Bauer, Every monomorphism in Rel is regular.
• nLab, Rel

Crossrefs

T(n, 0) = A000012(n).

T(n, 1) = A000225(n).

T(n, 2) = A016269(n - 2).

T(n, 3) = A028130(n - 3).

T(n, n) = A000012(n).

T(n, n - 1) = A002064(n - 1).

Analogous sequence in the category Set: A007318.

Programs

Mathematica

T[n_,k_]:=SeriesCoefficient[(1 / (1 - 2^k* x)) * Product[1 / (1 - (2^k - 2^i) * x),{i,0,k-1}],{x,0,n}]; Table[T[n-k,k],{n,0,9},{k,0,n}]//Flatten (* Stefano Spezia, Jun 04 2024 *)

Sage

dim = 10
def getGF(n):
    R. = PowerSeriesRing(ZZ, 'x', dim)
    f = 1 / (1 - 2^n * x)
    for k in range(n):
        f = f / (1 - (2^n - 2^k) * x)
    return f
for n in range(dim):
    print([getGF(k).list()[n - k] for k in range(n + 1)])

Formula

G.f.: Sum_{n>=0} T(n + k, k) * x^n = (1 / (1 - 2^k * x)) * Product_{i=0..k-1} (1 / (1 - (2^k - 2^i) * x)).