A231428 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 62nd year, we have over 390,000 sequences, and we’ve reached 12,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A231428

Sorted and encoded binary matrices representing equivalence relations.

0, 1, 2, 4, 7, 8, 12, 16, 18, 25, 32, 33, 42, 52, 63, 64, 68, 80, 96, 116, 128, 130, 136, 160, 170, 193, 225, 256, 257, 264, 272, 281, 322, 338, 388, 396, 455, 512, 513, 514, 516, 519, 584, 588, 656, 658, 729, 800, 801, 874, 948, 1023, 1024

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

The N X N binary matrix of an equivalence relation is perfectly defined by its upper-right triangle. We encode such a matrix with the (N*(N-1))/2 bit number obtained by joining together each line of the upper-right triangle. The numbers are converted to base 10.

This is an infinite sequence and can be used for arbitrarily large values of N. To enumerate the finite list of n X n matrices for a given n, truncate this sequence to the first A000110(n) elements.

LINKS

Philippe Beaudoin, Table of n, a(n) for n = 1..10000

Philippe Beaudoin, Python program to generate the sequence

Tilman Piesk, Illustrated list of the first 52 equivalence relations

Tilman Piesk, Non-singleton blocks of the partitions of {1...8} in the same order.

Tilman Piesk, Permutations and partitions in the OEIS (Wikiversity)

EXAMPLE

The 4 X 4 equivalence matrices are represented by the first A000110(4) = 15 elements, that is: 0, 1, 2, 4, 7, 8, 12, 16, 18, 25, 32, 33, 42, 52, 63.

The 4 X 4 matrix corresponding to 25 = 0b011001 is:

1 0 1 1

0 1 0 0

1 0 1 1