A047920 Triangular array formed from successive differences of factorial numbers.

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, 362, 309, 265, 5040, 4320, 3720, 3216, 2790, 2428, 2119, 1854, 40320, 35280, 30960, 27240, 24024, 21234, 18806, 16687, 14833, 362880, 322560

Offset

0,4

Comments

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

From Emeric Deutsch, Apr 21 2009: (Start)

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).

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

Mirror image of A068106.

Closely related to A134830, where each row has an extra term (see the Charalambides reference).

(End)

T(n,k) is the number of permutations of {1..n} that don't fix the points 1..k. - Robert FERREOL, Aug 04 2016

References

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 176, Table 5.3. [From Emeric Deutsch, Apr 21 2009]

Links

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

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

J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]

J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122.

Ira M. Gessel, Symmetric inclusion-exclusion, Séminaire Lotharingien de Combinatoire, B54b (2005).

Peter Kagey, Ranking and Unranking Restricted Permutations, arXiv:2210.17021 [math.CO], 2022.

Index entries for sequences related to factorial numbers

Formula

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

T(n, k) = Sum_{j>=0} (-1)^j * binomial(k, j)*(n-j)!. - Philippe Deléham, May 29 2005

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

Sum_{k=0..n} (k+1)*T(n,k) = A155521(n+1). - Emeric Deutsch, Jul 18 2009

Example

Triangle begins:
    1;
    1,  0;
    2,  1,  1;
    6,  4,  3,  2;
   24, 18, 14, 11,  9;
  120, 96, 78, 64, 53, 44;
  ...
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

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 <= 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
# second Maple program:
T:= proc(n, k) option remember;
     `if`(k=0, n!, T(n, k-1)-T(n-1, k-1))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Sep 01 2021

Mathematica

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 *)

Prog

(Haskell)
a047920 n k = a047920_tabl !! n !! k
a047920_row n = a047920_tabl !! n
a047920_tabl = map fst $ iterate e ([1], 1) where
   e (row, n) = (scanl (-) (n * head row) row, n + 1)
-- Reinhard Zumkeller, Mar 05 2012
(PARI) row(n) = vector(n+1, k, k--; sum(j=0, n, (-1)^j * binomial(k, j)*(n-j)!)); \\ Michel Marcus, Sep 04 2021

Crossrefs

Columns give A000142, A001563, A001564, etc. Cf. A047922.

See A068106 for another version of this triangle.

Orthogonal columns: A000166, A000255, A055790. Main diagonal A033815.

Cf. A002467, A068106, A134830. - Emeric Deutsch, Apr 21 2009

Cf. A155521.

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).

T(n+7,n) = 5040*A176733(n) - Richard R. Forberg, Dec 29 2013

Sequence in context: A103880 A135899 A327816 * A350269 A249673 A144655

Adjacent sequences: A047917 A047918 A047919 * A047921 A047922 A047923

Keyword

nonn,tabl,easy,nice

Author

N. J. A. Sloane

Status

approved