|
%I #69 Jun 21 2023 18:24:06
%S 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,
%T 13,15,13,18,22,16,14,17,13,19,15,18,24,20,18,21,17,21,21,18,20,18,28,
%U 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
%N 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.
%C 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
%C [1 2 4 7]
%C [ 3 5 8]
%C [ 6 9]
%C [ 10];
%C 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
%D Karl Javorszky, Transfer of Genetic Information: An Innovative Model, Proceedings 2017, 1, 222; doi:10.3390/IS4SI-2017-04030 www.mdpi.com/journal/proceedings
%H Karl Javorszky, <a href="/A235647/b235647.txt">Table of n, a(n) for n = 1..1000</a>
%H Theodore Chronis, <a href="/A235647/a235647.cdf.txt">Defs and demo</a>
%H Karl Javorszky, <a href="/A235647/a235647_1.txt">Description of A235647</a>, February 2014
%H Karl Javorszky, <a href="/A235647/a235647_4.pdf">Examples for acts of replacements</a>
%H Karl Javorszky, <a href="https://www.researchgate.net/profile/Yashbir_Singh3/publication/326009482_6th_International_Symposium_CompIMAGE'18_-_Computational_Modeling_of_Objects_Presented_in_Images_Fundamentals_Methods_and_Applications/links/5b3342e6aca2720785e996b0/6th-International-Symposium-CompIMAGE18-Computational-Modeling-of-Objects-Presented-in-Images-Fundamentals-Methods-and-Applications.pdf#page=93">Picturing Order</a>, Contemporary Computational Science (2018), 3rd Conf. on Inf. Tech. Systems Res. and Comp. Phys. (ITSRCP18), 83-91.
%H Karl Javorszky, <a href="https://doi.org/10.20944/preprints202209.0373.v1">Counting in Cycles</a>, Preprints (2022), 2022090373.
%e Example for n = 4:
%e 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.
%e lr pair clr
%e 1 (1,1) 1 fixed point
%e 2 (1,2) 2 fixed point
%e 3 (1,3) 4 -> 7 -> 8 -> 6 -> 5 -> 3
%e 4 (1,4) 7 (in same cycle as 3)
%e 5 (2,2) 3 (in same cycle as 3)
%e 6 (2,3) 5 (in same cycle as 3)
%e 7 (2,4) 8 (in same cycle as 3)
%e 8 (3,3) 6 (in same cycle as 3)
%e 9 (3,4) 9 fixed point
%e 10 (4,4) 10 fixed point
%e The permutation has 5 cycles, so a(4) = 5.
%e See also "Examples for acts of replacements" in the links.
%t A235647[n_]:=
%t Length@Flatten[PermutationCycles[
%t Flatten[Table[(b-1)b/2+a,{a,1,n},{b,a,n}],1]
%t ,List],1]
%o (Python)
%o from sympy.combinatorics import Permutation
%o def A235647(n):
%o pairs_lex = [(i,j) for i in range(n) for j in range(i,n)]
%o pairs_colex = sorted(pairs_lex,key=lambda x:list(reversed(x)))
%o rank = {p:i for i,p in enumerate(pairs_lex)}
%o return Permutation([rank[p] for p in pairs_colex]).cycles # _Pontus von Brömssen_, Jun 18 2023
%Y Cf. A000217, A242615.
%K nonn
%O 1,2
%A _Karl Javorszky_, Feb 22 2014
%E New name from _Pontus von Brömssen_, Jun 18 2023
%E Revised by _Peter Munn_, Jun 19 2023
|
