A140526 Number of derangements of n elements with one pair repeated exactly once (e.g., "ABABCDEF").

1, 4, 29, 230, 2033, 19744, 209581, 2418226, 30173825, 405194012, 5830108061, 89520810334, 1461569944369, 25288635875320, 462312939395693, 8905623605897834, 180313351427440001, 3828575562533760436

Offset

4,2

Links

Table of n, a(n) for n=4..21.

Hugo M. Spinelli, Program code related to this sequence

Formula

a(n) = ( (n^4 - 10*n^3 + 37*n^2 - 56*n + 25) * A000166(n-4) + (-1)^n * (-n^3 + 8*n^2 - 22*n + 19) ) / 4. - Max Alekseyev, Sep 22 2009

Example

a(4)=1 because "aabb" has only one derangement: "bbaa";
a(5)=4 because "aabbc" has four derangements: "bbaca", "bbcaa", "bcaab" and "cbaab".

Mathematica

A000166[n_] := Floor[n!/E + 1/2]; a[4] = 1; a[n_] := ((n^4 - 10*n^3 + 37*n^2 - 56*n + 25)*A000166[n-4] + (-1)^n*(-n^3 + 8*n^2 - 22*n + 19))/4; Table[ a[n], {n, 4, 21}] (* Jean-François Alcover, Jan 30 2012, after Max Alekseyev *)

Crossrefs

Cf. A105927 for derangements with an element repeated exactly once and no other repetition (e.g., "AABCDEF"); A105928 for derangements with an element appearing three times and no other repetition (e.g., "AAABCDEF").

Sequence in context: A344098 A221415 A087809 * A151343 A371743 A208812

Adjacent sequences: A140523 A140524 A140525 * A140527 A140528 A140529

Keyword

nonn,nice

Author

Hugo M. Spinelli (woodcroft(AT)poli.ufrj.br), Jul 02 2008, Jul 25 2008

Extensions

Extended by Max Alekseyev, Sep 22 2009

Status

approved