cp's OEIS Frontend

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.

%I A098825 #56 Feb 16 2025 08:32:54
%S A098825 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,
%T A098825 1,0,21,70,315,924,1855,1854,1,0,28,112,630,2464,7420,14832,14833,1,0,
%U A098825 36,168,1134,5544,22260,66744,133497,133496,1,0,45,240,1890,11088,55650,222480,667485,1334960,1334961
%N 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.
%C A098825 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
%C A098825 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.
%H A098825 Reinhard Zumkeller, <a href="/A098825/b098825.txt">Rows n = 0..125 of triangle, flattened</a>
%H A098825 P. Diaconis, <a href="https://www.jstor.org/stable/4355560">Group Representations in Probability and Statistics</a>, IMS, 1988; see p. 112.
%H A098825 Chris D. H. Evans, John Hughes and Julia Houston, <a href="https://doi.org/10.1348/000711002760554525">Significance-testing the validity of idiographic methods: A little derangement goes a long way</a>, British Journal of Mathematical and Statistical Psychology, 1 November 2002, Vol. 55, pp. 385-390.
%H A098825 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PartialDerangement.html">Partial Derangement</a>
%F A098825 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).
%F A098825 T(n,k) = A008290(n,n-k). - _Vladeta Jovovic_, Sep 04 2006
%F A098825 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
%F A098825 From _Manfred Boergens_, Oct 25 2022: (Start)
%F A098825 T(n, k) = (n!/(n-k)!)*Sum_{j=0..k} (-1)^j/j!.
%F A098825 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)
%F A098825 T(n, k) = (T(n-1, k)*n)/(n - k) for 0 < k < n, T(n, 0) = 1, and T(n, n) = (-1)^n + n*T(n-1, k-1). - _Oliver Seipel_, Nov 26 2024
%e A098825 Assume d(0), d(1), d(2) are given. Then
%e A098825   T(3, 3) = c(3, 3)*d(0) = (1)*(1) = 1;
%e A098825   T(3, 2) = c(3, 2)*d(1) = (3)*(0) = 0;
%e A098825   T(3, 1) = c(3, 1)*d(2) = (3)*(1) = 3;
%e A098825   T(3, 0) = 3! - (1 + 0 + 3) = 6 - 4 = 2.
%e A098825   d(3) = T(3, 0).
%e A098825 Triangle begins:
%e A098825   1;
%e A098825   1, 0;
%e A098825   1, 0,  1;
%e A098825   1, 0,  3,  2;
%e A098825   1, 0,  6,  8,   9;
%e A098825   1, 0, 10, 20,  45,  44;
%e A098825   1, 0, 15, 40, 135, 264,  265;
%e A098825   1, 0, 21, 70, 315, 924, 1855, 1854;
%e A098825   ...
%t A098825 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 A098825 T[n_, k_] := Binomial[n, n-k] Subfactorial[k];
%t A098825 Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Sep 01 2021 *)
%t A098825 (* Sum-free code *)
%t A098825 T[n_, k_] = If[k==0,1,Binomial[n,k] Round[k!/E]];
%t A098825 Table[T[n, k],{n,0,12},{k,0,n}]//Flatten (* _Manfred Boergens_, Oct 25 2022 *)
%o A098825 (Haskell)
%o A098825 a098825 n k = a098825_tabl !! n !! k
%o A098825 a098825_row n = a098825_tabl !! n
%o A098825 a098825_tabl = map (zipWith (*) a000166_list) a007318_tabl
%o A098825 -- _Reinhard Zumkeller_, Dec 16 2013
%o A098825 (Python)
%o A098825 from functools import cache
%o A098825 @cache
%o A098825 def T(n, k):  # (after _Oliver Seipel_)
%o A098825     if k == 0: return 1
%o A098825     if k == n: return (-1)**n + n * T(n-1, k-1)
%o A098825     return (T(n-1, k) * n) // (n - k)
%o A098825 print([T(n, k) for n in range(11) for k in range(n+1)]) # _Peter Luschny_, Nov 30 2024
%Y A098825 Mirror of triangle A008290.
%Y A098825 Cf. A000166, A007318.
%Y A098825 T(2n,n) gives A281262.
%K A098825 nonn,tabl
%O A098825 0,9
%A A098825 _Gerald P. Del Fiacco_, Nov 02 2004
%E A098825 More terms from _Robert G. Wilson v_, Nov 04 2004