|
| |
|
|
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.
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,2
|
|
|
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.?"
|
|
|
LINKS
|
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.
|
|
|
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.
|
|
|
EXAMPLE
|
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;
|
|
|
PROG
|
(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
);
|
|
|
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.
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
