A289632 Triangle read by rows: T(n-1,k), where n >= 2 and 1 <= k <= floor(n/2), is the number of permutations of (1, 2, ..., n) having k consecutive pairs but no consecutive sequences of length greater than 2.

1, 2, 9, 1, 44, 9, 265, 66, 3, 1854, 530, 44, 14833, 4635, 530, 11, 133496, 44499, 6180, 265, 1334961, 467236, 74165, 4635, 53, 14684570, 5339844, 934472, 74165, 1854, 176214841, 66080565, 12459636, 1168090, 44499, 309, 2290792932, 881074205, 176214840

Offset: 2

Author

Thomas Becker, Jul 08 2017

Keywords

• nonn
• tabf

Comments

A consecutive sequence of length m in a permutation P of the integers (1, 2, ..., n) is a contiguous subsequence of m consecutive integers in P, that is, a contiguous subsequence of the form (i, i+1, ..., i+m-1). A consecutive sequence of length 2 is also referred to as a consecutive pair. Consecutive pairs are also called successions or small ascents.

This triangle has the number of permutations of n elements (n >= 2) that have k consecutive pairs (1 <= k <= floor(n/2)) but no consecutive sequences of length greater than 2. So these are the permutations that have consecutive pairs, but only isolated ones, i.e., pairs that are not linked to form longer consecutive sequences.

The entry T(n-1,k) of the triangle (n >= 2) is the number of permutations of n elements having k consecutive pairs and no longer consecutive sequences. It is easy to see that the length of the i-th row is floor((i+1)/2), resulting in the row lengths 1,1,2,2,3,3,...

Following are the nine permutations of five elements that have exactly two consecutive pairs and no consecutive sequences of length greater than 2: (1,2,4,5,3), (1,2,5,3,4), (1,4,5,2,3), (2,3,1,4,5), (3,1,2,4,5), (3,4,1,2,5), (4,5,2,3,1),(4,5,3,1,2), (5,3,4,1,2).

The author's interest in the number of permutations having a specified configuration of consecutive sequences grew out of conversations with non-mathematicians about shuffle mode on today's music players: "If shuffle mode on my music player were truly random (which it isn't), what would be the odds for me to hear exactly one consecutive pair but no triple, two consecutive pairs but no triple, one triple but no pair, any consecutive sequence at all, etc.?"

Examples

			The first ten rows of the triangle are:
         1;
         2;
         9,       1;
        44,       9;
       265,      66,      3;
      1854,     530,     44;
     14833,    4635,    530,    11;
    133496,   44499,   6180,   265;
   1334961,  467236,  74165,  4635,   53;
  14684570, 5339844, 934472, 74165, 1854;
		

Links

• Thomas Becker, Table of n, a(n) for n = 2..10001
• Thomas Becker, ConsecutiveSequences (github repository). This repository has JavaScript implementations of some algorithms concerning consecutive sequences in permutations, among them the algorithm that was used to calculate this triangle.
• Thomas Becker, Two General Purpose Algorithms for Counting Permutations with Consecutive Sequences, 2017. This paper has the mathematical description and correctness proofs for the algorithms in the repository above.
• Thomas Becker, Some Mathematics, Algorithms, and Probabilities Concerning Your Music Player's Random Shuffle Mode, 2017. This blog entry has the discussion of random shuffle mode on today's music players that prompted the author's interest in the number of permutations with specified configurations of consecutive sequences.

Crossrefs

The first column of the triangle is the number of permutations of n elements that have exactly one consecutive pair. This is known to be the same as the subfactorial or rencontres numbers, or derangements (A000166).

A010027 has the number of permutations of n elements with k consecutive pairs, without the restriction that the consecutive pairs must not be "linked" to form longer consecutive sequences.

Programs

JavaScript

/*
* The program below calls into the algorithm package "ConsecutiveSequences" (see link to github repository).
*/
var numberOfPermutationsModule = require("ConsecutiveSequences.min.js");
var mcsSpec = {};
var numPermutations;
var numElements = 42;
var count = 7;
// Calculate the number of permutations that have exactly count many maximal consecutive
// sequences of length 2 and no maximal consecutive sequences of length other than 2.
//
mcsSpec["2"] = count;
numPermutations =
  numberOfPermutationsModule.numberOfPermutationsThatMeetAnMcsSpecificationByLengthsAndCounts(
  numElements,
  mcsSpec
  );

Formula

The entry T(n-1,k) of the triangle, that is, the number of permutations of n elements having k consecutive pairs and no longer consecutive sequences, is given by T(n-1,k) = u(n-k) * binomial(n-k, k) where u(n) is the number of permutations of n elements that have no consecutive sequences at all. This is a special case of a more general formula that gives the number of permutations that have a specified number of maximal consecutive sequences for each possible length. (A consecutive sequence is called maximal if it is not a subsequence of a longer consecutive sequence.) See the links in the "Links" section for details.