A307030 -id:A307030 - cp's OEIS frontend

A309993 Triangle read by rows: T(n,k) is the number of permutations of length n composed of exactly k overlapping adjacent runs (for n >= 1 and 1 <= k <= n).

1, 1, 0, 1, 2, 0, 1, 8, 2, 0, 1, 22, 26, 0, 0, 1, 52, 168, 42, 0, 0, 1, 114, 804, 692, 42, 0, 0, 1, 240, 3270, 6500, 1866, 0, 0, 0, 1, 494, 12054, 46304, 34078, 3060, 0, 0, 0, 1, 1004, 41708, 279566, 413878, 122830, 3060, 0, 0, 0, 1, 2026, 138320, 1514324

Offset: 1

Bjarki Ágúst Guðmundsson, Aug 26 2019

Permutations of A307030 grouped by number of runs. Thus row sums give A307030.

Each column admits a rational generating function (Asinowski et al.).

			For n = 3 the permutations with overlapping runs are 123, 132, 213. The first has k = 1 runs, the other two have k = 2 runs. Thus T(3,1) = 1, T(3,2) = 2, T(3,3) = 0.
Triangle begins:
  1;
  1,    0;
  1,    2,     0;
  1,    8,     2,      0;
  1,   22,    26,      0,      0;
  1,   52,   168,     42,      0,      0;
  1,  114,   804,    692,     42,      0,    0;
  1,  240,  3270,   6500,   1866,      0,    0, 0;
  1,  494, 12054,  46304,  34078,   3060,    0, 0, 0;
  1, 1004, 41708, 279566, 413878, 122830, 3060, 0, 0, 0;
  ...

Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 1..5050
Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl, Svante Linusson, Pop-stack sorting and its image: Permutations with overlapping runs (2019), preprint.
Anders Claesson, Bjarki Ágúst Guðmundsson, Jay Pantone, Counting pop-stacked permutations in polynomial time, arXiv:1908.08910 [math.CO], 2019.

Cf. A307030.

G.f. for column k=1: x/(1-x).
G.f. for column k=2: 2*x^3/((1-x)^2*(1-2*x)).
G.f. for column k=3: -2*x^4*(6*x^2 - 3*x - 1)/((1-x)^3*(1-2*x)^2*(1-3*x)).
G.f. for column k=4: -2*x^6*(144*x^4 - 180*x^3 - 5*x^2 + 74*x - 21)/((1-x)^4*(1-2*x)^3*(1-3*x)^2*(1-4*x)).
G.f. for column k=5: 2*x^7*(17280*x^8 - 37600*x^7 + 12784*x^6 + 33060*x^5 - 40581*x^4 + 18982*x^3 - 3856*x^2 + 198*x + 21)/((1-x)^5*(1-2*x)^4*(1-3*x)^3*(1-4*x)^2*(1-5*x)).

A327833 Number of non-overlapping pairs of adjacent runs in permutations of [n].

Original entry on oeis.org

1, 1, 4, 18, 100, 665, 5124, 44772, 437016, 4710915, 55568480, 711802894, 9838192572, 145921265581, 2311617527660, 38950657146120, 695562375445104, 13121344429311687, 260728755911619336, 5443039353326333330, 119101575356825879860, 2725785134463572716689

Offset: 1

David Bevan, Sep 27 2019

nonn

A run is a maximal consecutive subsequence of increasing values; two adjacent runs are non-overlapping if the least value in the first run exceeds the greatest value in the second.

Permutations all of whose adjacent runs overlap are in the image of the pop-stack sorting operation (see A307030 and references).

			a(3) = 4: one non-overlapping pair of adjacent runs in both 231 and 312, and two non-overlapping pairs in 321; the pairs of adjacent runs in 132 and 213 overlap.

Table[If[n==1,1,(n-1)n!-(n/3-1/2)Floor[E n!]+(n/6-1/2)],{n,20}]

a(n) = (n-1)*n! - (n/3-1/2)*floor(e*n!) + (n/6-1/2), for all n > 1.

Asymptotically, the expected number of non-overlapping adjacent pairs of runs an n-permutation is (1-e/3)*n + (e/2-1).

cp's OEIS Frontend

A309993 Triangle read by rows: T(n,k) is the number of permutations of length n composed of exactly k overlapping adjacent runs (for n >= 1 and 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula