A176733 -id:A176733 - cp's OEIS frontend

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

Offset: 0

N. J. A. Sloane

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

			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

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 176, Table 5.3. [From Emeric Deutsch, Apr 21 2009]

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

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

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

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
# second Maple program:
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

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

row(n) = vector(n+1, k, k--; sum(j=0, n, (-1)^j * binomial(k, j)*(n-j)!)); \\ Michel Marcus, Sep 04 2021

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

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

A176734 a(n) = (n+7)a(n-1) + (n-1)a(n-2), a(-1)=0, a(0)=1.

Original entry on oeis.org

1, 8, 73, 746, 8425, 104084, 1395217, 20157542, 312129649, 5155334720, 90449857081, 1679650774658, 32908313146393, 678322072223756, 14672571587601985, 332293083938376254, 7862829504396683617, 194024597448534426872, 4984283037788104293289, 133083801736564331309210

Offset: 0

Wolfdieter Lang, Jul 14 2010

a(n) enumerates the possibilities for distributing n beads, n>=1, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k=8 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute a factor 1 in the counting, e.g., a(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads. This produces for a(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A049388(n) = (n+7)!/7!}. See the necklaces and cords problem comment in A000153. Therefore the recurrence with inputs holds. 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).

			Necklaces and 8 cords problem. For n=4 one considers the following weak 2 part compositions of 4: (4,0), (3,1), (2,2), and (0,4), where (1,3) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively !4*1,binomial(4,3)*!3*c8(1), (binomial(4,2)*!2)*c8(2), and 1*c8(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c8(n):=A049388(n) numbers for the pure 8-cord problem (see the remark on the e.g.f. for the k cords problem in A000153; here for k=8: 1/(1-x)^8). This adds up as 9 + 4*2*8 + (6*1)*72 + 7920 = 8425 = a(4).

Cf. A176733 (necklaces and k=7 cords).

nxt[{n_,a_,b_}]:={n+1,b,(n+8)b+n*a}; Transpose[NestList[nxt,{1,1,8},20]][[2]] (* Harvey P. Dale, Mar 19 2013 *)
Table[(-1)^n HypergeometricPFQ[{9, -n}, {}, 1], {n, 0, 20}] (* Benedict W. J. Irwin, May 29 2016 *)

E.g.f. (exp(-x)/(1-x))*(1/(1-x)^8) = exp(-x)/(1-x)^9, equivalent to the given recurrence.
a(n) = A086764(n+8,8).
a(n) = (-1)^n*2F0(9,-n;;1). - Benedict W. J. Irwin, May 29 2016

A247490 Square array read by antidiagonals: A(k, n) = (-1)^(n+1)* hypergeom([k, -n+1], [], 1) for n>0 and A(k,0) = 0 (n>=0, k>=1).

Original entry on oeis.org

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

Offset: 0

Peter Luschny, Sep 20 2014

			k\n
[1], 0, 1, 0,  1,   2,    9,   44,    265,      1854, ...  A000166
[2], 0, 1, 1,  3,  11,   53,   309,  2119,     16687, ...  A000255
[3], 0, 1, 2,  7,  32,  181,  1214,  9403,     82508, ...  A000153
[4], 0, 1, 3, 13,  71,  465,  3539,  30637,   296967, ...  A000261
[5], 0, 1, 4, 21, 134, 1001,  8544,  81901,   870274, ...  A001909
[6], 0, 1, 5, 31, 227, 1909, 18089, 190435,  2203319, ...  A001910
[7], 0, 1, 6, 43, 356, 3333, 34754, 398959,  4996032, ...  A176732
[8], 0, 1, 7, 57, 527, 5441, 61959, 770713, 10391023, ...  A176733
The referenced sequences may have a different offset or other small deviations.

Cf. A000166, A000255, A000153, A000261, A001909, A001910, A176732 - A176736.

A := (k,n) -> `if`(n<2,n,hypergeom([k,-n+1],[],1)*(-1)^(n+1));
seq(print(seq(round(evalf(A(k,n),100)), n=0..8)), k=1..8);

from mpmath import mp, hyp2f0
mp.dps = 25; mp.pretty = True
def A247490(k, n):
    if n < 2: return n
    if k == 1 and n == 2: return 0  # (failed to converge)
    return int((-1)^(n+1)*hyp2f0(k, -n+1, 1))
for k in (1..8): print([k], [A247490(k, n) for n in (0..8)])

A284204 Eighth column of Euler's difference table in A068106.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 5040, 35280, 287280, 2656080, 27422640, 312273360, 3884393520, 52370755920, 760381337520, 11824686110160, 196038409800240, 3450899827705680, 64272619406504880, 1262590566656060880, 26087355385405781040, 565510731026706254160

Offset: 1

Enrique Navarrete, Mar 22 2017

nonn

For n >= 8, this is the number of permutations of [n] that avoid substrings j(j+7), 1 <= j <= n-7.

			a(11)=27422640 since this is the number of permutations in S11 that avoid substrings {18,29,3(10),4(11)}.

Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.

Also 5040 times A176733.

Cf. A068106.

With[{k = 8}, ConstantArray[0, k - 2]~Join~Table[Sum[(-1)^j*Binomial[n - (k - 1), j] (n - j)!, {j, 0, n - (k - 1)}], {n, k - 1, k + 12}]] (* Michael De Vlieger, Mar 26 2017 *)

For n>=8: a(n) = Sum_{j=0..n-7} (-1)^j*binomial(n-7,j)*(n-j)!.

Note a(n)/n! ~ 1/e.

A336246 Array read by upwards antidiagonals: T(n,k) is the number of ways to place n persons on different seats such that each person number p, 1 <= p <= n, differs from the seat number s(p), 1 <= s(p) <= n+k, k >= 0.

Original entry on oeis.org

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

Offset: 1

Gerhard Kirchner, Jul 19 2020

T(n,0) = !n (subfactorial) is the number of derangements or fixed-point-free permutations, see A000166(n) below: n persons are placed on n seats such that no person sits on a seat with the same number. The generalization of a permutation is a variation (n persons and n+k seats such that k seats remain free). In this sense, T(n,k) is the number of fixed-point-free variations. I am rather sure that such variations have been examined, but I cannot find a reference.
Some subsequences T(n,k) with k=const:
T(n,0) = A000166(n);   T(n,1) = A000255(n);   T(n,2) = A000153(n-1);
T(n,3) = A000261(n-1); T(n,4) = A001909(n-3); T(n,5) = A001910(n-4);
T(n,6) = A176732(n);   T(n,7) = A176733(n);   T(n,8) = A176734(n);
T(n,9) = A176735(n);   T(n,10) = A176736(n).

			For k=1, the n-tuples of seat numbers are:
- for n=1: 2 => T(1,1) = 1.
- for n=2: 21, 23, 31 => T(2,1) = 3,
     21: person 1 sits on seat 2 and vice versa.
     A counterexample is 13 because person 1 would sit on seat 1.
- for n=3: 214,231,234,241,312,314,341,342,412,431,432 => T(3,1) = 11.
Array begins:
   0   1    2    3    4 ...
   1   3    7   13   21 ...
   2  11   32   71  134 ...
   9  53  181  465 1001 ...
  44 309 1214 3539 8544 ...
  .. ... .... .... ....

Gerhard Kirchner, Fixed-point-free variations

Cf. A000166, A000255, A000153, A000261, A001909, A001910, A176732, A176733, A176734, A176735, A176736.

block(nr: 0, k: -1,  mmax: 55,
    /*First mmax terms are returned, recurrence used*/
   a: makelist(0, n, 1, mmax),
   while nr

block(n: 1, k: 0,  mmax: 55,
    /*First mmax terms are returned, explicit formula used*/
   a: makelist(0, n, 1, mmax),
   for m from 1 thru mmax do (su: 0,
     for r from 0 thru n do su: su+(-1)^r*binomial(n,r)*(n+k-r)!/k!,
     a[m]: su, if n=1 then (n: k+2, k: 0) else (n: n-1, k: k+1)),
  return(a));

T(n,k) = (n+k-1)*T(n-1,k) + (n-1)*T(n-2,k) for n >= 2, k >= 0 with T(0,k)=1 and T(1,k)=k.
For n=0, there is one empty variation. T(0,k) is used for the recurrence only, not in the table. For n=1, the person can be placed on seat number 2..k+1 (if k > 0).
You also find the recurrence in the formula section of A000166 (k=0) and in the name section of the other sequences listed above (1 <= k <= 10). Some sequences have a different offset.
T(n,k) = Sum_{r=0..n} (-1)^r*binomial(n,r)*(n+k-r)!/k!.
Proofs see link.

cp's OEIS Frontend

A047920 Triangular array formed from successive differences of factorial numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

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

A176734 a(n) = (n+7)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A247490 Square array read by antidiagonals: A(k, n) = (-1)^(n+1)* hypergeom([k, -n+1], [], 1) for n>0 and A(k,0) = 0 (n>=0, k>=1).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Sage

A284204 Eighth column of Euler's difference table in A068106.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A336246 Array read by upwards antidiagonals: T(n,k) is the number of ways to place n persons on different seats such that each person number p, 1 <= p <= n, differs from the seat number s(p), 1 <= s(p) <= n+k, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maxima

Maxima

Formula

A176734 a(n) = (n+7)a(n-1) + (n-1)a(n-2), a(-1)=0, a(0)=1.