A126065 Triangle of numbers read by rows: T(n,k) = number of permutations sigma of (1,2,...,n) with n - {length of longest increasing subsequence in sigma} = k (0<=k<=n-1).

1, 1, 1, 1, 4, 1, 1, 9, 13, 1, 1, 16, 61, 41, 1, 1, 25, 181, 381, 131, 1, 1, 36, 421, 1821, 2332, 428, 1, 1, 49, 841, 6105, 17557, 14337, 1429, 1, 1, 64, 1513, 16465, 83029, 167449, 89497, 4861, 1, 1, 81, 2521, 38281, 296326, 1100902, 1604098, 569794, 16795, 1

Offset

1,5

Comments

T(n,k) is the number of permutations in S_n with Ulam distance from the identity equal to k.

Mirror image of triangle in A047874.

References

P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.

See A047874 for further references, etc.

Links

Alois P. Heinz, Rows n = 1..60, flattened

E. Irurozki, Sampling and learning distance-based probability models for permutation spaces, PhD Dissertation, Department of Computer Science and Artificial Intelligence of the University of the Basque Country, 2015.

E. Irurozki, B. Calvo, J. Ceberio, and J. A. Lozano, Mallows model under the Ulam distance: a feasible combinatorial approach, 2014.

Ekhine Irurozki, B. Calvo, J. A. Lozano, PerMallows: An R Package for Mallows and Generalized Mallows Models, Journal of Statistical Software, August 2016, Volume 71, Issue 12. doi: 10.18637/jss.v071.i12

Example

Triangle T(n,k) begins:
  1;
  1,   1;
  1,   4,    1;
  1,  13,    9,    1;
  1,  41,   61,   16,   1;
  1, 131,  381,  181,  25,  1;
  1, 428, 2332, 1821, 421, 36, 1;
  ...

Crossrefs

T(2n,n) gives A267433.

Sequence in context: A189280 A168621 A039756 * A299427 A126062 A243608

Adjacent sequences: A126062 A126063 A126064 * A126066 A126067 A126068

Keyword

nonn,tabl

Author

N. J. A. Sloane, Mar 01 2007

Status

approved