A235647 a(n) is the number of cycles of the permutation relating the lexicographic order to the colexicographic order, for the set of pairs (i,j), 1 <= i <= j <= n.

1, 3, 5, 5, 6, 8, 6, 10, 11, 13, 7, 11, 12, 10, 14, 12, 11, 13, 11, 13, 12, 10, 18, 14, 17, 13, 15, 13, 18, 22, 16, 14, 17, 13, 19, 15, 18, 24, 20, 18, 21, 17, 21, 21, 18, 20, 18, 28, 21, 25, 21, 21, 24, 30, 26, 24, 23, 25, 25, 23, 22, 22, 32, 28, 27, 29, 21, 35, 30, 30, 26, 34, 29, 23, 35

Offset

1,2

Comments

An equivalent way to define the permutation is to number the upper triangular part of an n X n matrix by columns and then read it by rows. For n = 4, for example, the matrix is

[1 2 4 7]

[ 3 5 8]

[ 6 9]

[ 10];

reading it by rows gives the permutation (1,2,4,7,3,5,8,6,9,10) (in one-line notation), which has a(4) = 5 cycles (see example). - Pontus von Brömssen, Jun 18 2023

References

Karl Javorszky, Transfer of Genetic Information: An Innovative Model, Proceedings 2017, 1, 222; doi:10.3390/IS4SI-2017-04030 www.mdpi.com/journal/proceedings

Links

Karl Javorszky, Table of n, a(n) for n = 1..1000

Theodore Chronis, Defs and demo

Karl Javorszky, Description of A235647, February 2014

Karl Javorszky, Examples for acts of replacements

Karl Javorszky, Picturing Order, Contemporary Computational Science (2018), 3rd Conf. on Inf. Tech. Systems Res. and Comp. Phys. (ITSRCP18), 83-91.

Karl Javorszky, Counting in Cycles, Preprints (2022), 2022090373.

Example

Example for n = 4:
lr and clr in the table below are the lexicographic and colexicographic rankings of the pair. (That is, lr is derived by ordering the pairs by their 1st element then 2nd element. clr is similarly derived by ordering the pairs by their 2nd element then 1st element.) We then consider the permutation of 1..T_4, where T_4 is the 4th triangular number, derived by mapping lr to clr.
   lr   pair  clr
    1  (1,1)   1  fixed point
    2  (1,2)   2  fixed point
    3  (1,3)   4 -> 7 -> 8 -> 6 -> 5 -> 3
    4  (1,4)   7  (in same cycle as 3)
    5  (2,2)   3  (in same cycle as 3)
    6  (2,3)   5  (in same cycle as 3)
    7  (2,4)   8  (in same cycle as 3)
    8  (3,3)   6  (in same cycle as 3)
    9  (3,4)   9  fixed point
   10  (4,4)  10  fixed point
The permutation has 5 cycles, so a(4) = 5.
See also "Examples for acts of replacements" in the links.

Mathematica

A235647[n_]:=
Length@Flatten[PermutationCycles[
    Flatten[Table[(b-1)b/2+a, {a, 1, n}, {b, a, n}], 1]
    , List], 1]

Prog

(Python)
from sympy.combinatorics import Permutation
def A235647(n):
    pairs_lex = [(i, j) for i in range(n) for j in range(i, n)]
    pairs_colex = sorted(pairs_lex, key=lambda x:list(reversed(x)))
    rank = {p:i for i, p in enumerate(pairs_lex)}
    return Permutation([rank[p] for p in pairs_colex]).cycles # Pontus von Brömssen, Jun 18 2023

Crossrefs

Cf. A000217, A242615.

Sequence in context: A195939 A331859 A317587 * A010616 A296485 A055594

Adjacent sequences: A235644 A235645 A235646 * A235648 A235649 A235650

Keyword

nonn

Author

Karl Javorszky, Feb 22 2014

Extensions

New name from Pontus von Brömssen, Jun 18 2023

Revised by Peter Munn, Jun 19 2023

Status

approved