Voozh

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

(list; table; graph; refs; listen; history; text; internal format)

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

T(n, k) = n!*hypergeom([-k], [-n], -1). - Peter Luschny, Jul 28 2024

EXAMPLE

Triangle begins:

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

# Alternative:

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

T[n_, k_] := n! Hypergeometric1F1[-k, -n, -1];

Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten (* Peter Luschny, Jul 28 2024 *)

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.