Anthony Labarre - cp's OEIS frontend

User: Anthony Labarre

Anthony Labarre has authored 7 sequences.

A216256 Minimum length of a longest unimodal subsequence of a permutation of n elements.

1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15

Offset: 1

Anthony Labarre, Mar 15 2013

a(n) is the value such that for any permutation P of n elements, P always contains a unimodal subsequence of length a(n), i.e., a sequence that is increasing, or decreasing, or increasing then decreasing.

n appears floor((2n+1)/3) = A004396(n) times. - Peter Kagey, Feb 27 2021

			a(3) = 3 because all permutations of 3 elements are unimodal.
a(4) = 3 because there are permutations of 4 elements (e.g., 1423) that are not unimodal, but using the previous value we can always fix that by deleting one element.

Peter Kagey, Table of n, a(n) for n = 1..10000
F. R. K. Chung, On unimodal subsequences, Journal of Combinatorial Theory, Series A, 279 (1980), pp. 267-279.

Cf. A004396.

unsigned int a(unsigned int n) { return ceil( sqrt((double) 3*n - 0.75) - 0.5); }

[Ceiling(Sqrt(3*n - 3/4) - 1/2) : n in [1..100]]; // Wesley Ivan Hurt, Oct 16 2015

A216256:=n->ceil(sqrt(3*n - 3/4) - 1/2): seq(A216256(n), n=1..100); # Wesley Ivan Hurt, Oct 16 2015

Table[Ceiling[Sqrt[3 n - 3/4] - 1/2], {n, 100}] (* Wesley Ivan Hurt, Oct 16 2015 *)

a(n) = ceil(sqrt(3*n-3/4) - 1/2); \\ Michel Marcus, Apr 22 2014

a(n) = ceiling(sqrt(3*n - 3/4) - 1/2).

A178217 Number of unsigned permutations in S_{3n-1} whose breakpoint graph contains only cycles of length 3.

Original entry on oeis.org

1, 12, 464, 38720, 5678400, 1294720000, 423809075200, 188422340198400, 109244157102080000, 80068011114291200000, 72384558633074688000000, 79125533869852634644480000, 102879028406438808699535360000, 156917389218035568246207283200000, 277479100225377558605912342528000000

Offset: 1

Anthony Labarre, Dec 25 2010

nonn

The number of permutations in S_{n} whose breakpoint graph contains only cycles of length 3 is nonzero only for n=3*k-1 (see references for definitions).

			See references for examples (nongraphical explanations do not help much).

J.-P. Doignon and A. Labarre, On Hultman Numbers, J. Integer Seq., 10 (2007), 13 pages.
A. Labarre, Combinatorial aspects of genome rearrangements and haplotype networks (2008), Ph. D. thesis.

a(p) := ((3*p)!/(p!*12^p))*sum(binomial(p,i)*(3^i)/(2*i+1),i,0,p);

a(n) = (3*n)!/(n!*12^n) * sum(i = 0, n, binomial(n, i)*3^i/(2*i+1)); \\ Michel Marcus, Sep 05 2013

a(n) = (3*n)!/(n!*12^n)*Sum_{i=0..n} binomial(n,i)*3^i/(2*i+1). (See references for a proof.)

More terms from Michel Marcus, Oct 14 2024

A164645 Triangle read by rows: a(n,k) is the number of permutations of n elements with prefix transposition distance equal to k.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 6, 14, 3, 1, 10, 50, 55, 4, 1, 15, 130, 375, 194, 5, 1, 21, 280, 1575, 2598, 562, 3, 1, 28, 532, 4970, 18096, 15532, 1161, 0, 1, 36, 924, 12978, 85128, 188386, 74183, 1244, 0, 1, 45, 1500, 29610, 308988, 1364710, 1679189, 244430, 327

Offset: 1

Anthony Labarre, Aug 19 2009

A prefix transposition refers to the displacement of the first f elements of the permutation. The prefix transposition distance is the minimum number of such moves required to transform a given permutation into the identity permutation.

			a(4,2)=3 because the only 3 permutations that require 2 prefix transpositions to be sorted are (1 4 3 2), (2 1 4 3) and (4 3 2 1)

Zanoni Dias and Joao Meidanis, Sorting by Prefix Transpositions, Proceedings of the Ninth International Symposium on String Processing and Information Retrieval (SPIRE), 2002, 65-76, vol. 2476 of Lecture Notes in Computer Science, Springer-Verlag
G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 37.

G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009.

A164366 Triangle read by rows: T(n,k) is the number of permutations of n elements with transposition distance equal to k, n >= 1 and 0 <= k <= A065603(n).

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 10, 12, 1, 1, 20, 68, 31, 1, 35, 259, 380, 45, 1, 56, 770, 2700, 1513, 1, 84, 1932, 13467, 22000, 2836, 1, 120, 4284, 52512, 191636, 114327, 1, 165, 8646, 170907, 1183457, 2010571, 255053, 1, 220, 16203, 484440, 5706464, 21171518, 12537954, 1, 286, 28600, 1231230, 22822293, 157499810, 265819779, 31599601, 1, 364, 48048, 2864719, 78829491, 910047453, 3341572727, 1893657570, 427, 1, 455, 77441, 6196333, 241943403, 4334283646, 29432517384, 47916472532, 5246800005

Offset: 1

Anthony Labarre, Aug 14 2009

Here, a transposition refers to the exchange of two adjacent blocks, and NOT to an exchange of two nonnecessarily adjacent elements. The transposition distance is the minimum number of such moves required to transform a given permutation into the identity permutation.

			The triangle of T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows:
  1,
  1,   1,
  1,   4,    1,
  1,  10,   12,      1,
  1,  20,   68,     31,
  1,  35,  259,    380,      45,
  1,  56,  770,   2700,    1513,
  1,  84, 1932,  13467,   22000,    2836,
  1, 120, 4284,  52512,  191636,  114327,
  1, 165, 8646, 170907, 1183457, 2010571, 255053,
  ...
The number of permutations of 4 elements with transposition distance 3 is 1, since only (4 3 2 1) cannot be sorted using fewer transpositions (upper bound can be easily found by hand; for the lower bound, see the paper by Bafna and Pevzner).

G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 26.

V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
J. Gonçalves, L. R. Bueno, R. A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.

Cf. A219243 (main "diagonal"). See also A065603.

Edited by Max Alekseyev, Nov 07 2011

More terms from Gonçalves et al. added by Max Alekseyev, Nov 16 2012

A164652 Triangle read by rows: Hultman numbers: a(n,k) is the number of permutations of n elements whose cycle graph (as defined by Bafna and Pevzner) contains k cycles for n >= 0 and 1 <= k <= n+1.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 5, 0, 1, 8, 0, 15, 0, 1, 0, 84, 0, 35, 0, 1, 180, 0, 469, 0, 70, 0, 1, 0, 3044, 0, 1869, 0, 126, 0, 1, 8064, 0, 26060, 0, 5985, 0, 210, 0, 1, 0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1, 604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1, 0, 19056960, 0, 18128396, 0, 2641925, 0, 88803, 0, 715, 0, 1

Offset: 0

Anthony Labarre, Aug 19 2009

a(n,k) is also the number of ways to express a given (n+1)-cycle as the product of an (n+1)-cycle and a permutation with k cycles (see Doignon and Labarre). a(n,n+1-2k) is the number of permutations of n elements whose block-interchange distance is k (see Christie, Doignon and Labarre).
Named after the Swedish mathematician Axel Hultman. - Amiram Eldar, Jun 11 2021
a(2*n,1) is the number of spanning trees in certain graphs with 2*n+1 vertices and n*(n+1) edges (see Ishikawa, Miezaki, and Tanaka). - Tsuyoshi Miezaki, Feb 08 2023

			Triangle begins:
  n=0:  1;
  n=1:  0, 1;
  n=2:  1, 0, 1;
  n=3:  0, 5, 0, 1;
  n=4:  8, 0, 15, 0, 1;
  n=5:  0, 84, 0, 35, 0, 1;
  n=6:  180, 0, 469, 0, 70, 0, 1;
  n=7:  0, 3044, 0, 1869, 0, 126, 0, 1;
  n=8:  8064, 0, 26060, 0, 5985, 0, 210, 0, 1;
  n=9:  0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1;
  n=10: 604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1;
  ...
From _Jon E. Schoenfield_, May 20 2023: (Start)
As a right-aligned triangle:
                                                      1; n=0
                                                   0, 1; n=1
                                                1, 0, 1; n=2
                                           0,   5, 0, 1; n=3
                                        8, 0,  15, 0, 1; n=4
                                 0,    84, 0,  35, 0, 1; n=5
                            180, 0,   469, 0,  70, 0, 1; n=6
                      0,   3044, 0,  1869, 0, 126, 0, 1; n=7
                8064, 0,  26060, 0,  5985, 0, 210, 0, 1; n=8
          0,  193248, 0, 152900, 0, 16401, 0, 330, 0, 1; n=9
  604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1; n=10
  ...
(End)

Axel Hultman, Toric permutations, Master's thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999.

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
Nikita Alexeev, Anna Pologova, and Max A. Alekseyev, Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs, Journal of Computational Biology, Vol. 24, No. 2 (2017), pp. 93-105; arXiv preprint, arXiv:1503.05285 [q-bio.GN], 2015-2017.
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv preprint arXiv:1111.3061 [math.PR], 2011.
Nikita Alexeev and Peter Zograf, Random matrix approach to the distribution of genomic distance, Journal of Computational Biology, Vol. 21, No. 8 (2014), pp. 622-631.
Miklos Bona and Ryan Flynn, The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley, arXiv:0811.0740 [math.CO], 2008.
Miklos Bona and Ryan Flynn, The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley, Inf. Process. Lett., Vol. 109 (2009), pp. 927-931.
David A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett., Vol. 60, No. 4 (1996), pp. 165-169.
Robert Cori and Gábor Hetyei, On reduced unicellular hypermonopoles, arXiv:2403.19569 [math.CO], 2024. See at p. 4.
Jean-Paul Doignon and Anthony Labarre, On Hultman Numbers, J. Integer Seq., Vol. 10 (2007), Article 07.6.2, 13 pages.
Simona Grusea and Anthony Labarre, The distribution of cycles in breakpoint graphs of signed permutations, arXiv:1104.3353 [cs.DM], 2011-2012.
Reina Ishikawa, Tsuyoshi Miezaki, and Yuuho Tanaka, A new interpretation of Hultman numbers.

Cf. A000142 (row sums), A000217, A060593, A128174, A130534, A132393, A185259, A189507, A260695.

Cf. A185263 (rows reversed without 0's).

a164652 n k = a164652_tabl !! n !! k
a164652_row n = a164652_tabl !! n
a164652_tabl = [0] : tail (zipWith (zipWith (*)) a128174_tabl $
   zipWith (map . flip div) (tail a000217_list) (map init $ tail a130534_tabl))
-- Reinhard Zumkeller, Aug 01 2014

A164652:= (n, k)-> `if`(n-k mod 2 = 1, -Stirling1(n+2, k)/binomial(n+2, 2), 0):
for n from 0 to 7 do seq(A164652(n,k),k=1..n+1) od; # Peter Luschny, Mar 22 2015

T[n_, k_] := If[OddQ[n-k], Abs[StirlingS1[n+2, k]]/Binomial[n+2, 2], 0];
Table[T[n, k], {n, 0, 11}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Aug 10 2018 *)

T(n,k)= my(s=(n-k)%2); (-1)^s*s*stirling(n+2,k,1)/binomial(n+2,2);
concat(vector(12, n, vector(n, k, T(n-1,k)))) \\ Gheorghe Coserea, Jan 23 2018

def A164652(n, k):
    return stirling_number1(n+2,k)/binomial(n+2,2) if is_odd(n-k) else 0
for n in (0..7): print([A164652(n,k) for k in (1..n+1)]) # Peter Luschny, Mar 22 2015

T(n,k) = S1(n+2,k)/C(n+2,2) if n-k is odd, and 0 otherwise. Here S1(n,k) are the unsigned Stirling numbers of the first kind A132393 and C(n,k) is the binomial coefficient (see Bona and Flynn).
For n > 0: T(n,k) = A128174(n+1,k) * A130534(n+1,k-1) / A000217(n+1). - Reinhard Zumkeller, Aug 01 2014
n-th row polynomial R(n,x) = (x/2)*( P(n+1,x) + (-1)^n * P(n+1,-x) ) / binomial(n+2,2), where P(k,x) = (x + 1)*(x + 2)*...*(x + k). - Peter Bala, May 14 2023

T(0,1) set to 1 by Peter Luschny, Mar 24 2015

Edited to match values of k to the range 1 to n+1. - Max Alekseyev, Nov 20 2020

A132803 Number of simple permutations in S_n, i.e., those whose "cycle graph" (or "breakpoint graph") only contains alternating cycles of length at most 3.

Original entry on oeis.org

1, 2, 6, 16, 48, 204, 876, 3636, 18756, 105480, 561672

Offset: 1

Anthony Labarre, Nov 21 2007

J.-P. Doignon and A. Labarre, On Hultman Numbers, J. Integer Seq., 10 (2007), 13 pages.

A115755 Number of permutations of n elements whose unsigned reversal distance is k.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 6, 15, 2, 1, 10, 51, 56, 2, 1, 15, 127, 390, 185, 2, 1, 21, 263, 1562, 2543, 648, 2, 1, 28, 483, 4635, 16445, 16615, 2111, 2, 1, 36, 820, 11407, 69863, 169034, 105365, 6352, 2

Offset: 1

Anthony Labarre, Mar 29 2006, Jun 03 2006

Probably an erroneous version of A300003. Some inner terms of the triangle differ slightly. Sean A. Irvine reread the paper and checked manually that a(13) should be 52. The last row 1, 36, 820 ... 6352, 2 was added later and is ok. - Georg Fischer, Feb 24 2020

			a(3,1) = 3 because the only three permutations of S_3 that require exactly one reversal to be sorted are (1 3 2), (2 1 3) and (3 2 1).

J. D. Kececioglu, and D. Sankoff, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Algorithmica (1995) 13:180.

Cf. A300003.

cp's OEIS Frontend

User: Anthony Labarre

A216256 Minimum length of a longest unimodal subsequence of a permutation of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Magma

Maple

Mathematica

PARI

Formula

A178217 Number of unsigned permutations in S_{3n-1} whose breakpoint graph contains only cycles of length 3.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maxima

PARI

Formula

Extensions

A164645 Triangle read by rows: a(n,k) is the number of permutations of n elements with prefix transposition distance equal to k.

Views

Author

Keywords

Comments

Examples

References

Links

A164366 Triangle read by rows: T(n,k) is the number of permutations of n elements with transposition distance equal to k, n >= 1 and 0 <= k <= A065603(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A164652 Triangle read by rows: Hultman numbers: a(n,k) is the number of permutations of n elements whose cycle graph (as defined by Bafna and Pevzner) contains k cycles for n >= 0 and 1 <= k <= n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A132803 Number of simple permutations in S_n, i.e., those whose "cycle graph" (or "breakpoint graph") only contains alternating cycles of length at most 3.

Views

Author

Keywords

Links

A115755 Number of permutations of n elements whose unsigned reversal distance is k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs