A155521 -id:A155521 - 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

A349980 Irregular triangle read by rows: T(n,k) is the number of n-permutations whose second-shortest cycle has length exactly k; n >= 0, 0 <= k <= max(0,n-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 6, 7, 3, 8, 24, 31, 15, 20, 30, 120, 191, 135, 40, 90, 144, 720, 1331, 945, 280, 420, 504, 840, 5040, 10655, 7077, 4480, 1260, 2688, 3360, 5760, 40320, 95887, 64197, 41552, 11340, 18144, 20160, 25920, 45360, 362880, 958879, 646965, 395360, 238140, 72576, 151200, 172800, 226800, 403200

Offset: 0

Steven Finch, Dec 07 2021

If the permutation has no second cycle, then its second-longest cycle is defined to have length 0.

			Triangle begins:
[0]     1;
[1]     1;
[2]     1,     1;
[3]     2,     1,     3;
[4]     6,     7,     3,     8;
[5]    24,    31,    15,    20,    30;
[6]   120,   191,   135,    40,    90,   144;
[7]   720,  1331,   945,   280,   420,   504,   840;
[8]  5040, 10655,  7077,  4480,  1260,  2688,  3360,  5760;
[9] 40320, 95887, 64197, 41552, 11340, 18144, 20160, 25920, 45360;
    ...

Alois P. Heinz, Rows n = 0..141, flattened
Steven Finch, Second best, Third worst, Fourth in line, arxiv:2202.07621 [math.CO], 2022.

Column 0 gives 1 together with A000142.
Column 1 gives the nonzero terms of A155521.
Row sums give A000142.
T(n,n-1) gives A059171(n) for n>=1.
Cf. A126074, A145877, A332906, A349979, A350015, A350016, A350273, A350274.

m:= infinity:
b:= proc(n, l) option remember; `if`(n=0, x^`if`(l[2]=m,
      0, l[2]), add(b(n-j, sort([l[], j])[1..2])
               *binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, n-1)))(b(n, [m$2])):
seq(T(n), n=0..10);  # Alois P. Heinz, Dec 07 2021

m = Infinity;
b[n_, l_] := b[n, l] = If[n == 0, x^If[l[[2]] == m, 0, l[[2]]], Sum[b[n-j, Sort[Append[l, j]][[1;;2]]]*Binomial[n - 1, j - 1]*(j - 1)!, {j, 1, n}]];
T[n_] := With[{p = b[n, {m, m}]}, Table[Coefficient[p, x, i], {i, 0, Max[0, n - 1]}]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)

Sum_{k=0..max(0,n-1)} k * T(n,k) = A332906(n). - Alois P. Heinz, Dec 07 2021

More terms from Alois P. Heinz, Dec 07 2021

A344262 a(0)=1; for n>0, a(n) = a(n-1)n+1 if n is even, (a(n-1)+1)n otherwise.

Original entry on oeis.org

1, 2, 5, 18, 73, 370, 2221, 15554, 124433, 1119906, 11199061, 123189682, 1478276185, 19217590418, 269046265853, 4035693987810, 64571103804961, 1097708764684354, 19758757764318373, 375416397522049106, 7508327950440982121, 157674886959260624562

Offset: 0

Amrit Awasthi, May 13 2021

nonn

			a(0) = 1;
a(1) = (a(0)+1)*1 =  (1+1)*1 =   2;
a(2) = (a(1)*2)+1 =  (2*2)+1 =   5;
a(3) = (a(2)+1)*3 =  (5+1)*3 =  18;
a(4) = (a(3)*4)+1 = (18*4)+1 =  73;
a(5) = (a(4)+1)*5 = (73+1)*5 = 370.

Cf. A033540, A073743, A090805, A137204, A155521, A344317.

a:= proc(n) a(n):= n*a(n-1) + n^(n mod 2) end: a(0):= 1:
seq(a(n), n=0..22);  # Alois P. Heinz, May 14 2021

a[1] = 1; a[n_] := a[n] = If[OddQ[n], (n - 1)*a[n - 1] + 1, (n - 1)*(a[n - 1] + 1)]; Array[a, 25] (* Amiram Eldar, May 13 2021 *)

E.g.f.: (x+1)*cosh(x)/(1-x). - Alois P. Heinz, May 14 2021
Lim_{n->infinity} a(n)/n! = 2*cosh(1) = A137204 = 2*A073743. - Amrit Awasthi, May 15 2021
a(n) = A344317(n) - A155521(n-1) for n > 0. - Alois P. Heinz, May 18 2021

A212291 Number of permutations of n elements with at most one fixed point.

Original entry on oeis.org

1, 1, 1, 5, 17, 89, 529, 3709, 29665, 266993, 2669921, 29369141, 352429681, 4581585865, 64142202097, 962133031469, 15394128503489, 261700184559329, 4710603322067905, 89501463119290213, 1790029262385804241, 37590614510101889081, 826993519222241559761

Offset: 0

Charles R Greathouse IV, Jun 17 2012

Agrees with the number of maximal matchings in the n-crown graph up to at least n = 10. - Eric W. Weisstein, Jun 14-Dec 30 2017

Alois P. Heinz, Table of n, a(n) for n = 0..400
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Cf. A000166, A000240, A155521.

b:= proc(n) b(n):= `if` (n<1, 1, n*b(n-1)+(-1)^(n)) end:
a:= n-> b(n) +n*b(n-1):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 17 2012

nn=20; Range[0,nn]! CoefficientList[Series[(1+x)Exp[-x]/(1-x),{x,0,nn}],x] (* Geoffrey Critzer, Sep 27 2013 *)
Table[(-1)^n (HypergeometricPFQ[{1, -n}, {}, 1] - n HypergeometricPFQ[{1, 1 - n}, {}, 1]), {n, 20}] (* Eric W. Weisstein, Jun 14 2017 *)
Table[2 Subfactorial[n] - (-1)^n, {n, 20}] (* Eric W. Weisstein, Dec 30 2017 *)

d(n)=if(n,round(n!/exp(1)),1)
a(n)=if(n,n*d(n-1))+d(n)

my(x='x+O('x^25)); Vec(serlaplace((1+x)/(1-x)*exp(-x))) \\ Joerg Arndt, Jun 04 2023

a(n) = 2/e * n! + O(n).
a(n) = 2*!n - (-1)^n, where !n is the subfactorial. - Eric W. Weisstein, Dec 30 2017
a(n) = A000166(n) + A000240(n).
E.g.f.: (1+x)*exp(-x)/(1-x).
From Mohammed Bouras, May 29 2023: (Start)
a(n) = n! - A155521(n-1).
A155521(n-1)/a(n) = 1/(2+3/(3+4/(4+5/(...(n-1)+n)))). (End)

A344317 a(n) = n*a(n-1) + n^(1+n mod 2), a(0) = 1.

Original entry on oeis.org

1, 2, 6, 19, 80, 401, 2412, 16885, 135088, 1215793, 12157940, 133737341, 1604848104, 20863025353, 292082354956, 4381235324341, 70099765189472, 1191696008221025, 21450528147978468, 407560034811590893, 8151200696231817880, 171175214620868175481

Offset: 0

Alois P. Heinz, May 14 2021

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A155521, A174548, A344229, A344262.

a:= proc(n) a(n):= n*a(n-1) + n^(1+n mod 2) end: a(0):= 1:
seq(a(n), n=0..23);

E.g.f.: (1+(x+1)*sinh(x))/(1-x).
a(n) = A155521(n-1) + A344262(n) for n > 0.
Lim_{n->infinity} a(n)/n! = 1+2*sinh(1) = 1+e-1/e = 1+A174548. - Amrit Awasthi, May 19 2021

A344419 a(n) = n*a(n-1) + n^(n mod 2), a(0) = 0.

Original entry on oeis.org

0, 1, 3, 12, 49, 250, 1501, 10514, 84113, 757026, 7570261, 83272882, 999274585, 12990569618, 181867974653, 2728019619810, 43648313916961, 742021336588354, 13356384058590373, 253771297113217106, 5075425942264342121, 106583944787551184562, 2344846785326126060365

Offset: 0

Alois P. Heinz, May 17 2021

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A000142, A001113, A073743, A155521, A137204, A344262, A344418.

a:= proc(n) a(n):= n*a(n-1) + n^(n mod 2) end: a(0):= 0:
seq(a(n), n=0..23);

E.g.f.: ((x+1)*cosh(x)-1)/(1-x).
a(n) = A344262(n) - n! = A344262(n) - A000142(n).
a(n) = A344418(n) - A155521(n-1) for n > 0.
Lim_{n->infinity} a(n)/n! = 2*cosh(1)-1 = 2*A073743-1 = e+1/e-1 = A137204-1. - Amrit Awasthi, May 20 2021

A161130 Sum of the differences between the largest and the smallest fixed points over all non-derangement permutations of {1,2,...,n}.

Original entry on oeis.org

0, 0, 1, 2, 13, 74, 523, 4178, 37609, 376082, 4136911, 49642922, 645357997, 9035011946, 135525179203, 2168402867234, 36862848742993, 663531277373858, 12607094270103319, 252141885402066362, 5294979593443393621

Offset: 0

Emeric Deutsch, Jul 18 2009

nonn

			a(3)=2 because the non-derangements of {1,2,3} are 1'23', 1'32, 213', and 32'1 with differences between the largest and smallest fixed points (marked) equal to 2, 0, 0, and 0, respectively.
a(4)=13 because the non-derangements of {1,2,3,4} are 1'234', 1'2'43, 1'423, 1'324', 1'342, 1'43'2, 413'2, 3124', 213'4', 42'13, 2314', 243'1, 42'3'1, 32'14', and 32'41 with differences between the largest and smallest fixed points (marked) equal to 3, 1, 0, 3, 0, 2, 0, 0, 1, 0, 0, 0, 1, 2, and 0, respectively.

Vincenzo Librandi, Table of n, a(n) for n = 0..300
E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792v1 [math.CO], 2009.

Cf. A000166, A000240, A155521, A161129

G := (exp(-x)*(1+x+x^2)-1)/(1-x)^2: Gser := series(G, x = 0, 25): seq(factorial(n)*coeff(Gser, x, n), n = 0 .. 22);

CoefficientList[Series[(E^(-x)*(1+x+x^2)-1)/(1-x)^2, {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 20 2012 *)

E.g.f.: (exp(-x) * (1+x+x^2) - 1) / (1-x)^2.
a(n) = A000166(n+1) - A155521(n).
a(n) = Sum(k*A161129(n,k), k=0..n-1).
Recurrence: (n-2)*a(n) = (n^2-2*n-1)*a(n-1) + (n-1)*n*a(n-2). - Vaclav Kotesovec, Oct 20 2012
a(n) ~ n!*n*(3/e-1). - Vaclav Kotesovec, Oct 20 2012

A208956 Triangular array read by rows. T(n,k) is the number of n-permutations that have at least k fixed points with n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 1, 1, 15, 7, 1, 1, 76, 31, 11, 1, 1, 455, 191, 56, 16, 1, 1, 3186, 1331, 407, 92, 22, 1, 1, 25487, 10655, 3235, 771, 141, 29, 1, 1, 229384, 95887, 29143, 6883, 1339, 205, 37, 1, 1, 2293839, 958879, 291394, 68914, 13264, 2176, 286, 46, 1, 1

Offset: 1

Geoffrey Critzer, Mar 03 2012

Row sums = n!

			Triangle begins:
     1;
     1,    1;
     4,    1,   1;
    15,    7,   1,  1;
    76,   31,  11,  1,  1;
   455,  191,  56, 16,  1, 1;
  3186, 1331, 407, 92, 22, 1, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A002467 (column 1), A155521 (column 2).

b:= proc(n) b(n):= `if`(n<2, 1-n, (n-1)*(b(n-1)+b(n-2))) end:
T:= (n, k)-> add(binomial(n, i)*b(n-i), i=k..n):
seq(seq(T(n,k), k=1..n), n=1..12);  # Alois P. Heinz, Apr 22 2013

f[list_] := Select[list,#>0&]; Map[f,Transpose[Table[nn=10; d=Exp[-x]/(1-x); p=1/(1-x); s=Sum[x^i/i!,{i,0,n}]; Drop[Range[0,nn]! CoefficientList[Series[p-s d, {x,0,nn}], x], 1], {n,0,9}]]]//Flatten

E.g.f. for column k: 1/(1-x) - D(x)*Sum_{i=0..k-1} x^i/i! where D(x) is the e.g.f. for A000166.

T(n,k) = Sum_{i=k..n} C(n,i)*A000166(n-i). - Alois P. Heinz, Apr 22 2013

A344418 a(n) = n*a(n-1) + n^(1+n mod 2), a(0) = 0.

Original entry on oeis.org

0, 1, 4, 13, 56, 281, 1692, 11845, 94768, 852913, 8529140, 93820541, 1125846504, 14636004553, 204904063756, 3073560956341, 49176975301472, 836008580125025, 15048154442250468, 285914934402758893, 5718298688055177880, 120084272449158735481, 2641853993881492180604

Offset: 0

Alois P. Heinz, May 17 2021

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A000142, A001113, A073742, A155521, A174548, A344317, A344419.

a:= proc(n) a(n):= n*a(n-1) + n^(1+n mod 2) end: a(0):= 0:
seq(a(n), n=0..23);

E.g.f.: (x+1)*sinh(x)/(1-x).
a(n) = A344317(n) - n! = A344317(n) - A000142(n).
a(n) = A155521(n-1) + A344419(n) for n > 0.
Lim_{n-> infinity} a(n)/n! = 2*sinh(1) = 2*A073742 = e-1/e = A174548. - Amrit Awasthi, May 20 2021

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

A349980 Irregular triangle read by rows: T(n,k) is the number of n-permutations whose second-shortest cycle has length exactly k; n >= 0, 0 <= k <= max(0,n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A344262 a(0)=1; for n>0, a(n) = a(n-1)*n+1 if n is even, (a(n-1)+1)*n otherwise.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A212291 Number of permutations of n elements with at most one fixed point.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A344317 a(n) = n*a(n-1) + n^(1+n mod 2), a(0) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A344419 a(n) = n*a(n-1) + n^(n mod 2), a(0) = 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A161130 Sum of the differences between the largest and the smallest fixed points over all non-derangement permutations of {1,2,...,n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A344262 a(0)=1; for n>0, a(n) = a(n-1)n+1 if n is even, (a(n-1)+1)n otherwise.