%I #80 Jul 28 2024 04:17:28
%S 1,1,0,2,1,1,6,4,3,2,24,18,14,11,9,120,96,78,64,53,44,720,600,504,426,
%T 362,309,265,5040,4320,3720,3216,2790,2428,2119,1854,40320,35280,
%U 30960,27240,24024,21234,18806,16687,14833,362880,322560
%N Triangular array formed from successive differences of factorial numbers.
%C Number of permutations of 1,2,...,k,n+1,n+2,...,2n-k that have no agreements with 1,...,n. For example, consider 1234 and 1256, then n=4 and k=2, so T(4,2)=14. Compare A000255 for the case k=1. - _Jon Perry_, Jan 23 2004
%C From _Emeric Deutsch_, Apr 21 2009: (Start)
%C T(n-1,k-1) is the number of non-derangements of {1,2,...,n} having smallest fixed point equal to k. Example: T(3,1)=4 because we have 4213, 4231, 3214, and 3241 (the permutations of {1,2,3,4} having smallest fixed equal to 2).
%C Row sums give the number of non-derangement permutations of {1,2,...,n} (A002467).
%C Mirror image of A068106.
%C Closely related to A134830, where each row has an extra term (see the Charalambides reference).
%C (End)
%C T(n,k) is the number of permutations of {1..n} that don't fix the points 1..k. - _Robert FERREOL_, Aug 04 2016
%D Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 176, Table 5.3. [From _Emeric Deutsch_, Apr 21 2009]
%H Reinhard Zumkeller, <a href="/A047920/b047920.txt">Rows n = 0..150 of triangle, flattened</a>
%H E. Deutsch and S. Elizalde, <a href="http://arxiv.org/abs/0904.2792">The largest and the smallest fixed points of permutations</a>, arXiv:0904.2792 [math.CO], 2009.
%H J. D. H. Dickson, <a href="/A002775/a002775.pdf">Discussion of two double series arising from the number of terms in determinants of certain forms</a>, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]
%H J. D. H. Dickson, <a href="https://doi.org/10.1112/plms/s1-10.1.120">Discussion of two double series arising from the number of terms in determinants of certain forms</a>, Proc. London Math. Soc., 10 (1879), 120-122.
%H Ira M. Gessel, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s54gessel.html">Symmetric inclusion-exclusion</a>, Séminaire Lotharingien de Combinatoire, B54b (2005).
%H Peter Kagey, <a href="https://arxiv.org/abs/2210.17021">Ranking and Unranking Restricted Permutations</a>, arXiv:2210.17021 [math.CO], 2022.
%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>
%F t(n, k) = t(n, k-1) - t(n-1, k-1) = t(n, k+1) - t(n-1, k) = n*t(n-1, k) + k*t(n-2, k-1) = (n-1)*t(n-1, k-1) + (k-1)*t(n-2, k-2) = A060475(n, k)*(n-k)!. - _Henry Bottomley_, Mar 16 2001
%F T(n, k) = Sum_{j>=0} (-1)^j * binomial(k, j)*(n-j)!. - _Philippe Deléham_, May 29 2005
%F T(n,k) = Sum_{j=0..n-k} d(n-j)*binomial(n-k,j), where d(i)=A000166(i) are the derangement numbers. - _Emeric Deutsch_, Jul 17 2009
%F Sum_{k=0..n} (k+1)*T(n,k) = A155521(n+1). - _Emeric Deutsch_, Jul 18 2009
%F T(n, k) = n!*hypergeom([-k], [-n], -1). - _Peter Luschny_, Jul 28 2024
%e Triangle begins:
%e 1;
%e 1, 0;
%e 2, 1, 1;
%e 6, 4, 3, 2;
%e 24, 18, 14, 11, 9;
%e 120, 96, 78, 64, 53, 44;
%e ...
%e The left-hand column is the factorial numbers (A000142). The other numbers in the row are calculated by subtracting the numbers in the previous row. For example, row 4 is 6, 4, 3, 2, so row 5 is 4! = 24, 24 - 6 = 18, 18 - 4 = 14, 14 - 3 = 11, 11 - 2 = 9. - _Michael B. Porter_, Aug 05 2016
%p d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k <= n then sum(binomial(n-k, j)*d[n-j], j = 0 .. n-k) else 0 end if end proc: for n from 0 to 9 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form - _Emeric Deutsch_, Jul 17 2009
%p # second Maple program:
%p T:= proc(n, k) option remember;
%p `if`(k=0, n!, T(n, k-1)-T(n-1, k-1))
%p end:
%p seq(seq(T(n, k), k=0..n), n=0..12); # _Alois P. Heinz_, Sep 01 2021
%t t[n_, k_] = Sum[(-1)^j*Binomial[k, j]*(n-j)!, {j, 0, n}]; Flatten[Table[t[n, k], {n, 0, 9}, {k, 0, n}]][[1 ;; 47]] (* _Jean-François Alcover_, May 17 2011, after _Philippe Deléham_ *)
%t T[n_, k_] := n! Hypergeometric1F1[-k, -n, -1];
%t Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten (* _Peter Luschny_, Jul 28 2024 *)
%o (Haskell)
%o a047920 n k = a047920_tabl !! n !! k
%o a047920_row n = a047920_tabl !! n
%o a047920_tabl = map fst $ iterate e ([1], 1) where
%o e (row, n) = (scanl (-) (n * head row) row, n + 1)
%o -- _Reinhard Zumkeller_, Mar 05 2012
%o (PARI) row(n) = vector(n+1, k, k--; sum(j=0, n, (-1)^j * binomial(k, j)*(n-j)!)); \\ _Michel Marcus_, Sep 04 2021
%Y Columns give A000142, A001563, A001564, etc. Cf. A047922.
%Y See A068106 for another version of this triangle.
%Y Orthogonal columns: A000166, A000255, A055790. Main diagonal A033815.
%Y Cf. A002467, A068106, A134830. - _Emeric Deutsch_, Apr 21 2009
%Y Cf. A155521.
%Y T(n+2,n) = 2*A000153(n+1). T(n+3,n) = 6*A000261(n+2). T(n+4,n) = 24*A001909(n+3). T(n+5, n) = 120*A001910(n+4). T(n+6,n) = 720*A176732(n).
%Y T(n+7,n) = 5040*A176733(n) - _Richard R. Forberg_, Dec 29 2013
%K nonn,tabl,easy,nice
%O 0,4
%A _N. J. A. Sloane_