login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A098825 Triangle read by rows: T(n,k) = number of partial derangements, that is, the number of permutations of n distinct, ordered items in which exactly k of the items are in their natural ordered positions, for n >= 0, k = n, n-1, ..., 1, 0. 35
1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 6, 8, 9, 1, 0, 10, 20, 45, 44, 1, 0, 15, 40, 135, 264, 265, 1, 0, 21, 70, 315, 924, 1855, 1854, 1, 0, 28, 112, 630, 2464, 7420, 14832, 14833, 1, 0, 36, 168, 1134, 5544, 22260, 66744, 133497, 133496, 1, 0, 45, 240, 1890, 11088, 55650, 222480, 667485, 1334960, 1334961 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

In other words, T(n,k) is the number of permutations of n letters that are at Hammimg distance k from the identity permutation (cf. Diaconis, p. 112). - N. J. A. Sloane, Mar 02 2007

The sequence d(n) = 1, 0, 1, 2, 9, 44, 265, 1854, 14833, ... (A000166) is the number of derangements, that is, the number of permutations of n distinct, ordered items in which none of the items is in its natural ordered position.

LINKS

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened

P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.

Chris D. H. Evans, John Hughes and Julia Houston, Significance-testing the validity of idiographic methods: A little derangement goes a long way, British Journal of Mathematical and Statistical Psychology, 1 November 2002, Vol. 55, pp. 385-390.

Eric Weisstein's World of Mathematics, Partial Derangement

FORMULA

T(0, 0) = 1; d(0) = T(0, 0); for k = n, n-1, ..., 1, T(n, k) = c(n, k) d(n-k) where c(n, k) = n! / [(k!) (n-k)! ]; T(n, 0) = n! - [ T(n, n) + T(n, n-1) + ... + T(n, 1) ]; d(n) = T(n, 0).

T(n,k) = A008290(n,n-k). - Vladeta Jovovic, Sep 04 2006

Assuming a uniform distribution on S_n, the mean Hamming distance is n-1 and the variance is 1 (Diaconis, p. 117). - N. J. A. Sloane, Mar 02 2007

From Manfred Boergens, Oct 25 2022: (Start)

T(n, k) = (n!/(n-k)!)*Sum_{j=0..k} (-1)^j/j!.

T(n,0)=1; T(n, k) = C(n, k)*round(k!/e) = C(n,k)*A000166(k) = C(n, k)*floor(k!/e + 1/2) for k > 0. (End)

EXAMPLE

Assume d(0), d(1), d(2) are given. Then

T(3, 3) = c(3, 3)*d(0) = (1)*(1) = 1;

T(3, 2) = c(3, 2)*d(1) = (3)*(0) = 0;

T(3, 1) = c(3, 1)*d(2) = (3)*(1) = 3;

T(3, 0) = 3! - (1 + 0 + 3) = 6 - 4 = 2.

d(3) = T(3, 0).

Triangle begins:

1;

1, 0;

1, 0, 1;

1, 0, 3, 2;

1, 0, 6, 8, 9;

1, 0, 10, 20, 45, 44;

1, 0, 15, 40, 135, 264, 265;

1, 0, 21, 70, 315, 924, 1855, 1854;

...

MATHEMATICA

t[0, 0] = 1; t[n_, k_] := Binomial[n, k]*k!*Sum[(-1)^j/j!, {j, 0, k}]; Flatten[ Table[ t[n, k], {n, 0, 10}, {k, 0, n}]] (* Robert G. Wilson v, Nov 04 2004 *)

T[n_, k_] := Binomial[n, n-k] Subfactorial[k];

Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 01 2021 *)

(* Sum-free code *)

T[n_, k_] = If[k==0, 1, Binomial[n, k] Round[k!/E]];

Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* Manfred Boergens, Oct 25 2022 *)

PROG

(Haskell)

a098825 n k = a098825_tabl !! n !! k

a098825_row n = a098825_tabl !! n

a098825_tabl = map (zipWith (*) a000166_list) a007318_tabl

-- Reinhard Zumkeller, Dec 16 2013

CROSSREFS

Mirror of triangle A008290.

Cf. A000166, A007318.

T(2n,n) gives A281262.

Sequence in context: A194753 A359400 A323908 * A111460 A035327 A004444

Adjacent sequences: A098822 A098823 A098824 * A098826 A098827 A098828

KEYWORD

nonn,tabl

AUTHOR

Gerald P. Del Fiacco, Nov 02 2004

EXTENSIONS

More terms from Robert G. Wilson v, Nov 04 2004

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 31 16:08 EDT 2023. Contains 361668 sequences. (Running on oeis4.)