A023044 -id:A023044 - cp's OEIS frontend

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

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, 504, 600, 720, 1854, 2119, 2428, 2790, 3216, 3720, 4320, 5040, 14833, 16687, 18806, 21234, 24024, 27240, 30960, 35280, 40320, 133496, 148329, 165016, 183822, 205056, 229080, 256320, 287280, 322560, 362880

Offset: 0

N. J. A. Sloane, Apr 12 2002

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.
From Emeric Deutsch, Apr 21 2009: (Start)
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.
Mirror image of A047920.
(End)

			Triangle begins:
[0]    1;
[1]    0,    1;
[2]    1,    1,    2;
[3]    2,    3,    4,    6;
[4]    9,   11,   14,   18,   24;
[5]   44,   53,   64,   78,   96,  120;
[6]  265,  309,  362,  426,  504,  600,  720;
[7] 1854, 2119, 2428, 2790, 3216, 3720, 4320, 5040.

Reinhard Zumkeller, Rows n = 0..150 of triangle, flattened
W. Y. C. Chen et al., Higher-order log-concavity in Euler's difference table, Discrete Math., 311 (2011), 2128-2134.
P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.
Emeric Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792 [math.CO], 2009.
D. Dumont, Matrices d'Euler-Seidel, Sem. Loth. Comb. B05c (1981) 59-78.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson scheme, and Generalized Derangements, arXiv:1710.00788 [math.CO], (2017); see page 29.
P. Feinsilver and J. McSorley, Zeons, Permanents, the Johnson scheme, and Generalized Derangements, International Journal of Combinatorics, 2011 (2011).
Fanja Rakotondrajao, k-Fixed-Points-Permutations, Integers: Electronic journal of combinatorial number theory 7 (2007) A36.
Index entries for sequences related to factorial numbers

Row sums give A002467.
Diagonals give A000142, A001563, A001564, A001565, A001688, A001689, A023043, A023044, A023045, A023046, A023047 (factorials and k-th differences, k=1..10).
See A047920 and A086764 for other versions.
T(2*n, n) is A033815.
Columns k=0..10 give A000166, A000255, A055790, A277609, A277563, A280425, A280920, A284204, A284205, A284206, A284207.

a068106 n k = a068106_tabl !! n !! k
a068106_row n = a068106_tabl !! n
a068106_tabl = map reverse a047920_tabl
-- Reinhard Zumkeller, Mar 05 2012

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[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[n_, k_] := n! HypergeometricPFQ[{k-n}, {-n}, -1];
Table[T[n, k], {n,0,9}, {k,0,n}] // Flatten (* Peter Luschny, Oct 05 2017 *)

T(n, k) = Sum_{j>= 0} (-1)^j*binomial(n-k, j)*(n-j)!. - Philippe Deléham, May 29 2005
From Emeric Deutsch, Jul 18 2009: (Start)
T(n,k) = Sum_{j=0..k} d(n-j)*binomial(k, j), where d(i) = A000166(i) are the derangement numbers.
Sum_{k=0..n} (k+1)*T(n,k) = A000166(n+2) (the derangement numbers). (End)
T(n, k) = n!*hypergeom([k-n], [-n], -1). - Peter Luschny, Oct 05 2017
D-finite recurrence for columns: T(n,k) = n*T(n-1,k) + (n-k)*T(n-2,k). - Georg Fischer, Aug 13 2022

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

Edited by N. J. A. Sloane, Sep 24 2011

A086764 Triangle T(n, k), read by row, related to Euler's difference table A068106 (divide column k of A068106 by k!).

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 3, 2, 1, 9, 11, 7, 3, 1, 44, 53, 32, 13, 4, 1, 265, 309, 181, 71, 21, 5, 1, 1854, 2119, 1214, 465, 134, 31, 6, 1, 14833, 16687, 9403, 3539, 1001, 227, 43, 7, 1, 133496, 148329, 82508, 30637, 8544, 1909, 356, 57, 8, 1

Offset: 0

Philippe Deléham, Aug 02 2003

The k-th column sequence, k >= 0, without leading zeros, enumerates the ways to distribute n beads, n >= 1, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k+1 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords each contribute a factor 1, hence for n=0 one has 1. See A000255 for the description of a fixed cord with beads. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010

			Formatted as a square array:
      1      3     7    13   21   31  43 57 ... A002061;
      2     11    32    71  134  227 356    ... A094792;
      9     53   181   465 1001 1909        ... A094793;
     44    309  1214  3539 8544             ... A094794;
    265   2119  9403 30637                  ... A023043;
   1854  16687 82508                        ... A023044;
  14833 148329                              ... A023045;
Formatted as a triangular array (mirror of A076731):
       1;
       0      1;
       1      1     1;
       2      3     2     1;
       9     11     7     3    1;
      44     53    32    13    4    1;
     265    309   181    71   21    5    1;
    1854   2119  1214   465  134   31    6   1;
   14833  16687  9403  3539 1001  227   43   7   1;
  133496 148329 82508 30637 8544 1909  356  57   8   1;

Indranil Ghosh, Rows 0..50, flattened
W. Y. C. Chen et al., Higher-order log-concavity in Euler's difference table, Discrete Math., 311 (2011), 2128-2134. (These are the numbers d^k_n.)
Fanja Rakotondrajao, k-Fixed-Points-Permutations, Integers: Electronic journal of combinatorial number theory 7 (2007) A36.

Columns: A000166, A000155, A000153, A000261, A001909, A001910, A176732, A176733, A176734, A176735, A176736.
Mirror image of A076731.
Cf. A002061, A003470, A008288, A023043, A023044, A023045, A068106.
Cf. A076731, A094792, A094793, A094794, A095000, A108625, A143007.
Cf. A143409, A143410, A143411, A143413.

A086764:= func< n,k | (&+[(-1)^j*Binomial(n-k,j)*Factorial(n-j): j in [0..n]])/Factorial(k) >;
[A086764(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 05 2023

T[n_,k_]:=(1/k!)*Sum[(-1)^j*Binomial[n-k,j]*(n-j)!,{j,0,n}];Flatten[Table[T[n,k],{n,0,11},{k,0,n}]] (* Indranil Ghosh, Feb 20 2017 *)
T[n_, k_] := (n!/k!) HypergeometricPFQ[{k-n},{-n},-1];
Table[T[n,k], {n,0,9}, {k,0,n}] // Flatten (* Peter Luschny, Oct 05 2017 *)

def A086764(n,k): return sum((-1)^j*binomial(n-k,j)*factorial(n-j) for j in range(n+1))//factorial(k)
flatten([[A086764(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Oct 05 2023

T(n, n) = 1; T(n+1, n) = n.
T(n+2, n) = A002061(n+1) = n^2 + n + 1; T(n+3, n) = n^3 + 3*n^2 + 5*n + 2.
T(n, k) = (k + 1)*T(n, k + 1) - T(n-1, k); T(n, n) = 1; T(n, k) = 0, if k > n.
T(n, k) = (n-1)*T(n-1, k) + (n-k-1)*T(n-2, k).
k!*T(n, k) = A068106(n, k). [corrected by Georg Fischer, Aug 13 2022]
Sum_{k>=0} T(n, k) = A003470(n+1).
T(n, k) = (1/k!) * Sum_{j>=0} (-1)^j*binomial(n-k, j)*(n-j)!. - Philippe Deléham, Jun 13 2005
From Peter Bala, Aug 14 2008: (Start)
The following remarks all relate to the array read as a square array: e.g.f for column k: exp(-y)/(1-y)^(k+1); e.g.f. for array: exp(-y)/(1-x-y) = (1 + x + x^2 + x^3 + ...) + (x + 2*x^2 + 3*x^3 + 4*x^4 + ...)*y + (1 + 3*x + 7*x^2 + 13*x^3 + ...)*y^2/2! + ... .
This table is closely connected to the constant e. The row, column and diagonal entries of this table occur in series formulas for e.
Row n for n >= 2: e = n!*(1/T(n,0) + (-1)^n*[1/(1!*T(n,0)*T(n,1)) + 1/(2!*T(n,1)*T(n,2)) + 1/(3!*T(n,2)*T(n,3)) + ...]). For example, row 3 gives e = 6*(1/2 - 1/(1!*2*11) - 1/(2!*11*32) - 1/(3!*32*71) - ...). See A095000.
Column 0: e = 2 + Sum_{n>=2} (-1)^n*n!/(T(n,0)*T(n+1,0)) = 2 + 2!/(1*2) - 3 !/(2*9) + 4!/(9*44) - ... .
Column k, k >= 1: e = (1 + 1/1! + 1/2! + ... + 1/k!) + 1/k!*Sum_{n >= 0} (-1)^n*n!/(T(n,k)*T(n+1,k)). For example, column 3 gives e = 8/3 + 1/6*(1/(1*3) - 1/(3*13) + 2/(13*71) - 6/(71*465) + ...).
Main diagonal: e = 1 + 2*(1/(1*1) - 1/(1*7) + 1/(7*71) - 1/(71*1001) + ...).
First subdiagonal: e = 8/3 + 5/(3*32) - 7/(32*465) + 9/(465*8544) - ... .
Second subdiagonal: e = 2*(1 + 2^2/(1*11) - 3^2/(11*181) + 4^2/(181*3539) - ...). See A143413.
Third subdiagonal: e = 3 - (2*3*5)/(2*53) + (3*4*7)/(53*1214) - (4*5*9)/(1214*30637) + ... .
For the corresponding results for the constants 1/e, sqrt(e) and 1/sqrt(e) see A143409, A143410 and A143411 respectively. For other arrays similarly related to constants see A008288 (for log(2)), A108625 (for zeta(2)) and A143007 (for zeta(3)). (End)
G.f. for column k is hypergeom([1,k+1],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
T(n, k) = (n!/k!)*hypergeom([k-n], [-n], -1). - Peter Luschny, Oct 05 2017

More terms from David Wasserman, Mar 28 2005
Additional comments from Zerinvary Lajos, Mar 30 2006
Edited by N. J. A. Sloane, Sep 24 2011

A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 7, 11, 9, 4, 13, 32, 53, 44, 5, 21, 71, 181, 309, 265, 6, 31, 134, 465, 1214, 2119, 1854, 7, 43, 227, 1001, 3539, 9403, 16687, 14833, 8, 57, 356, 1909, 8544, 30637, 82508, 148329, 133496, 9, 73, 527, 3333, 18089, 81901, 296967, 808393

Offset: 1

Mohammad K. Azarian, Oct 28 2002

Hanson et al. define the (n,k)-matching problem in the following realistic way. A matching question on an exam has k questions with n possible answers to choose from, each question having a unique answer. If a student guesses the answers at random, using each answer at most once, what is the probability of obtaining r of the k correct answers?
The T(n,k) represent the number of ways of obtaining exactly zero correct answers, i.e., r=0, given k questions and n possible answers, 1 <= k <= n.
T(n,k) is the number of injections from [1,...,k] into [1,...,n] with no fixed points. - David Bevan, Apr 29 2013

			0; 1,1; 2,3,2; 3,7,11,9; ...
Formatted as a square array:
0 1 2 3 4 5 6 7 8
1 3 7 13 21 31 43 57 which equals A002061
2 11 32 71 134 227 356 which equals A094792
9 53 181 465 1001 1909 which equals A094793
44 309 1214 3539 8544 which equals A094794
265 2119 9403 30637 which equals A023043
1854 16687 82508 which equals A023044
14833 148329 which equals A023045
Columns give A000255 A000153 A000261 A001909 A001910
Formatted as a triangular array (mirror image of A086764):
0
1 1
2 3 2
3 7 11 9
4 13 32 53 44
5 21 71 181 309 265
6 31 134 465 1214 2119 1854
7 43 227 1001 3539 9403 16687 14833
8 57 356 1909 8544 30637 82508 148329 133496

D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.
StackExchange, How many injective functions f:[1,...,m]->[1,...,n] have no fixed point?

Cf. A076732, A086764.

Similar to A060475.

A076731 := proc(n,k): (1/(n-k)!)*A061312(n-1,k-1) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: for n from 1 to 7 do seq(A076731(n,k), k=1..n) od; seq(seq(A076731(n,k), k=1..n), n=1..9); # Johannes W. Meijer, Jul 27 2011

t[n_,k_] := k!(n - k)! SeriesCoefficient[Exp[z(1-u+u^2z)/(1-z u)]/(1-z u), {z,0,n}, {u,0,k}]; Table[t[n,k], {n,9}, {k,n}] //TableForm (* David Bevan, Apr 29 2013 *)
t[n_, k_] := Pochhammer[n-k+1, k]*Hypergeometric1F1[-k, -n, -1]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 29 2013 *)

T(n,k) = F(n,k)*Sum{((-1)^j)*C(k, j)*(n-j)! (j=0 to k)}, where F(n,k) = 1/(n-k)! for 1 <= k <= n.
From Johannes W. Meijer, Jul 27 2011: (Start)
T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) with T(n,1) = (n-1) and T(n,n) = A000166(n) [Hanson et al.]
T(n,k) = (1/(n-k)!)*A061312(n-1,k-1)
sum(T(n,k), k=1..n) = A193464(n); row sums. (End)
T(n,k) = k!(n-k)![z^n*u^k]J(z,u) where J(z,u) = exp(z(1-u+z*u^2)/(1-z*u))/(1-z*u) is the exponential generating function of labeled digraphs consisting just of directed paths and oriented cycles (of length at least 2), z marking the vertices and u the edges; [z^n*u^k]J(z,u) is the coefficient of z^n*u^k in J(z,u). - David Bevan, Apr 29 2013

Additional comments from Zerinvary Lajos, Mar 30 2006

A061312 Triangle T[n,m]: T[n,-1] = 0; T[0,0] = 0; T[n,0] = n*n!; T[n,m] = T[n,m-1] - T[n-1,m-1].

Original entry on oeis.org

0, 1, 1, 4, 3, 2, 18, 14, 11, 9, 96, 78, 64, 53, 44, 600, 504, 426, 362, 309, 265, 4320, 3720, 3216, 2790, 2428, 2119, 1854, 35280, 30960, 27240, 24024, 21234, 18806, 16687, 14833, 322560, 287280, 256320, 229080, 205056, 183822, 165016, 148329

Offset: 0

Wouter Meeussen, Jun 06 2001

Appears in the (n,k)-matching problem A076731. [Johannes W. Meijer, Jul 27 2011]

			0,
1, 1,
4, 3, 2,
18, 14, 11, 9,
96, 78, 64, 53, 44,
600, 504, 426, 362, 309, 265,
4320, 3720, 3216, 2790, 2428, 2119, 1854,
35280, 30960, 27240, 24024, 21234, 18806, 16687, 14833,

G. C. Greubel, Rows n=0..100 of triangle, flattened

Cf. A061018.
From Johannes W. Meijer, Jul 27 2011: (Start)
Columns: A001563, A001564, A001565, A001688, A001689, A023044, A023045, A023046, A023047; A000166, A000255, A055790;
The row sums equal A193465. (End)

[[(&+[(-1)^j*Binomial(k+1,j)*Factorial(n-j+1): j in [0..k+1]]): k in [0..n]]: n in [0..20]]; // G. C. Greubel, Aug 13 2018

A061312 := proc(n,m): add(((-1)^j)*binomial(m+1,j)*(n+1-j)!, j=0..m+1) end: seq(seq(A061312(n,m), m=0..n), n=0..7); # Johannes W. Meijer, Jul 27 2011

T[n_, k_]:= Sum[(-1)^j*Binomial[k + 1, j]*(n + 1 - j)!, {j, 0, k + 1}]; Table[T[n, k], {n, 0, 100}, {k, 0, n}] // Flatten  (* G. C. Greubel, Aug 13 2018 *)

for(n=0,20, for(k=0,n, print1(sum(j=0,k+1, (-1)^j*binomial(k+1,j) *(n-j+1)!), ", "))) \\ G. C. Greubel, Aug 13 2018

T[n,m] = T[n,m-1]-T[n-1,m-1] with T[n,-1] = 0 and T[n,0] = A001563(n) = n*n!

T(n,m) = sum(((-1)^j)*binomial(m+1,j)*(n+1-j)!, j=0..m+1) [Johannes W. Meijer, Jul 27 2011]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A086764 Triangle T(n, k), read by row, related to Euler's difference table A068106 (divide column k of A068106 by k!).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A061312 Triangle T[n,m]: T[n,-1] = 0; T[0,0] = 0; T[n,0] = n*n!; T[n,m] = T[n,m-1] - T[n-1,m-1].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula