Daniel Krenn - cp's OEIS frontend

A334275 Number of unlabeled connected graphs with n vertices such that every vertex has exactly 2 vertices at distance 2.

1, 0, 0, 0, 0, 1, 11, 9, 7, 5, 6, 7, 10, 11, 14, 18, 22, 26, 34, 40, 50, 61, 74, 89, 111, 131, 159, 192, 231, 274, 332, 392, 469, 557, 661, 780, 928, 1088, 1285, 1511, 1776, 2076, 2439, 2843, 3324, 3873, 4511, 5238, 6096, 7057, 8183, 9466

Offset: 0

Daniel Krenn, Apr 21 2020

nonn

Gaar and Krenn call these graphs 2-metamour-regular.

			For n = 8 vertices, there exist the connected 2-metamour-regular graphs
   - c(C_8), c(C_5) join c(C_3), c(C_4) join c(C_4),
   - C_8 and
   - 3 exceptional graphs,
where C_i is the cycle graph on i vertices, and c(G) is the complement graph of G.
Therefore the unlabeled total is a(8) = 7.

E. Gaar and D. Krenn, Metamour-regular Polyamorous Relationships and Graphs, arXiv:2005.14121 [math.CO], 2020.

Cf. A008483.

a(n)=if(n<9,[1, 0, 0, 0, 0, 1, 11, 9, 7, 5][n+1], numbpart(n)-numbpart(n-1)-numbpart(n-2)+numbpart(n-3)+1) \\ Charles R Greathouse IV, Apr 22 2020

[(len(Partitions(n, min_part=3)) if n >= 6 else 0)
           + (1 if n >= 5 else 0)
           + {0: 1, 6: 8, 7: 6, 8: 3}.get(n, 0)
           for n in srange(52)]

a(n) = p_3(n) + 1 for n >= 9 with p_3(n) being the number of integer partitions of n with parts at least 3 (A008483).

A289263 Number of maximal roller coasters in all n! permutations of n elements.

Original entry on oeis.org

2, 26, 242, 2194, 21304, 226388, 2643008

Offset: 3

Daniel Krenn, Jul 01 2017

A roller coaster is a pattern in a permutation (not necessarily consecutive) consisting of alternating up and down steps, with always at least two in one direction.
A maximal roller coaster is one that cannot be extended further.
Note that the singleton pattern (only one element) is not considered a roller coaster.
Examples:
- 123 and 321 are the only two (maximal) roller coasters in all permutations with 3 elements; see also the examples section. These patterns are the smallest two roller coasters that exist.
- The permutation 1536742 contains the maximal roller coasters 136742, 156742 and 532, no further maximal roller coaster.
- The permutation 163978524 contains among others the maximal roller coasters 124 and 137854. In total, this permutation has 14 maximal roller coasters.
- The permutation 1254367 is already a roller coaster, so the only maximal roller coaster is the permutation itself.

			For n = 3 the a(3) = 2 maximal roller coasters are 123 (of the permutation 123) and 321 (of the permutation 321); the permutations 132, 213, 231 and 312 do not contain any roller coaster pattern.

Daniel Krenn, sequences-roller-coasters, program in SageMath, on GitHub.

rc[p_] := Block[{L = {}, s}, s = Select[Reverse@ Subsets[p, {2, Length@p}], Min[Length /@ Split[ Sign@ Differences@#]] >= 2 &]; Do[ If[ AllTrue[L, ! SubsetQ[#, e] &], AppendTo[L, e]], {e, s}]; Length@ L]; a[n_] := ParallelSum[rc@ p, {p, Permutations@ Range@ n}]; a /@ Range[3, 8] (* Giovanni Resta, Jul 05 2017 *)

a(9) from Giovanni Resta, Jul 05 2017

A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

Original entry on oeis.org

0, 0, 2, 16, 116, 888, 7416, 67968, 682272, 7467840, 88678080, 1136712960, 15655438080, 230672171520, 3621985113600, 60392753971200, 1065907048550400, 19855856150323200, 389354639411404800, 8017578241634304000, 172991656889856000000, 3903132531903897600000

Offset: 0

Daniel Krenn, Jun 20 2017

nonn

From Petros Hadjicostas, May 04 2020: (Start)
Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. (To get the number of key comparisons to sort all n! permutations of n elements by quicksort, multiply this number by n!.)
For this sequence, we have C = 4. The corresponding number of key comparisons to sort all n! permutations of n elements by quicksort when C = 3 is A063090(n). Thus, a(n) = A063090(n) - n!*n.
For more details, see my comments and references for sequences A093418, A096620, and A115107. (End)

Daniel Krenn, Table of n, a(n) for n = 0..100
Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Lucky Cars and the Quicksort Algorithm, arXiv:2306.13065 [math.CO], 2023.
Index entries for sequences related to sorting

Cf. A063090, A093418, A096620, A115107, A117627, A117628, A159324, A288965.

a:= proc(n) option remember; `if`(n<3, n*(n-1),
      ((2*n^2-3*n-1)*a(n-1)-(n-1)^2*n*a(n-2))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 21 2017

a[n_] := n! (2(n+1)HarmonicNumber[n] - 4n);
a /@ Range[0, 25] (* Jean-François Alcover, Oct 29 2020 *)

[n.factorial() * (2*(n+1)*sum(1/k for k in srange(1, n+1)) - 4*n) for n in srange(21)]

# alternative using the recurrence relation
@cached_function
def c(n):
    if n <= 1:
        return 0
    return (n - 1) + 2/n*sum(c(i) for i in srange(n))
[n.factorial() * c(n) for n in srange(21)]

a(n) = n!*(2*(n+1)*H(n) - 4*n).
c(n) = a(n) / n! satisfies c(n) = (n-1) + 2/n * Sum_{i < n} c(i).
a(n) = 2*A002538(n-1), n >= 2. - Omar E. Pol, Jun 20 2017
E.g.f.: -2*log(1-x)/(1-x)^2 - 2*x/(1-x)^2. - Daniel Krenn, Jun 20 2017
a(n) = ((2*n^2-3*n-1)*a(n-1) -(n-1)^2*n*a(n-2))/(n-2) for n >= 3, a(n) = n*(n-1) for n < 3. - Alois P. Heinz, Jun 21 2017
From Petros Hadjicostas, May 03 2020: (Start)
a(n) = A063090(n) - n!*n for n >= 1.
a(n) = n!*A115107(n)/A096620(n) = n!*(-n + A093418(n)/A096620(n)). (End)

A288971 Number of key comparisons to sort all n! permutations of n elements by the optimal quadral-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7008, 63648, 635040, 6915168, 81757440, 1044161280, 14334076800, 210595524480

Offset: 0

Daniel Krenn, Jun 20 2017

The 4 pivot elements are chosen from fixed indices (e.g. the last 4 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A288964, A288965, A288970.

a(9)-a(13) from Melanie Siebenhofer, Feb 05 2018

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264

Offset: 0

Daniel Krenn, Jun 20 2017

The 3 pivot elements are chosen from fixed indices (e.g., the last 3 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.

a(9)-a(11) from Melanie Siebenhofer, Jan 29 2018

a(12)-a(13) from Melanie Siebenhofer, Feb 02 2018

A288965 Number of key comparisons to sort all n! permutations of n elements by the optimal dual-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 114, 866, 7188, 65580, 655872, 7157376, 84775680, 1084343040, 14906039040, 219267751680, 3437854963200, 57247256424960, 1009189972869120, 18779054120386560, 367876307230064640, 7568437652936294400, 163164173556503347200, 3678547646214424166400

Offset: 0

Daniel Krenn, Jun 20 2017

nonn

Daniel Krenn, Table of n, a(n) for n = 0..100
M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, arXiv:1611.00258 [math.CO], 2016.
M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, Combin. Probab. Comput. 28(4) (2019), 485-518.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", arXiv:1710.07505 [cs.DS], 2017.
R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", 2018 Proceedings of the Meeting of Analytic Algorithmics and Combinatorics, New Orleans, Louisiana, USA, 7pp.
Index entries for sequences related to sorting

Cf. A058312, A058313, A288964, A288970, A288971.

haralt := proc(n) local k: add((-1)^k/k, k = 1 .. n): end proc:
a := proc(n) local v, v1, v2: if n = 0 or n = 1 then v := 0: end if; if n = 2 then v := 2: end if: if n = 3 then v := 16: end if:
if 4 <= n then v1 := 9/5*n*harmonic(n) - 1/5*n*haralt(n) - 89/25*n + 67/40*harmonic(n) - 3/40*haralt(n) - 83/800 + 1/10*(-1)^n:
if 0 = n mod 2 then v2 := -1/320*1/(n - 3) - 3/320*1/(n - 1): end if:
if 1 = n mod 2 then v2 := 3/320*1/(n - 2) + 1/320*1/n: end if:
v := n!*(v1 + v2): end if: v: end proc:
seq(a(n1), n1 = 0 .. 30); # Petros Hadjicostas, May 03 2020

haralt[n_] := Sum[(-1)^k/k, {k, 1, n}];
a[n_] := Switch[n, 0|1, 0, 2, 2, 3, 16, _, n! ((9/5) n HarmonicNumber[n] - (1/5) n haralt[n] - (89/25) n + (67/40) HarmonicNumber[n] - (3/40)* haralt[n] - 83/800 + (-1)^n/10 - (Boole[EvenQ[n]]/320)(1/(n-3) + 3/(n-1)) + (Boole[OddQ[n]]/320)(3/(n-2) + 1/n))];
a /@ Range[0, 21] (* Jean-François Alcover, Jun 05 2020 *)

lista(nn) = {my(x='x + O('x^nn)); concat([0,0],Vec(serlaplace(-8*log(1-x)/(5*(1-x)^2) + 2*atanh(x)/(5*(1-x)^2) - 44/(25*(1-x)^2) - atanh(x)/(4*(1-x)) + 281/(160*(1-x)) + ((1-x)^3/320)*atanh(x) + x^3/150 - 27*x^2/1600 + 17*x/1600 + 3/800)))}; \\ Petros Hadjicostas and Michel Marcus, May 04 2020, e.g.f. from p. 29 in Aumüller et al. (2016)

a(n) = n!*((9/5)*n*Harmonic(n) - (1/5)*n*Harmonic_alt(n) - (89/25)*n + (67/40)*Harmonic(n) - (3/40)*Harmonic_alt(n) - 83/800 + (-1)^n/10 - ([n even]/320)*(1/(n - 3) + 3/(n - 1)) + ([n odd]/320)*(3/(n - 2) + 1/n)) for n >= 4, where [condition] = 1 if the condition holds, and 0 otherwise, and Harmonic_alt(n) = Sum_{k=1..n} (-1)^n/n = -A058313(n)/A058312(n). [This follows from Theorem 12.1 in Aumüller et al. (2016) or Theorem 5.7 in Aumüller et al. (2019).] - Petros Hadjicostas, May 03 2020

cp's OEIS Frontend

User: Daniel Krenn

A334275 Number of unlabeled connected graphs with n vertices such that every vertex has exactly 2 vertices at distance 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

SageMath

Formula

A289263 Number of maximal roller coasters in all n! permutations of n elements.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Extensions

A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

Formula

A288971 Number of key comparisons to sort all n! permutations of n elements by the optimal quadral-pivot quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A288965 Number of key comparisons to sort all n! permutations of n elements by the optimal dual-pivot quicksort.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula