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

1, 2, 4, 1, 1, 8, 3, 4, 16, 104, 40, 24, 1, 32, 392, 896, 480, 54, 64, 152, 308, 1496, 63, 108, 1, 128, 2276, 30384, 14410, 4315, 3024, 14, 256, 7340, 153400, 235252, 24766, 180416, 4984, 448, 1, 512, 23172, 365520, 1713160, 5794944, 3739512, 881152, 63840, 453

Offset

2,2

Comments

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

Conjecture: T(n, 1) = 2^(n-2).

T(2n, 2n-1) = 1, since there is only one derangement of 2n letters with 2n-1 descents.

The analogous sequence for permutations is T'(n, k) = 1. That is, the expected value of the first letter of a permutation with k descents is an integer (namely k + 1).

Links

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

Example

Triangle begins:
    1;
    2;
    4,    1,     1;
    8,    3,     4;
   16,  104,    40,    24,    1;
   32,  392,   896,   480,   54;
   64,  152,   308,  1496,   63,  108,  1;
  128, 2276, 30384, 14410, 4315, 3024, 14.
T(4,1) = 4 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 4 as its denominator.

Crossrefs

Cf. A000166, A083329, A219836.

Numerators are given by A332009.

Sequence in context: A207260 A187913 A329458 * A201287 A236367 A197489

Adjacent sequences: A332007 A332008 A332009 * A332011 A332012 A332013

Keyword

nonn,tabf

Author

Peter Kagey, Feb 04 2020

Status

approved