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,5

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.

Links

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

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

nLab, Rel

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

Example

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

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 *)

Prog

(Sage)
dim = 10
def getGF(n):
    R.<x> = 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)])

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.

Sequence in context: A259471 A220555 A369559 * A075440 A137470 A112492

Adjacent sequences: A373395 A373396 A373397 * A373399 A373400 A373401

Keyword

nonn,easy,tabl

Author

Keith J. Bauer, Jun 03 2024

Status

approved