login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047920 Triangular array formed from successive differences of factorial numbers. 15
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).

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

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

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: A186023 A103880 A135899 * A249673 A144655 A190782

Adjacent sequences:  A047917 A047918 A047919 * A047921 A047922 A047923

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 16:53 EDT 2018. Contains 316529 sequences. (Running on oeis4.)