login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A161129 Triangle read by rows: T(n,k) is the number of non-derangements of {1,2,...,n} for which the difference between the largest and smallest fixed points is k (n>=1; 0 <= k <= n-1). 1
1, 0, 1, 3, 0, 1, 8, 3, 2, 2, 45, 8, 9, 8, 6, 264, 45, 44, 42, 36, 24, 1855, 264, 265, 256, 234, 192, 120, 14832, 1855, 1854, 1810, 1704, 1512, 1200, 720, 133497, 14832, 14833, 14568, 13950, 12864, 11160, 8640, 5040, 1334960, 133497, 133496, 131642, 127404 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Row sums give the number of non-derangement permutations of {1,2,...,n} (A002467).

T(n,0) = A000240(n) = number of permutations of {1,2,...,n} with exactly 1 fixed point.

T(n,1) = A000240(n-1).

T(n,2) = A000166(n-1) (the derangement numbers).

T(n,3) = A018934(n-1).

Sum_{k=0..n-1} k*T(n,k) = A161130(n).

LINKS

Table of n, a(n) for n=1..50.

E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792 [math.CO], 2009.

FORMULA

T(n,0) = n*d(n-1); T(n,k) = (n-k)*Sum_{j=0..k-1}d(n-2-j)*binomial(k-1,j) for 1 <= k <= n-1, where d(i)=A000166(i) are the derangement numbers.

EXAMPLE

T(4,1)=3 because we have 1243, 4231, and 2134; T(4,2)=2 because we have 1432 and 3214; T(5,4)=6 because we have 1xyz5 where xyz is any permutation of 234.

Triangle starts:

    1;

    0,  1;

    3,  0,  1;

    8,  3,  0,  1;

   45,  8,  9,  8,  6;

  264, 45, 44, 42, 36, 24;

MAPLE

d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k = 0 then n*d[n-1] elif k < n then (n-k)*(sum(binomial(k-1, j)*d[n-2-j], j = 0 .. k-1)) else 0 end if end proc: for n to 10 do seq(T(n, k), k = 0 .. n-1) end do; # yields sequence in triangular form

MATHEMATICA

d = Subfactorial;

T[n_, 0] := n*d[n - 1];

T[n_, k_] := (n - k)*Sum[d[n - j - 2]*Binomial[k - 1, j], {j, 0, k - 1}];

Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Nov 28 2017 *)

CROSSREFS

Cf. A000166, A000240, A002467, A018934, A161130.

Sequence in context: A208758 A320161 A291763 * A011074 A020816 A174860

Adjacent sequences:  A161126 A161127 A161128 * A161130 A161131 A161132

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jul 18 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 6 08:44 EDT 2020. Contains 333268 sequences. (Running on oeis4.)