A000085 -id:A000085 - cp's OEIS frontend

A050398 Exponential reversion of sequence of involutions (A000085).

1, -2, 8, -50, 434, -4864, 66996, -1095324, 20724756, -445310616, 10708301328, -284863999848, 8304979127496, -263299784899488, 9018495674420592, -331867682445078000, 13057137391032043920, -546957850901539335840

Offset: 1

Christian G. Bower, Nov 15 1999

sign

Andrew Howroyd, Table of n, a(n) for n = 1..200
N. J. A. Sloane, Transforms
Index entries for reversions of series

Cf. A000085, A050397.

seq(n)=Vec(serlaplace(serreverse(-1 + exp(x+x^2/2 + O(x*x^n))))) \\ Andrew Howroyd, May 06 2023

E.g.f. A(x) satisfies: A(x) = log(1 + x) - A(x)^2/2. - Ilya Gutkovskiy, Apr 23 2020

A066224 Bisection of A000085.

Original entry on oeis.org

1, 4, 26, 232, 2620, 35696, 568504, 10349536, 211799312, 4809701440, 119952692896, 3257843882624, 95680443760576, 3020676745975552, 101990226254706560, 3666624057550245376, 139813029266338603264

Offset: 0

N. J. A. Sloane, Dec 19 2001

Cf. A066223.

Unsigned row sums of A130757.

a := proc(n) option remember: if n = 0 then RETURN(1) fi: if n = 1 then RETURN(1) fi: a(n-1)+(n-1)*a(n-2): end: for i from 1 to 61 by 2 do printf(`%d,`,a(i)) od: # James Sellers, Feb 11 2002

Table[n! 2^n LaguerreL[n,1/2,-1/2],{n,0,20}] (* Harvey P. Dale, Mar 11 2013 *)
Table[(-2)^n HypergeometricU[-n, 3/2, -(1/2)], {n, 0, 90}] (* Emanuele Munarini, Aug 31 2017 *)

a(n) = n!*2^n*LaguerreL(n, 1/2, -1/2). - Vladeta Jovovic, May 10 2003
a(n) = sum(n!*(2^(n-m))*binomial(n+1/2,n-m)/m!,m=0..n), n>=0.
a(n) ~ n^(n+1/2)*2^n*exp(-n+sqrt(2*n)-1/4) * (1 + 19/(24*sqrt(2*n))). - Vaclav Kotesovec, Jun 22 2013
a(n+2) - 4*(n+2)*a(n+1) + 2*(n+1)*(2*n+3)*a(n) = 0 - Emanuele Munarini, Aug 31 2017

More terms from James Sellers, Feb 11 2002

A214851 Irregular triangular array read by rows. T(n,k) is the number of n-permutations that have exactly k square roots. n >= 1, 0 <= k <= A000085(n).

Original entry on oeis.org

0, 1, 1, 0, 1, 3, 2, 0, 0, 1, 12, 8, 3, 0, 0, 0, 0, 0, 0, 0, 1, 60, 24, 35, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 450, 184, 0, 0, 85, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Geoffrey Critzer, Mar 08 2013

Row sums = n!.
Sum_{k=1...A000085(n)} T(n,k)*k = n!.
Sum_{k=1...A000085(n)} T(n,k) = A003483(n).
Column k=0 is n! - A003483(n).

			0, 1,
1, 0, 1,
3, 2, 0, 0, 1,
12, 8, 3, 0, 0, 0, 0, 0, 0, 0, 1,
60, 24, 35, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
450, 184, 0, 0, 85, 0,0,0,...,1 where the 1 is in column k=76.
T(5,2)= 35 because we have 20 5-permutations of the type (1,2,3)(4)(5) and 15 of the type (1,2)(3,4)(5).  These have 2 square roots:(1,3,2)(4)(5),(1,3,2)(4,5) and (1,3,2,4)(5),(3,1,4,2)(5) respectively.

Cf. A214849 (column k=1), A214854 (column k=2).

(* Warning: the code is very inefficient, it takes about one minute to run on a laptop computer. *) a={1,2,4,10,26}; Table[Distribution[Distribution[Table[MultiplicationTable[Permutations[m], Permute[#1,#2]&][[n]][[n]], {n,1,m!}], Range[1,m!]], Range[0,a[[m]]]], {m,1,5}] //Grid

A246552 2-adic valuation of the number of involutions of n (A000085).

Original entry on oeis.org

0, 0, 1, 2, 1, 1, 2, 3, 2, 2, 3, 4, 3, 3, 4, 5, 4, 4, 5, 6, 5, 5, 6, 7, 6, 6, 7, 8, 7, 7, 8, 9, 8, 8, 9, 10, 9, 9, 10, 11, 10, 10, 11, 12, 11, 11, 12, 13, 12, 12, 13, 14, 13, 13, 14, 15, 14, 14, 15, 16, 15, 15, 16, 17, 16, 16, 17, 18, 17, 17, 18, 19, 18, 18, 19, 20, 19, 19, 20, 21, 20, 20, 21, 22, 21, 21, 22, 23, 22, 22, 23

Offset: 0

Joerg Arndt, Sep 06 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Cf. A000085 (involutions).

Cf. A011371 (2-adic valuation of n!), A007814 (2-adic valuation of derangements (A000166)).

I:=[0, 0, 1, 2, 1]; [n le 5 select I[n] else Self(n-1)+Self(n-4)-Self(n-5): n in [1..100]]; // Vincenzo Librandi, Sep 06 2014

seq(n-2*floor(n/4)-floor((n+3)/4), n=0..100) ; # Ridouane Oudra, Dec 11 2023

CoefficientList[Series[x^2 (1 + x - x^2)/((1 - x)^2 (1 + x) (1 + x^2)), {x, 0, 100}], x] (* Vincenzo Librandi, Sep 06 2014 *)
LinearRecurrence[{1,0,0,1,-1},{0,0,1,2,1},100] (* Harvey P. Dale, Jun 13 2016 *)

N=166; x='x+O('x^N);
v=Vec(serlaplace(exp(x+x^2/2)));
vector(#v,n,valuation(v[n],2))

concat([0,0],Vec(x^2*(1+x-x^2)/((1-x)^2*(1+x)*(1+x^2))+O(x^166)))

a(n) = (3 - (-1)^n - (1+3*I)*(-I)^n - (1-I*3)*I^n + 2*n)/8 \\ Colin Barker, Oct 16 2015

a(n) = a(n-1) + a(n-4) - a(n-5).
G.f.: x^2*(1+x-x^2)/((1-x)^2*(1+x)*(1+x^2)).
a(n) = (3 - (-1)^n - (1+3*i)*(-i)^n - (1-i*3)*i^n + 2*n)/8 where i=sqrt(-1). - Colin Barker, Oct 16 2015
a(n) = (2*n+3-2*cos(n*Pi/2)-cos(n*Pi)-6*sin(n*Pi/2))/8. - Wesley Ivan Hurt, Oct 01 2017
a(n) = n - 2*floor(n/4) - floor((n+3)/4). - Ridouane Oudra, Dec 11 2023

A264737 Primes which divide some term of A000085 (numbers of involutions).

Original entry on oeis.org

2, 5, 13, 19, 23, 29, 31, 43, 53, 59, 61, 67, 73, 79, 83, 89, 97, 103, 131, 137, 151, 157, 163, 173, 179, 181, 191, 197, 199, 211, 229, 233, 239, 241, 281, 293, 307, 317, 347, 359, 367, 373, 379, 389, 397, 409, 419, 421, 431, 433, 443, 449, 457, 461, 463, 479, 487, 491, 499

Offset: 1

David Eppstein, Nov 22 2015

Essentially the same as A245177. - R. J. Mathar, Nov 25 2015

			23 divides A000085(11) = 35696 = 2^4 * 23 * 97, so it appears in this set. The sequence A000085 mod 3 cycles: 1,1,2,1,1,2,..., so the prime factor 3 does not appear in this set.

Robert Israel, Table of n, a(n) for n = 1..4000

Cf. A000085. Essentially a duplicate of A245177.

filter:= proc(p) local a,b,c,n,R;
  if not isprime(p) then return false fi;
  a:= 1; b:= 1;
  R[1,1,1]:= 1;
  for n from 2 do
    c:= a + (n-1)*b mod p;
    if c = 0 then return true fi;
    b:= a; a:= c;
    if R[a,b,(n mod p)] = 1 then return false fi;
    R[a,b,(n mod p)]:= 1;
  od:
end proc:
select(filter, [2,seq(i,i=3..1000,2)]); # Robert Israel, Nov 22 2015

A85 = DifferenceRoot[Function[{y, n}, {(-n - 1) y[n] - y[n + 1] + y[n + 2] == 0, y[1] == 1, y[2] == 2}]];
selQ[p_] := AnyTrue[Range[p - 1], Divisible[A85[#], p]&]; selQ[2] = True;
Reap[For[p = 2, p < 1000, p = NextPrime[p], If[selQ[p], Print[p]; Sow[p] ]]][[2, 1]] (* Jean-François Alcover, Jul 28 2020 *)

Any individual prime p is easily tested for membership in this set by iterating the recurrence for A000085 mod p, T(n) = T(n-1) + (n-1)T(n-2) modulo p, until either finding a value divisible by p or entering a cycle.

A306009 Inverse Weigh transform of A000085.

Original entry on oeis.org

1, 2, 2, 7, 14, 43, 130, 446, 1544, 5773, 22170, 89356, 370198, 1591379, 7020014, 31922981, 148679262, 710828036, 3474337098, 17379964444, 88739068866, 462670294023, 2458638559154, 13317850411827, 73432568553848, 412120738922369, 2351720323257872

Offset: 1

Alois P. Heinz, Jun 16 2018

nonn

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

Cf. A000085, A293114.

g:= proc(n) option remember;
      `if`(n<2, 1, g(n-1)+(n-1)*g(n-2))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= proc(n) option remember; g(n)-b(n, n-1) end:
seq(a(n), n=1..30);

g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[a[i], j]*b[n - i*j, i - 1], {j, 0, n/i}]]];
a[n_] := a[n] = g[n] - b[n, n - 1];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Oct 27 2021, after Alois P. Heinz *)

Product_{k>=1} (1+x^k)^a(k) = Sum_{n>=0} A000085(n) * x^n.

A007868 Number of inverse pairs of elements in symmetric group S_n, or pairs of total orders on n nodes (average of A000085 and A000142).

Original entry on oeis.org

1, 1, 2, 5, 17, 73, 398, 2636, 20542, 182750, 1819148, 19976248, 239570876, 3113794652, 43590340840, 653842358768, 10461418047368, 177843819947656, 3201187351520912, 60822552609266720, 1216451015967652048, 25545471145831066448, 562000364198246159456

Offset: 0

Peter J. Cameron

T. D. Noe, Table of n, a(n) for n=0..100
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

(Table[n!, {n, 0, 20}] + Range[0, 20]! CoefficientList[Series[Exp[x + x^2/2], {x, 0, 20}],x])/2  (* Geoffrey Critzer, Nov 07 2011 *)

E.g.f.: 1/2*(1-1/(x-1)*exp(-(1/2*x+1)*x))*exp((1/2*x+1)*x).

a(n) ~ n! / 2. - Vaclav Kotesovec, Feb 15 2015

A152736 Triangle read by rows: M*Q, where M = an infinite lower triangular matrix with A140456 in every column: (1, 1, 1, 3, 7, 23, 71, ...) and Q = a matrix with A000085 as the main diagonal the rest zeros.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 1, 2, 4, 7, 3, 2, 4, 10, 23, 7, 6, 4, 10, 26, 71, 23, 14, 12, 10, 26, 76, 255, 71, 46, 28, 30, 26, 76, 232, 911, 255, 142, 92, 70, 78, 76, 232, 764, 3535, 911, 510, 284, 230, 182, 228, 232, 764, 2620

Offset: 1

Gary W. Adamson, Dec 12 2008

An eigentriangle.
Row sums = A000085 starting with offset 1.
Sum of n-th row terms = rightmost term of next row.

			First few rows of the triangle:
      1;
      1,    1;
      1,    1,    2;
      3,    1,    2,    4;
      7,    3,    2,    4,  10;
     23,    7,    6,    4,  10,  26;
     71,   23,   14,   12,  10,  26,  76;
    255,   71,   46,   28,  30,  26,  76, 232;
    911,  255,  142,   92,  70,  78,  76, 232, 764;
   3535,  911,  510,  284, 230, 182, 228, 232, 764, 2620;
  13903, 3535, 1822, 1020, 710, 598, 532, 696, 764, 2620, 9496;
  ...
Row r = (3, 1, 2, 4) = (3*1, 1*1, 1*2, 1*4) = termwise products of (3, 1, 1, 1) and (1, 1, 2, 4), where A000085 = (1, 1, 2, 4, 10, 26, 76, ...).

Cf. A000085, A140456.

A172395 G.f. satisfies: A(x) = G(x/A(x)) where o.g.f. G(x) = A(xG(x)) = Sum_{n>=0} A000085(n)x^n.

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 4, 0, 27, 0, 248, 0, 2830, 0, 38232, 0, 593859, 0, 10401712, 0, 202601898, 0, 4342263000, 0, 101551822350, 0, 2573779506192, 0, 70282204726396, 0, 2057490936366320, 0, 64291032462761955, 0, 2136017303903513184, 0

Offset: 0

Paul D. Hanna, Feb 06 2010

nonn

The e.g.f. of A000085 is exp(x+x^2/2) = Sum_{n>=0} A000085(n)*x^n/n!, where A000085(n) is the number of self-inverse permutations on n letters.

			G.f.: A(x) = 1 + x + x^2 + x^4 + 4*x^6 + 27*x^8 + 248*x^10 +...
where G(x) = A(x*G(x)) is the o.g.f. of A000085:
G(x) = 1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 26*x^5 + 76*x^6 + 232*x^7 +...
while the e.g.f. of A000085 is given by:
exp(x+x^2/2) = 1 + x + 2*x^2/2! + 4*x^3/3! + 10*x^4/4! + 26*x^5/5! +...

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

Cf. A000085, A000699, A172394 (variant).

{a(n)=local(G=sum(m=0,n,m!*polcoeff(exp(x+x^2/2+x*O(x^m)),m)*x^m)+x*O(x^n));polcoeff(x/serreverse(x*G),n)}

a(2n-2) = A000699(n), the number of irreducible diagrams with 2n nodes, for n>=1.

a(2n-1) = 0 for n>=2, with a(1)=1.

A188287 Convolution of A000085 with itself.

Original entry on oeis.org

1, 2, 5, 12, 32, 88, 260, 800, 2604, 8824, 31340, 115568, 443760, 1763456, 7260256, 30835712, 135124496, 609027360, 2822461648, 13417923008, 65401203584, 326242088064, 1664539966400, 8674167861760, 46140838036160, 250248380068736, 1383064482739392, 7782094359642880

Offset: 0

Groux Roland, Mar 26 2011

nonn

a(n) is also the moment of order n for the measure of density: x*exp(-(x-1)^2)*erfi((x-1)/sqrt(2)) over the interval -infinity..infinity, with erfi the Imaginary Error Function.

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A000085, A034430.

seq(n)={Vec(serlaplace(exp(x + x^2/2 + O(x*x^n)))^2)} \\ Andrew Howroyd, Nov 04 2019

a(n) = Sum_{k=0..floor(n/2)} binomial(n+1,2*k+1)*A034430(k).

Terms a(20) and beyond from Andrew Howroyd, Nov 04 2019

cp's OEIS Frontend

A050398 Exponential reversion of sequence of involutions (A000085).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A066224 Bisection of A000085.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A214851 Irregular triangular array read by rows. T(n,k) is the number of n-permutations that have exactly k square roots. n >= 1, 0 <= k <= A000085(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A246552 2-adic valuation of the number of involutions of n (A000085).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

A264737 Primes which divide some term of A000085 (numbers of involutions).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A306009 Inverse Weigh transform of A000085.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A007868 Number of inverse pairs of elements in symmetric group S_n, or pairs of total orders on n nodes (average of A000085 and A000142).

Views

Author

Keywords

Links

Programs

Mathematica

Formula

A152736 Triangle read by rows: M*Q, where M = an infinite lower triangular matrix with A140456 in every column: (1, 1, 1, 3, 7, 23, 71, ...) and Q = a matrix with A000085 as the main diagonal the rest zeros.

Views

Author

Keywords

Comments

Examples

Crossrefs

A172395 G.f. satisfies: A(x) = G(x/A(x)) where o.g.f. G(x) = A(xG(x)) = Sum_{n>=0} A000085(n)x^n.