login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047920 Triangular array formed from successive differences of factorial numbers. 19

%I

%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="http://plms.oxfordjournals.org/content/s1-10/1/120.extract">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 <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

%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

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

%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

%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_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 00:28 EST 2020. Contains 332006 sequences. (Running on oeis4.)