login
Euler's difference table: triangle read by rows, formed by starting with factorial numbers (A000142) and repeatedly taking differences. T(n,n) = n!, T(n,k) = T(n,k+1) - T(n-1,k).
23

%I #67 Aug 13 2022 15:49:28

%S 1,0,1,1,1,2,2,3,4,6,9,11,14,18,24,44,53,64,78,96,120,265,309,362,426,

%T 504,600,720,1854,2119,2428,2790,3216,3720,4320,5040,14833,16687,

%U 18806,21234,24024,27240,30960,35280,40320,133496,148329,165016,183822,205056,229080,256320,287280,322560,362880

%N Euler's difference table: triangle read by rows, formed by starting with factorial numbers (A000142) and repeatedly taking differences. T(n,n) = n!, T(n,k) = T(n,k+1) - T(n-1,k).

%C Triangle T(n,k) (n >= 1, 1 <= k <= n) giving number of ways of winning with (n-k+1)st card in the generalized "Game of Thirteen" with n cards.

%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 largest fixed point equal to k. Example: T(3,1)=3 because we have 1243, 4213, and 3241.

%C Mirror image of A047920.

%C (End)

%H Reinhard Zumkeller, <a href="/A068106/b068106.txt">Rows n = 0..150 of triangle, flattened</a>

%H W. Y. C. Chen et al., <a href="http://dx.doi.org/10.1016/j.disc.2011.06.006">Higher-order log-concavity in Euler's difference table</a>, Discrete Math., 311 (2011), 2128-2134.

%H P. R. de Montmort, <a href="http://dx.doi.org/10.1007/978-1-4757-3500-0_4">On the Game of Thirteen (1713)</a>, reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.

%H Emeric 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 D. Dumont, <a href="http://www.mat.univie.ac.at/~slc/opapers/s05dumont.html">Matrices d'Euler-Seidel</a>, Sem. Loth. Comb. B05c (1981) 59-78.

%H Philip Feinsilver and John McSorley, <a href="https://arxiv.org/abs/1710.00788">Zeons, Permanents, the Johnson scheme, and Generalized Derangements</a>, arXiv:1710.00788 [math.CO], (2017); see page 29.

%H P. Feinsilver and J. McSorley, <a href="https://doi.org/10.1155/2011/539030">Zeons, Permanents, the Johnson scheme, and Generalized Derangements</a>, International Journal of Combinatorics, 2011 (2011).

%H Fanja Rakotondrajao, <a href="http://www.emis.de/journals/INTEGERS/papers/h36/h36.Abstract.html">k-Fixed-Points-Permutations</a>, Integers: Electronic journal of combinatorial number theory 7 (2007) A36.

%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>

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

%F From _Emeric Deutsch_, Jul 18 2009: (Start)

%F T(n,k) = Sum_{j=0..k} d(n-j)*binomial(k, j), where d(i) = A000166(i) are the derangement numbers.

%F Sum_{k=0..n} (k+1)*T(n,k) = A000166(n+2) (the derangement numbers). (End)

%F T(n, k) = n!*hypergeom([k-n], [-n], -1). - _Peter Luschny_, Oct 05 2017

%F D-finite recurrence for columns: T(n,k) = n*T(n-1,k) + (n-k)*T(n-2,k). - _Georg Fischer_, Aug 13 2022

%e Triangle begins:

%e [0] 1;

%e [1] 0, 1;

%e [2] 1, 1, 2;

%e [3] 2, 3, 4, 6;

%e [4] 9, 11, 14, 18, 24;

%e [5] 44, 53, 64, 78, 96, 120;

%e [6] 265, 309, 362, 426, 504, 600, 720;

%e [7] 1854, 2119, 2428, 2790, 3216, 3720, 4320, 5040.

%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(k, j)*d[n-j], j = 0 .. 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 18 2009

%t t[n_, k_] := Sum[(-1)^j*Binomial[n-k, j]*(n-j)!, {j, 0, n}]; Flatten[ Table[ t[n, k], {n, 0, 9}, {k, 0, n}]] (* _Jean-François Alcover_, Feb 21 2012, after _Philippe Deléham_ *)

%t T[n_, k_] := n! HypergeometricPFQ[{k-n}, {-n}, -1];

%t Table[T[n, k], {n,0,9}, {k,0,n}] // Flatten (* _Peter Luschny_, Oct 05 2017 *)

%o (Haskell)

%o a068106 n k = a068106_tabl !! n !! k

%o a068106_row n = a068106_tabl !! n

%o a068106_tabl = map reverse a047920_tabl

%o -- _Reinhard Zumkeller_, Mar 05 2012

%Y Row sums give A002467.

%Y Diagonals give A000142, A001563, A001564, A001565, A001688, A001689, A023043, A023044, A023045, A023046, A023047 (factorials and k-th differences, k=1..10).

%Y See A047920 and A086764 for other versions.

%Y T(2*n, n) is A033815.

%Y Columns k=0..10 give A000166, A000255, A055790, A277609, A277563, A280425, A280920, A284204, A284205, A284206, A284207.

%K nonn,easy,tabl,nice

%O 0,6

%A _N. J. A. Sloane_, Apr 12 2002

%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 01 2003

%E Edited by _N. J. A. Sloane_, Sep 24 2011