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

Author

N. J. A. Sloane, Mar 01 2007

Keywords

• nonn
• tabl

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.

Examples

			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;
  ...
		

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

Crossrefs

T(2n,n) gives A267433.