A047920 -id:A047920 - cp's OEIS frontend

A193463 Row sums of triangle A076732.

1, 1, 6, 22, 117, 705, 4972, 39916, 360105, 3606865, 39721266, 477061026, 6205806061, 86925018817, 1304396077272, 20877063837400, 355003736855697, 6391465311099681, 121460116022428510, 2429579599296960430, 51027940329395658981, 1122742916106886416001

Offset: 1

Johannes W. Meijer, Jul 27 2011

a(n)/ceiling(n/2), i.e., a(n) divided by the positive integers repeated, leads to another sequence of integer numbers [1, 1, 3, 11, 39, 235, 1243, 9979, ... ].

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

Cf. A047920, A076732.

A193463:=proc(n): add(A076732(n,k), k=1..n) end: A076732:=proc(n,k): (k/(n-k)!)*A047920(n,k) end: A047920:=proc(n,k): add(((-1)^j)*binomial(k-1,j)*(n-1-j)!, j=0..k-1) end: seq(A193463(n), n=1..22);

A000240[n_] := Subfactorial[n] - (-1)^n;
T[n_, k_] := T[n, k] = Switch[k, 1, 1, n, A000240[n], _, k*T[n - 1, k - 1] + T[n - 1, k]];
a[n_] := Sum[T[n, k], {k, 1, n}];
Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Nov 14 2023 *)

a(n) = Sum_{k=1..n} A076732(n,k).
a(n) = Sum_{k=1..n} (k/(n-k)!)*A047920(n,k).
a(n) = Sum_{k=1..n} (k/(n-k)!) * Sum_{j=0..k-1} (-1)^j*binomial(k-1,j)*(n-1-j)!.

A335391 Square array read by antidiagonals downwards: for n >= 2, T(k,n) is the number of permutations of [k+n] that differ in every position from both the identity permutation and a permutation consisting of k 1-cycles and one n-cycle.

Original entry on oeis.org

2, -1, 0, 0, 1, 2, 1, 0, 1, 4, 2, 3, 4, 7, 18, 13, 16, 19, 24, 35, 88, 80, 95, 114, 137, 168, 221, 530, 579, 672, 783, 916, 1077, 1280, 1589, 3708, 4738, 5397, 6164, 7061, 8114, 9359, 10860, 12979, 29666, 43387, 48704, 54773, 61720, 69697, 78888, 89527, 101976, 118663, 266992

Offset: 0

William P. Orrick, Jun 04 2020

The number of permutations of [k+n] that differ in every position from both the identity permutation and a permutation consisting of k 1-cycles and s cycles of lengths p_1, p_2, ... p_s, with p_j >= 2 and p_1+p_2+...+p_s = n, can be expressed as Sum T(k,p_1+-p_2+-...+-p_s), where the sum is over all 2^(s-1) choices of sign and where T(k,-n) = T(k,n) (Touchard).
The first of Touchard's formulas for T(k,n) involves A034807, the number of k-matchings of C_n (A213234 or A127677 with sign included) and A047920, the k-th differences of the factorial numbers.
A slightly different formula, due to Wyman and Moser in the k=0 case, involves A213234 and A000023.
The first column is twice A000166 (twice the number of derangements of [k]); the second column is A105926 (first differences of A000166); the third column is A331007 (with offset 2); the first row is A102761 (the ménage numbers); the second row is A000270.

			Array starts:
k/n |    0     1      2      3       4         5          6           7
-----------------------------------------------------------------------
0   |    2    -1      0      1       2        13         80         579
1   |    0     1      0      3      16        95        672        5397
2   |    2     1      4     19     114       783       6164       54773
3   |    4     7     24    137     916      7061      61720      602955
4   |   18    35    168   1077    8114     69697     671736     7172007
5   |   88   221   1280   9359   78888    749547    7913440    91815601
6   |  530  1589  10860  89527  837794   8741875  100478588  1260186153
7   | 3708 12979 101976 938181 9669196 110058257 1369406616 18475560567
There are T(1,3)=3 permutations that differ from 1234=(1)(2)(3)(4) and 1342=(1)(234) in every position: 2413, 3421, and 4123.

Mathematics Stack Exchange, Double derangement and the other unfamous kind of derangement.
J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.
Max Wyman and Leo Moser, On the problème des ménages, Canadian Journal of Mathematics, 10 (1958) 468-480.

Cf. A034807, A213234, A127677, A047920, A000023, A000166, A105926, A331007, A102761, A000270.

T := proc(n,k) local t; t := proc(n, k) option remember;
   simplify((n + k)!*hypergeom([-n], [-n - k], -1)) end:
   if k = 0 then return 2*t(n, 0) fi;
   add((-1)^j*(2*k)/(2*k-j)*binomial(2*k-j, j)*t(n, k-j), j=0 ..k) end:
seq(lprint(seq(T(n, k), k=0..7)),n=0..7); # Peter Luschny, Jul 22 2020

f(k, n) = sum(j=0, k, (-1)^j*binomial(k, j)*(n+k-j)!);
T(k, n) = if (n==0, 2*f(k, 0), sum(j=0, n, (-1)^j*(2*n)/(2*n-j)*binomial(2*n-j, j)*f(k, n-j)));
matrix(7, 7,n, k, T(n-1,k-1))
\\ Michel Marcus, Jun 26 2020

def f(k,n):
    return sum((-1)^j*binomial(k,j)*factorial(n+k-j) for j in range(0,k+1))
def T(k,n):
    if n==0:
        return 2*f(k,0)
    else:
        return sum((-1)^j*(2*n)/(2*n-j)*binomial(2*n-j,j)*f(k,n-j) for j in range(0,n+1))

T(k,0) = 2*nu(k,k), T(k,n>0) = Sum_{j=0..n} A213234(2*n,j)*nu(k,k+n-j) = Sum_{j=0..n} (-1)^j*2*n/(2*n-j)*binomial(2*n-j,j)*nu(k,k+n-j) where nu(k,k+n) = A047920(k+n,k) = Sum_{j=0..k} (-1)^j*binomial(k,j)*(k+n-j)! (Touchard).
T(k,n) = 2*cos(2*n * arccos(1/2*sqrt(x))) = 2*Chebyshev_T(2*n,sqrt(x)/2), where, after expanding in powers of x, x^m gets replaced by nu(k,k+m) (Touchard).
T(k,n) = 2*(-1)^n*Sum_{j=0..n} (-1)^j*(Product_{r=0..j} n^2-r^2)/(2*j)!*nu(k,k+j) (Touchard).
T(k,n) = 2*Integral_{x=0..oo} e^(-x^2) * (x^2-1)^k * x * ((x+sqrt(x^2-4))^(2*n)+(x-sqrt(x^2-4))^(2*n)) / 2^(2*n) dx (Touchard).
T(k,0) = 2*Sum_{j=0..h} binomial(h,j)*k(j), T(k,n) = Sum_{i>=0} A213234(n,i)*Sum_{j=0..h} binomial(h,j)*k(n-2*i+j) = Sum_{i>=0} (-1)^i*n/(n-i)*binomial(n-i,i)*Sum_{j=0..h} binomial(h,j)*k(n-2*i+j) where k(n) = A000023(n) = n! * Sum_{i=0..n} (-2)^i / i! (k=0 case due to Wyman and Moser)
T(k+1,n+1) = T(k,n)+T(k,n+1)+T(k,n+2): This holds for all integers n if one defines T(k,-n) = T(k,n).
T(k,0) = 2*A000166(k).
T(k,1) = A105926(k).
T(k,2) = A331007(k+2).
T(0,n) = A102761(n).
T(1,n) = A000270(n).

A116854 First differences of the rows in the triangle of A116853, starting with 0.

Original entry on oeis.org

1, 1, 1, 3, 1, 2, 11, 3, 4, 6, 53, 11, 14, 18, 24, 309, 53, 64, 78, 96, 120, 2119, 309, 362, 426, 504, 600, 720, 16687, 2119, 2428, 2790, 3216, 3720, 4320, 5040, 148329, 16687, 18806, 21234, 24024, 27240, 30960, 35280, 40320, 1468457, 148329, 165016, 183822, 205056, 229080, 256320, 287280, 322560, 362880

Offset: 1

Gary W. Adamson, Feb 24 2006

Row n contains the first differences of row n of A116853, starting with T(n,1) = A116853(n,1) - 0.

As in A116853, 0! = 1 is omitted here. - Georg Fischer, Mar 23 2019

			First few rows of the triangle are:
[1]    1;
[2]    1,   1;
[3]    3,   1,   2;
[4]   11,   3,   4,   6;
[5]   53,  11,  14,  18,  24;
[6]  309,  53,  64,  78,  96, 120;
[7] 2119, 309, 362, 426, 504, 600, 720;
...
For example, row 4 (11, 3, 4, 6) are first differences along row 4 of A116853: ((0), 11, 14, 18, 24).

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened

Cf. A000255, A116853.

Cf. A000142 (row sums), A033815 (central terms), A047920, A068106 (with 0!), A055790 (column k=3), A277609 (k=4), A277563 (k=5), A280425 (k=6).

a116854 n k = a116854_tabl !! (n-1) !! (k-1)
a116854_row n = a116854_tabl !! (n-1)
a116854_tabl = [1] : zipWith (:) (tail $ map head tss) tss
               where tss = a116853_tabl
-- Reinhard Zumkeller, Aug 31 2014

A116853 := proc(n,k) option remember ; if n = k then n! ; else procname(n,k+1)-procname(n-1,k) ; end if; end proc:
A116854 := proc(n,k) if k = 1 then A116853(n,1) ; else A116853(n,k) -A116853(n,k-1) ; end if; end proc:
seq(seq(A116854(n,k),k=1..n),n=1..15) ; # R. J. Mathar, Mar 27 2010

rows = 10;
rr = Range[rows]!;
dd = Table[Differences[rr, n], {n, 0, rows - 1}];
T = Array[t, {rows, rows}];
Do[Thread[Evaluate[Diagonal[T, -k+1]] = dd[[k, ;; rows-k+1]]], {k, rows}];
Table[({0}~Join~Table[t[n, k], {k, 1, n}]) // Differences, {n, 1, rows}] // Flatten (* Jean-François Alcover, Dec 21 2019 *)

T(n,k) = A116853(n,k) - A116853(n,k-1) if k>1.
T(n,1) = A116853(n,1) = A000255(n-1).
Sum_{k=1..n} T(n,1) = n! = A000142(n).

Definition made concrete and sequence extended by R. J. Mathar, Mar 27 2010

A193465 Row sums of triangle A061312.

Original entry on oeis.org

0, 2, 9, 52, 335, 2466, 20447, 189064, 1930959, 21603430, 262869959, 3457226268, 48880169351, 739429561066, 11918051268255, 203914545928336, 3691384616598047, 70491995143458894, 1416242276574905879, 29862732908481855460, 659413025994777460119

Offset: 0

Johannes W. Meijer, Jul 27 2011

a(n) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = A001563(k) for k = 0, 1, ..., n. - Michael Somos, Jun 06 2012

			2*x + 9*x^2 + 52*x^3 + 335*x^4 + 2466*x^5 + 20447*x^6 + 189064*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..445

Cf. A000166, A001563, A002467, A047920, A061312, A180191, A074909.

A193465 := proc(n): add(A061312(n,k), k=0..n) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: seq(A193465(n), n=0..20);

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 + x - (1 + x^2) / Exp[ x ]) / (1 - x)^3, {x, 0, n}]] (* Michael Somos, Jun 06 2012 *)

{a(n) = if( n<0, 0, n! * polcoeff( (1 + x - (1 + x^2) / exp(x + x * O(x^n))) / (1 - x)^3, n))} /* Michael Somos, Jun 06 2012 */

a(n) = Sum_{k=0..n} A061312(n,k).
a(n) = (n+1)*A180191(n+1).
a(n) = A002467(n+2) - (n+1)! (the game of mousetrap with n cards).
a(n) = (n+1)*(n+1)! - A000166(n+2) (rencontres numbers).
a(n) = ((n-n^3)*a(n-3) + (2*n+n^2-n^3)*a(n-2) - (1-n-2*n^2)*a(n-1))/n with a(0) = 0, a(1) = 2 and a(2) = 9.
E.g.f: (1 + x - (1 + x^2) / exp(x)) / (1 - x)^3. - Michael Somos, Jun 06 2012
a(n) = Sum_{k=0..n} C(n+1,k)*A000166(k+1) = Sum_{k=0..n} A074909(n,k)*A000166(k+1). - Anton Zakharov, Sep 26 2016
a(n) = Sum_{k=1..n+1} A047920(n+1,k). - Alois P. Heinz, Sep 01 2021

A374419 Triangle read by rows: T(n,k) = number of permutations in symmetric group S_n with an even number of non-fixed point cycles, without k<=n particular fixed points.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 4, 3, 3, 3, 3, 36, 32, 29, 26, 23, 20, 296, 260, 228, 199, 173, 150, 130, 2360, 2064, 1804, 1576, 1377, 1204, 1054, 924, 19776, 17416, 15352, 13548, 11972, 10595, 9391, 8337, 7413, 180544, 160768, 143352, 128000, 114452, 102480, 91885, 82494, 74157, 66744

Offset: 0

Julian Hatfield Iacoponi, Jul 08 2024

			Triangle array T(n,k) begins:
  n: {k<=n}
  0:  {1}
  1:  {1,       0}
  2:  {1,       0,       0}
  3:  {1,       0,       0,       0}
  4:  {4,       3,       3,       3,       3}
  5:  {36,      32,      29,      26,      23,      20}
  6:  {296,     260,     228,     199,     173,     150,     130}
  7:  {2360,    2064,    1804,    1576,    1377,    1204,    1054,   924}
T(n,0) = A373339(n) = the number of permutations in S_n without k=0 particular fixed points (i.e., not filtered, so all permutations) with an even number of cycles.
T(n,n) = A216778(n) = the number of permutations in S_n without k=n particular fixed points (i.e., filtered down to just the derangements) with an even number of cycles.
T(4,1<=k<=4) = 3 because S_4 contains 3 permutations with an even number of non-fixed point cycles without k=1,2,3 or 4 particular fixed points, namely the 3 (2,2)-cycles: (12)(34), (13)(24), (14)(23).
T(4,0) = 4 is one more than the above because it includes the permutation without k=0 particular fixed points, i.e., the identity permutation of 4 fixed points.

Cf. A047920, A062111.

Cf. A374420 (odd case), A216778 (main diagonal), A373339 (first column).

Table[Table[1/2*(Sum[(-1)^j*Binomial[k, j]*(n - j)!, {j, 0, k}] + 2^(n - k - 1)*(2 - n - k)), {k, 0, n}], {n, 0, 10}]

T(n,k) = T(n,k-1) - T(n-1,k-1) with T(n,0) = A373339(n).

T(n,k) = (1/2) * (Sum_{j=0..k} (-1)^j * binomial(k,j) * (n-j)! + 2^(n-k-1)*(2-n-k)).

A374420 Triangle T(n, k) for the number of permutations of symmetric group S_n with an odd number of non-fixed point cycles, without k <= n particular fixed points.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 5, 4, 3, 2, 20, 15, 11, 8, 6, 84, 64, 49, 38, 30, 24, 424, 340, 276, 227, 189, 159, 135, 2680, 2256, 1916, 1640, 1413, 1224, 1065, 930, 20544, 17864, 15608, 13692, 12052, 10639, 9415, 8350, 7420, 182336, 161792, 143928, 128320, 114628, 102576, 91937, 82522, 74172, 66752

Offset: 0

Julian Hatfield Iacoponi, Jul 08 2024

			Triangle array T(n,k)
n: {k<=n}
0:  {0}
1:  {0,       0}
2:  {1,       1,       1}
3:  {5,       4,       3,       2}
4:  {20,      15,      11,      8,       6}
5:  {84,      64,      49,      38,      30,      24}
6:  {424,     340,     276,     227,     189,     159,     135}
7:  {2680,    2256,    1916,    1640,    1413,    1224,    1065,   930}
T(n,0) = A373340(n) = the number of permutations in S_n without k=0 particular fixed points (i.e., not filtered, so all permutations) with an odd number of cycles.
T(n,n) = A216779(n) = the number of permutations in S_n without k=n particular fixed points (i.e., filtered down to just the derangements) with an odd number of cycles.
T(2,k) = 1 because S_2 contains 1 permutation with an odd number of non-fixed point cycles without k=0,1 or 2 particular fixed points, namely the derangement (12).
T(3,2) = 3 because S_3 contains 3 permutations with an odd number of non-fixed point cycles without k=2 particular fixed points: say, without fixed points (1) and (2), namely (12)(3), (123), (132).

Cf. A047920, A062111, A047920.

Cf. A374419 (even case), A216779 (main diagonal), A373340 (first column).

Table[Table[1/2*(Sum[(-1)^j*Binomial[k, j]*(n - j)!, {j, 0, k}] - 2^(n - k - 1)*(2 - n - k)), {k, 0, n}], {n, 0, 10}]

T(n,k) = T(n,k-1) - T(n-1,k-1) with T(n,0) = A373340(n).
T(n,k) = (1/2)*(Sum_{j=0..k} (-1)^j * binomial(k,j) * (n-j)! - 2^(n-k-1)*(2-n-k)).
T(n,k) = (A047920(n, k) + 2^(n-k-1)*(n+k-2))/2. - Peter Luschny, Jul 28 2024

cp's OEIS Frontend

A193463 Row sums of triangle A076732.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335391 Square array read by antidiagonals downwards: for n >= 2, T(k,n) is the number of permutations of [k+n] that differ in every position from both the identity permutation and a permutation consisting of k 1-cycles and one n-cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Sage

Formula

A116854 First differences of the rows in the triangle of A116853, starting with 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A193465 Row sums of triangle A061312.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A374419 Triangle read by rows: T(n,k) = number of permutations in symmetric group S_n with an even number of non-fixed point cycles, without k<=n particular fixed points.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A374420 Triangle T(n, k) for the number of permutations of symmetric group S_n with an odd number of non-fixed point cycles, without k <= n particular fixed points.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula