Søren Fuglede Jørgensen - cp's OEIS frontend

User: Søren Fuglede Jørgensen

Søren Fuglede Jørgensen's wiki page.

Søren Fuglede Jørgensen has authored 3 sequences.

A382018 Number of orbits under the action of the permutation group S(n) on the nonsingular n X n matrices over GF(2).

Original entry on oeis.org

1, 1, 4, 33, 908, 85411, 28227922, 32597166327

Offset: 0

Søren Fuglede Jørgensen, Mar 12 2025

The action is defined by f.M(i,j)=M(f(i),f(j)).

Equivalently, the number of digraphs on n unlabeled nodes with loops allowed but no more than one arc with the same start and end node with adjacency matrices invertible over GF(2).

			For n = 2, representatives of the four different orbits are [[1, 0], [0, 1]], [[1, 1], [0, 1]], [[0, 1], [1, 1]], and [[0, 1], [1, 0]].

Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol, On Exact Sizes of Minimal CNOT Circuits, RC 2025, LNCS, vol 15716, pp. 71-88; arXiv:2503.01467 [quant-ph], 2025, Table 1.

Cf. A000595, A002884, A224879.

A381451 Triangle read by rows: T(n,k) is the clique covering number of the Johnson graph J(n, k), n >= 2, 0 < k < n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 9, 9, 5, 1, 1, 6, 12, 14, 12, 6, 1, 1, 7, 16, 25, 25, 16, 7, 1, 1, 8, 20, 40, 46, 40, 20, 8, 1, 1, 9, 25, 56

Offset: 2

Søren Fuglede Jørgensen, Feb 24 2025

T(2*k, k) = C(k) = A000108(k), the k-th Catalan number, for k = 1, 2, 4, 6, 8, 16; whether this holds for other values of k is an open question.

			Triangle begins:
   n\k  1  2  3  4  5  6  7  8  9 10
   2:   1
   3:   1  1
   4:   1  2  1
   5:   1  3  3  1
   6:   1  4  6  4  1
   7:   1  5  9  9  5  1
   8:   1  6 12 14 12  6  1
   9:   1  7 16 25 25 16  7  1
  10:   1  8 20 40 46 40 20  8  1
  11:   1  9 25 56  ?  ? 56 25  9  1
  ...

Søren Fuglede Jørgensen, On the clique covering numbers of Johnson graphs, Des. Codes Cryptogr. (2025); arXiv:2502.15019 [math.CO], 2025.
Eric Weisstein's World of Mathematics, Clique Covering Number.
Eric Weisstein's World of Mathematics, Johnson Graph.
Wikipedia, Johnson graph.

Cf. A002620 (column 3).

T(n, k) = T(n, n - k).
T(n, 1) = 1.
T(n, 2) = n - 2.
T(n, 3) = A002620(n-1), for n >= 6.
T(n, k) <= T(n - 1, k - 1) + T(n - 1, k).

A381854 Triangle read by rows: T(n, k) is the number of invertible n X n matrices over GF(2) that can be optimally row-reduced in k steps, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 1, 6, 24, 51, 60, 24, 2, 1, 12, 96, 542, 2058, 5316, 7530, 4058, 541, 6, 1, 20, 260, 2570, 19680, 117860, 540470, 1769710, 3571175, 3225310, 736540, 15740, 24, 1, 30, 570, 8415, 101610, 1026852, 8747890, 61978340, 355193925, 1561232840, 4753747050, 8111988473, 4866461728, 437272014, 949902, 120

Offset: 0

Søren Fuglede Jørgensen, Mar 08 2025

Using transvections as the generating set of the matrix group, this is the number of inequivalent minimal words in k generators; the number of elements at distance k from the identity in the corresponding Cayley graph.

Also the number of different elements that can be represented by minimal quantum circuits of k CNOT gates on n qubits.

			Triangle begins:
   n\k  0    1    2    3    4    5    6    7    8    9
   0:   1
   1:   1
   2:   1    2    2    1
   3:   1    6   24   51   60   24    2
   4:   1   12   96  542 2058 5316 7530 4058  541    6
   ...
For n = 2, k = 1, the two matrices are [[1, 1], [0, 1]] and [[1, 0], [1, 1]].
For n = 2, k = 2, the two matrices are [[1, 1], [1, 0]] and [[0, 1], [1, 1]].
For n = 2, k = 3, the only matrix is [[0, 1], [1, 0]].

Søren Fuglede Jørgensen, Table of n, a(n) for n = 0..83
Marc Bataille, Quantum Circuits of CNOT gates: Optimization and Entanglement, Quantum Information Processing, 21(7):269 (2022).
Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol, On Exact Sizes of Minimal CNOT Circuits, RC 2025, LNCS, vol 15716, pp. 71-88; arXiv:2503.01467 [quant-ph] (2025).
Ketan N. Patel, Igor L. Markov, and John P. Hayes, Optimal synthesis of linear reversible circuits, Quantum Info. Comput., 8(3) (2008), pp. 282-294.

Cf. A002378 (column 1), A172225 (column 2), A002884 (row sums).

T(n, 0) = 1.
T(n, 1) = n^2 - n.
T(n, 2) = (1/2)*(n^4 - 5*n^2 + 4*n).
T(n, 3) = (1/6)*(n^6 + 3*n^5 - 9*n^4 - 63*n^3 + 179*n^2 - 111*n).
Sum_{k>=0} T(n,k) = A002884(n).

cp's OEIS Frontend

User: Søren Fuglede Jørgensen

A382018 Number of orbits under the action of the permutation group S(n) on the nonsingular n X n matrices over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A381451 Triangle read by rows: T(n,k) is the clique covering number of the Johnson graph J(n, k), n >= 2, 0 < k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A381854 Triangle read by rows: T(n, k) is the number of invertible n X n matrices over GF(2) that can be optimally row-reduced in k steps, n >= 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula