cp's OEIS Frontend

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.

%I A289632 #31 Feb 24 2019 02:12:34
%S A289632 1,2,9,1,44,9,265,66,3,1854,530,44,14833,4635,530,11,133496,44499,
%T A289632 6180,265,1334961,467236,74165,4635,53,14684570,5339844,934472,74165,
%U A289632 1854,176214841,66080565,12459636,1168090,44499,309,2290792932,881074205,176214840
%N 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.
%C A289632 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.
%C A289632 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.
%C A289632 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,...
%C A289632 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).
%C A289632 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.?"
%H A289632 Thomas Becker, <a href="/A289632/b289632.txt">Table of n, a(n) for n = 2..10001</a>
%H A289632 Thomas Becker, <a href="https://github.com/walkswiththebear/ConsecutiveSequences">ConsecutiveSequences</a> (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.
%H A289632 Thomas Becker, <a href="https://walkswiththebear.github.io/ConsecutiveSequences/Paper/CountingPermutationsWithConsecutiveSequences.pdf">Two General Purpose Algorithms for Counting Permutations with Consecutive Sequences</a>, 2017. This paper has the mathematical description and correctness proofs for the algorithms in the repository above.
%H A289632 Thomas Becker, <a href="http://blog.greaterthanzero.com/post/159874910652/some-mathematics-algorithms-and-probabilities"> Some Mathematics, Algorithms, and Probabilities Concerning Your Music Player's Random Shuffle Mode</a>, 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.
%F A289632 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.
%e A289632 The first ten rows of the triangle are:
%e A289632          1;
%e A289632          2;
%e A289632          9,       1;
%e A289632         44,       9;
%e A289632        265,      66,      3;
%e A289632       1854,     530,     44;
%e A289632      14833,    4635,    530,    11;
%e A289632     133496,   44499,   6180,   265;
%e A289632    1334961,  467236,  74165,  4635,   53;
%e A289632   14684570, 5339844, 934472, 74165, 1854;
%o A289632 (JavaScript)
%o A289632 /*
%o A289632 * The program below calls into the algorithm package "ConsecutiveSequences" (see link to github repository).
%o A289632 */
%o A289632 var numberOfPermutationsModule = require("ConsecutiveSequences.min.js");
%o A289632 var mcsSpec = {};
%o A289632 var numPermutations;
%o A289632 var numElements = 42;
%o A289632 var count = 7;
%o A289632 // Calculate the number of permutations that have exactly count many maximal consecutive
%o A289632 // sequences of length 2 and no maximal consecutive sequences of length other than 2.
%o A289632 //
%o A289632 mcsSpec["2"] = count;
%o A289632 numPermutations =
%o A289632   numberOfPermutationsModule.numberOfPermutationsThatMeetAnMcsSpecificationByLengthsAndCounts(
%o A289632   numElements,
%o A289632   mcsSpec
%o A289632   );
%Y A289632 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).
%Y A289632 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.
%K A289632 nonn,tabf
%O A289632 2,2
%A A289632 _Thomas Becker_, Jul 08 2017