A000240 -id:A000240 - cp's OEIS frontend

A076732 Table T(n,k) giving number of ways of obtaining exactly one correct answer on an (n,k)-matching problem (1 <= k <= n).

1, 1, 0, 1, 2, 3, 1, 4, 9, 8, 1, 6, 21, 44, 45, 1, 8, 39, 128, 265, 264, 1, 10, 63, 284, 905, 1854, 1855, 1, 12, 93, 536, 2325, 7284, 14833, 14832, 1, 14, 129, 908, 5005, 21234, 65821, 133496, 133497, 1, 16, 171, 1424, 9545, 51264, 214459, 660064, 1334961, 1334960

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 one correct answer, i.e., r=1, given k questions and n possible answers, 1 <= k <= n.

			Triangle begins
  1;
  1,0;
  1,2,3;
  1,4,9,8;
  ...

D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.

Columns: A000012(n), 2*A001477(n-2), 3*A002061(n-2), 4*A094792(n-4), 5*A094793(n-5), 6*A094794(n-6), 7*A094795(n-7); A000240(n), A000166(n). - Johannes W. Meijer, Jul 27 2011

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(seq(A076732(n,k), k=1..n), n=1..10); # Johannes W. Meijer, Jul 27 2011

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]];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 14 2023 *)

T(n,k) = F(n,k)*Sum{((-1)^j)*C(k-1, j)*(n-1-j)! (j=0 to k-1)}, where F(n,k) = k/(n-k)!, for 1 <= k <= n.
From Johannes W. Meijer, Jul 27 2011: (Start)
T(n,k) = k*T(n-1,k-1) + T(n-1,k) with T(n,1) = 1 and T(n,n) = A000240(n). [Hanson et al.]
T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) + (1-k)*A076731(n-2,k-2) + A076731(n-1,k-1) with T(0,0) = T(n,0) = 0 and T(n,1) = 1. [Hanson et al.]
T(n,k) = k*A060475(n-1,k-1).
T(n,k) = (k/(n-k)!)*A047920(n-1,k-1).
Sum_{k=1..n} T(n,k) = A193463(n); row sums.
Sum_{k=1..n} T(n,k)/k = A003470(n-1). (End)

Edited and information added by Johannes W. Meijer, Jul 27 2011

A088436 Number of permutations in the symmetric group S_n that have exactly one transposition in their cycle decomposition.

Original entry on oeis.org

0, 1, 3, 6, 30, 225, 1575, 12180, 109620, 1100925, 12110175, 145259730, 1888376490, 26438216805, 396573252075, 6345155817000, 107867648889000, 1941617990136825, 36890741812599675, 737814829704702750

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 09 2003

nonn

			From _Bernard Schott_, Feb 19 2019: (Start)
For S_4, the six permutations that have exactly one transposition in their cycle decomposition are (12)(3)(4), (13)(2)(4), (14)(2)(3), (23)(1)(4), (24)(1)(3), (34)(1)(2).
For S_5, there are exactly 10 transpositions: (12), (13), (14), (15), (23), (24), (25), (34), (35), (45), and for each transposition, there are 3 permutations that have exactly this transposition and no other transposition in their cycle decomposition; for example, for transposition (12), these three permutations: (12)(3)(4)(5), (12)(345), (12)(354), so a(5) = 10 * 3 = 30. (End)

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 189, Exercise 19 for k=1. With (-1)^k omitted.

Muniru A Asiru, Table of n, a(n) for n = 1..440

Cf. A000266, A027616, A000240.

m:=32; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( x^2*Exp(-x^2/2)/(2*(1-x)) )); [0] cat [Factorial(n+1)*b[n]: n in [1..m-2]]; // G. C. Greubel, Feb 19 2019

G=(exp(-z^2/2)*z^2*k)/((1-z)*2^k*k!): Gser=series(G,z=0,21):
for n from 2*k to 20 do a(n)=n!*coeff(Gser,z,n): end do: # Paul Weisenhorn, Jun 02 2010

d=Exp[-x^2/2]/(1-x); Range[0,20]! CoefficientList[Series[(x^2/2! )d, {x,0,20}], x] (* Geoffrey Critzer, Nov 29 2011 *)

my(x='x+O('x^30)); concat([0], Vec(serlaplace( x^2*exp(-x^2/2)/(2*(1-x)) ))) \\ G. C. Greubel, Feb 19 2019

m = 30; T = taylor(x^2*exp(-x^2/2)/(2*(1-x)), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (1..m)] # G. C. Greubel, Feb 19 2019

a(n) = (n!/2)*Sum_{j=0..floor(n/2)-1} (-1)^j/(j!*2^j), n >= 1.
E.g.f.: x^2/(1-x)/2*exp(-x^2/2). - Vladeta Jovovic, Nov 09 2003
From Paul Weisenhorn, Jun 02 2010: (Start)
In general, for k cycles of length 2,
a(n) = n!*Sum_{j=k..floor(n/2)} (-1)^j/((j-k)!*2^j*k!).
G.f.: (exp(-z^2/2)*z^2*k)/((1-z)*2^k*k!). (End)
a(n) ~ exp(-1/2)/2 * n!. - Vaclav Kotesovec, Mar 18 2014

More terms from Wolfdieter Lang, Feb 22 2008

A176043 a(n) = (2n-1)(n-1)^(n-1).

Original entry on oeis.org

1, 1, 3, 20, 189, 2304, 34375, 606528, 12353145, 285212672, 7360989291, 210000000000, 6562168424053, 222902511206400, 8177627877990831, 322248197941182464, 13574710601806640625, 608742554432415203328, 28953409166021786746195, 1455817098785971890290688, 77158366570752229975835181

Offset: 0

Michel Lagneau, Apr 07 2010

Determinant of the symmetric n X n matrix M_n where M_n(j,k) = n for j = k, M_n(j,k) = 1 otherwise.
The eigenvalues are 2*n-1, and n-1 with multiplicity n-1. The determinant of M_n is (2n-1)*(n-1)^(n-1), where 0^0 = 1.
Number of functions from [n] to [n] with zero or one fixed point. - Olivier Gérard, Jul 31 2016

			a(5) = determinant(M_5) = 2304 where M_5 is the matrix
  [5 1 1 1 1]
  [1 5 1 1 1]
  [1 1 5 1 1]
  [1 1 1 5 1]
  [1 1 1 1 5]
The 20 functions from [3] to [3] with one or zero fixed point are:
  0fp : 211,212,231,232,311,312,331,332
  1fp : 111,112,131,132,   221,222,321,322,   213,233,313,333

Vincenzo Librandi, Table of n, a(n) for n = 0..100, (corrected by _Peter Luschny_, Jan 19 2019)

Cf. A174964.
Cf. A007778 (functions from [n] to [n] without fixed point).
Cf. A055897 (functions from [n] to [n] with one fixed point).
Cf. A212291 (bijections of [n] with zero or one fixed point).
Cf. A000166 (bijections of [n] without fixed point).
Cf. A000240 (bijections of [n] with one fixed point).

[ (2*n-1)*(n-1)^(n-1): n in [1..17] ]; // Klaus Brockhaus, Apr 19 2010

[ Determinant( SymmetricMatrix( &cat[ [ j eq k select n else 1: k in [1..j] ]: j in [1..n] ] ) ): n in [1..17] ]; // Klaus Brockhaus, Apr 19 2010

for n from 2 to 30 do:x:=(2*n-1)*(n-1)^(n-1):print(x) :od:

Join[{1},Table[(2n-1)(n-1)^(n-1),{n,2,20}]] (* Harvey P. Dale, Jan 16 2014 *)

a(n)=n--; (2*n+1)*n^n \\ Charles R Greathouse IV, Jul 31 2016

a(n) = (2*n-1)*(n-1)^(n-1).
A176043(n) = A007778(n-1) + A055897(n).
a(n+1) = n! * [x^n] exp(n*x)*(1 + 2*n*x) for n >= 0. - Stefano Spezia, May 07 2023

Edited by Klaus Brockhaus, Apr 19 2010

New interpretation and cross-references by Olivier Gérard, Jul 31 2016

A180188 Triangle read by rows: T(n,k) is the number of permutations of [n] with k circular successions (0<=k<=n-1). A circular succession in a permutation p of [n] is either a pair p(i), p(i+1), where p(i+1)=p(i)+1 or the pair p(n), p(1) if p(1)=p(n)+1.

Original entry on oeis.org

1, 0, 2, 3, 0, 3, 8, 12, 0, 4, 45, 40, 30, 0, 5, 264, 270, 120, 60, 0, 6, 1855, 1848, 945, 280, 105, 0, 7, 14832, 14840, 7392, 2520, 560, 168, 0, 8, 133497, 133488, 66780, 22176, 5670, 1008, 252, 0, 9, 1334960, 1334970, 667440, 222600, 55440, 11340, 1680, 360, 0

Offset: 1

Emeric Deutsch, Sep 06 2010

For example, p=(4,1,2,5,3) has 2 circular successions: (1,2) and (3,4).
Sum of entries in row n = n! = A000142(n).
T(n,0)=nd(n-1)=A000240(n).
T(n,1)=n(n-1)d(n-2)=A180189(n).
Sum(k*T(n,k), k>=0)=n! = A000142(n) if n>=2.

			T(3,2) = 3 because we have 123, 312, and 231.
The triangle starts:
1;
0,   2;
3,   0,  3;
8,  12,  0, 4;
45, 40, 30, 0, 5;

Alois P. Heinz, Rows n = 1..141, flattened
S. M. Tanny, Permutations and successions, J. Combinatorial Theory, Series A, 21 (1976), 196-202.

Cf. A000142, A000166, A000240, A180189.

A180188 := proc (n, k) n*binomial(n-1, k)*A000166(n-1-k) end proc:
for n to 10 do seq(A180188(n, k), k = 0 .. n-1) end do; # yields sequence in triangular form

T[n_, k_] := n*Binomial[n-1, k]*Subfactorial[n-1-k]; Table[T[n, k], {n, 0, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Feb 19 2017 *)

T(n,k) = n*C(n-1,k)*d(n-1-k), where d(j) = A000166(j) are the derangement numbers (see Prop. 1 of the Tanny reference).

T(n,k) = n*A008290(n-1,k), 0<=k=1. - R. J. Mathar, Sep 08 2013

A060836 Number of permutations of n letters where exactly 5 change position.

Original entry on oeis.org

0, 0, 0, 0, 44, 264, 924, 2464, 5544, 11088, 20328, 34848, 56628, 88088, 132132, 192192, 272272, 376992, 511632, 682176, 895356, 1158696, 1480556, 1870176, 2337720, 2894320, 3552120, 4324320, 5225220, 6270264, 7476084, 8860544, 10442784, 12243264, 14283808, 16587648

Offset: 1

Robert Goodhand (rgoodhand(AT)hotmail.com), May 12 2001

			a(8) = a(7) * 8/(8-5) = 924 * 8/3 = 2464.

Harry J. Smith, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

For changing 0, 1, 2, 3, 4, 5, n-4, n elements see A000012, A000004, A000217 (offset), A007290, A060008, A060836, A000475, A000166. Also see A000332, A008290.
Rencontre sequences are A000166 A000240 A000387 A000449 and A000475.
A diagonal of A008291.

a(n) = { 44*binomial(n, 5) } \\ Harry J. Smith, Jul 19 2009

a(n) = 44*binomial(n, 5).
a(n) = a(n-1)*n/(n-5).
G.f.: 44*x^5/(1 - x)^6. - Colin Barker, Apr 22 2012

A177265 Number of permutations of {1,2,...,n} having exactly one string of consecutive fixed points (including singletons).

Original entry on oeis.org

1, 1, 4, 12, 57, 321, 2176, 17008, 150505, 1485465, 16170036, 192384876, 2483177809, 34554278857, 515620794592, 8212685046336, 139062777326001, 2494364438359953, 47245095998005060, 942259727190907180, 19737566982241851721, 433234326593362631601

Offset: 1

Emeric Deutsch, May 25 2010

nonn

Empirically the partial sums of A000240. - Sean A. Irvine, Jul 12 2022

			a(4,1) = 12 because we have (the string of consecutive fixed points is between square brackets): [1]342, [1]423, [12]43, [1234], 3[2]41, 4[2]13, 4[23]1, 24[3]1, 41[3]2, 21[34], 231[4], and 312[4].

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

Cf. A000166, A000240.

Column A180192(n,1).

A000166:= func< n | Factorial(n)*(&+[(-1)^j/Factorial(j): j in [0..n]]) >;
A177265:= func< n | n le 2 select 1 else Self(n-1) + n*A000166(n-1) >;
[A177265(n): n in [1..30]]; // G. C. Greubel, May 19 2024

d := proc (n) options operator, arrow: factorial(n)*(sum((-1)^i/factorial(i), i = 0 .. n)) end proc: a := proc (n) options operator, arrow: 1/2-(1/2)*(-1)^n+add(d(j), j = 1 .. n) end proc; seq(a(n), n = 1 .. 22);

a[0] = 1; a[n_] := a[n] = n*a[n - 1] + (-1)^n; f[n_] := Sum[(n - k) a[n - k - 1], {k, 0, n-1}]; Array[f, 20] (* Robert G. Wilson v, Apr 01 2011 *)

def A000166(n): return factorial(n)*sum((-1)^j/factorial(j) for j in range(n+1))
def a(n): return 1 if n<3 else a(n-1) + n*A000166(n-1) # a = A177265
[a(n) for n in range(1,31)] # G. C. Greubel, May 19 2024

a(n) = (1/2)*(1 - (-1)^n) + Sum_{j=1..n} d(j), where d(j) = A000166(j) are the derangement numbers.
a(1) = 1, a(2) = 1, a(n) = a(n-1) + n*A000166(n-1). - Daniel Suteu, Jan 25 2018
Conjecture: D-finite with recurrence a(n) - (n-1)*a(n-1) - (n-1)*a(n-2) +(n-1)*a(n-3) + (n-2)*a(n-4) = 0. - R. J. Mathar, Jul 01 2022

A193463 Row sums of triangle A076732.

Original entry on oeis.org

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

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)

A368765 a(n) = n! * (1 + Sum_{k=0..n} (-1)^k * k / k!).

Original entry on oeis.org

1, 0, 2, 3, 16, 75, 456, 3185, 25488, 229383, 2293840, 25232229, 302786760, 3936227867, 55107190152, 826607852265, 13225725636256, 224837335816335, 4047072044694048, 76894368849186893, 1537887376983737880, 32295634916658495459, 710503968166486900120, 16341591267829198702737

Offset: 0

Seiichi Manyama, Jan 04 2024

nonn

Cf. A368766, A368767, A368768.

Cf. A000240, A033540.

Table[n!(1+Sum[(-1)^k k/k!,{k,0,n}]),{n,0,30}] (* Harvey P. Dale, Mar 26 2025 *)

my(N=30, x='x+O('x^N)); Vec(serlaplace((1-x*exp(-x))/(1-x)))

a(0) = 1; a(n) = n*a(n-1) + (-1)^n * n.
a(n) = n! - A000240(n).
E.g.f.: (1 - x * exp(-x)) / (1-x).
a(n) ~ (1 - exp(-1)) * n!. - Vaclav Kotesovec, Jan 13 2024

A370527 Triangle read by rows: T(n,k) = number of permutations of [n] having exactly one adjacent k-cycle. (n>=1, 1<=k<=n).

Original entry on oeis.org

1, 0, 1, 3, 2, 1, 8, 4, 2, 1, 45, 18, 6, 2, 1, 264, 99, 22, 6, 2, 1, 1855, 612, 114, 24, 6, 2, 1, 14832, 4376, 696, 118, 24, 6, 2, 1, 133497, 35620, 4923, 714, 120, 24, 6, 2, 1, 1334960, 324965, 39612, 5016, 718, 120, 24, 6, 2, 1, 14684571, 3285270, 357900, 40200, 5034, 720, 120, 24, 6, 2, 1

Offset: 1

Seiichi Manyama, Feb 21 2024

			Triangle starts:
      1;
      0,    1;
      3,    2,   1;
      8,    4,   2,   1;
     45,   18,   6,   2,  1;
    264,   99,  22,   6,  2, 1;
   1855,  612, 114,  24,  6, 2, 1;
  14832, 4376, 696, 118, 24, 6, 2, 1;

R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Columns k=1..4 give A000240, A370524, A370525, A369098.

Cf. A008290, A177248, A177250, A177252.

T(n, k) = sum(j=0, n\k-1, (-1)^j*(n-(k-1)*(j+1))!/j!);

G.f. of column k: Sum_{j>=1} j! * x^(j+k-1) / (1+x^k)^(j+1).

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

cp's OEIS Frontend

A076732 Table T(n,k) giving number of ways of obtaining exactly one correct answer on an (n,k)-matching problem (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A088436 Number of permutations in the symmetric group S_n that have exactly one transposition in their cycle decomposition.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A176043 a(n) = (2*n-1)*(n-1)^(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

Formula

Extensions

A180188 Triangle read by rows: T(n,k) is the number of permutations of [n] with k circular successions (0<=k<=n-1). A circular succession in a permutation p of [n] is either a pair p(i), p(i+1), where p(i+1)=p(i)+1 or the pair p(n), p(1) if p(1)=p(n)+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A060836 Number of permutations of n letters where exactly 5 change position.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A177265 Number of permutations of {1,2,...,n} having exactly one string of consecutive fixed points (including singletons).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A176043 a(n) = (2n-1)(n-1)^(n-1).