|
|
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.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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, Picturing Order, Contemporary Computational Science (2018), 3rd Conf. on Inf. Tech. Systems Res. and Comp. Phys. (ITSRCP18), 83-91.
|
|
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
|
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
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)}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|