A332009 Irregular triangle of numerators of the average value of the first letter over all derangements of {1, 2, ..., n} with k descents.

2, 5, 11, 3, 4, 23, 10, 17, 47, 367, 173, 121, 6, 95, 1431, 3973, 2513, 331, 191, 567, 1395, 8011, 391, 761, 8, 383, 8615, 139897, 78483, 27201, 21685, 113, 767, 28073, 715277, 1298393, 158189, 1310499, 40613, 4049, 10, 1535, 89311, 1721203, 9555617, 37414903, 27455053, 7254087, 582767, 4549

Offset

2,1

Comments

Even-indexed rows have length n - 1; odd-indexed rows have length n - 2.

Conjecture: T(n, 1) = A083329(n - 1).

T(2n, 2n-1) = 2n, since the only derangement of 2n letters with 2n-1 descents is [2n, 2n-1,...,3,2,1].

The analogous sequence for permutations is T'(n, k) = k + 1.

Links

Table of n, a(n) for n=2..51.

Example

Triangle begins:
    2;
    5;
   11,    3,    4;
   23,   10,   17;
   47,  367,  173,  121,   6;
   95, 1431, 3973, 2513, 331;
  191,  567, 1395, 8011, 391, 761, 8.
T(4,1) = 11 because the derangements of four letters with one descent are
[2,3,4,1], [2,4,1,3], [3,4,1,2], and [4,1,2,3], and the expected value of the first letter is (2+2+3+4)/4 = 11/4, which has 11 as its numerator.

Prog

(PARI)
descents(p)={sum(i=2, #p, p[i]<p[i-1])}
isderange(p)={for(i=1, #p, if(p[i]==i, return(0))); 1}
qrow(n, f=numerator)={my(s=vector(n-n%2-1), d=vector(#s)); forperm(n, p, if(isderange(p), my(k=descents(p)); d[k]++; s[k]+=p[1])); vector(#s, k, f(s[k]/d[k]))}
{ for(n=2, 8, print(qrow(n, numerator))) } \\ Andrew Howroyd, Feb 02 2022

Crossrefs

Cf. A000166, A083329, A219836.

Denominators are given by A332010.

Sequence in context: A163784 A215615 A018862 * A175310 A175311 A246208

Adjacent sequences: A332006 A332007 A332008 * A332010 A332011 A332012

Keyword

nonn,tabf

Author

Peter Kagey, Feb 04 2020

Extensions

Terms a(27) and beyond from Andrew Howroyd, Feb 02 2022

Status

approved