A085534 -id:A085534 - cp's OEIS frontend

A069895 2^a(n) divides (2n)^(2n): exponent of 2 in (2n)^(2n).

2, 8, 6, 24, 10, 24, 14, 64, 18, 40, 22, 72, 26, 56, 30, 160, 34, 72, 38, 120, 42, 88, 46, 192, 50, 104, 54, 168, 58, 120, 62, 384, 66, 136, 70, 216, 74, 152, 78, 320, 82, 168, 86, 264, 90, 184, 94, 480, 98, 200, 102, 312, 106, 216, 110, 448, 114, 232, 118, 360, 122

Offset: 1

Labos Elemer, Apr 10 2002

Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.

Cf. A001511, A007814, A085534, A091512, A249153 (partial sums).

function A069895List(length)
    a = zeros(Int, length)
    for n in 1:length a[n] = 2 * (isodd(n) ? n : n + a[div(n, 2)]) end
a end
A069895List(61) |> println # Peter Luschny, Oct 16 2021

a:= 2*n*padic[ordp](2*n, 2):
seq(a(n), n=1..61);  # Alois P. Heinz, Oct 14 2021

Table[ Part[ Flatten[ FactorInteger[n^n]], 2], {n, 2, 124, 2}]

a(n) = n<<=1; n*valuation(n,2); \\ Kevin Ryde, Oct 14 2021

def A069895(n): return n*(n&-n).bit_length()<<1 # Chai Wah Wu, Jul 11 2022

a(n) = 2*n*A001511(n).
a(n) = A007814(A085534(n)). [corrected by Kevin Ryde, Oct 15 2021]
G.f.: Sum_{k>=0} 2^(k+1)*x^2^k/(1-x^2^k)^2. - Ralf Stephan, Jun 07 2003
a(n) = 2 * A091512(n). - Alois P. Heinz, Oct 14 2021
Sum_{k=1..n} a(k) ~ 2*n^2. - Amiram Eldar, Sep 13 2024

A246070 Number A(n,k) of endofunctions f on [2n] satisfying f^k(i) = i for all i in [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 4, 1, 2, 256, 1, 3, 16, 46656, 1, 2, 50, 216, 16777216, 1, 3, 36, 1626, 4096, 10000000000, 1, 2, 56, 1440, 83736, 100000, 8916100448256, 1, 3, 16, 2688, 84624, 6026120, 2985984, 11112006825558016, 1, 2, 70, 720, 215760, 7675200, 571350096, 105413504, 18446744073709551616

Offset: 0

Alois P. Heinz, Aug 12 2014

			Square array A(n,k) begins:
0 :            1,      1,       1,       1,        1,        1, ...
1 :            4,      2,       3,       2,        3,        2, ...
2 :          256,     16,      50,      36,       56,       16, ...
3 :        46656,    216,    1626,    1440,     2688,      720, ...
4 :     16777216,   4096,   83736,   84624,   215760,    94816, ...
5 :  10000000000, 100000, 6026120, 7675200, 24899120, 11218000, ...

Alois P. Heinz, Antidiagonals n = 0..70, flattened

Columns k=0-3 give: A085534, A062971, A245141, A245959.
Main diagonal gives A246071.
Cf. A246072 (the same for permutations).

with(numtheory): with(combinat): M:=multinomial:
b:= proc(n, k, p) local l, g; l, g:= sort([divisors(p)[]]),
      proc(k, m, i, t) option remember; local d, j; d:= l[i];
        `if`(i=1, n^m, add(M(k, k-(d-t)*j, (d-t)$j)/j!*
         (d-1)!^j *M(m, m-t*j, t$j) *g(k-(d-t)*j, m-t*j,
        `if`(d-t=1, [i-1, 0], [i, t+1])[]), j=0..min(k/(d-t),
        `if`(t=0, [][], m/t))))
      end; g(k, n-k, nops(l), 0)
    end:
A:= (n, k)-> `if`(k=0, (2*n)^(2*n), b(2*n, n, k)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

multinomial[n_, k_List] := n!/Times @@ (k!); M = multinomial;
b[n_, k0_, p_] := Module[{l, g}, l = Divisors[p];
g[k_, m_, i_, t_] := g[k, m, i, t] = Module[{d, j}, d = l[[i]];
    If[i == 1, If[m == 0, 1, n^m], Sum[M[k, Join[{k - (d - t)*j},
    Table[d - t, {j}]]]/j!*If[j == 0, 1, (d - 1)!^j]*M[m, Join[{m - t*j},
    Array[t&, j]]]*g[k - (d - t)*j, m - t*j, Sequence @@
    If[d - t == 1, {i - 1, 0}, {i, t + 1}]], {j, 0, Min[k/(d - t),
    If[t == 0, {}, m/t]]}]]];
g[k0, n - k0, Length[l], 0]];
A[n_, k_] := If[k == 0, If[n == 0, 1, (2n)^(2n)], b[2*n, n, k]];
Table[A[n, d - n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz, updated Jan 01 2021 *)

A331500 a(n) = A302112(n) * n! * 2^n.

Original entry on oeis.org

1, 2, 120, 20880, 7244160, 4193683200, 3648171985920, 4450790792448000, 7251098441261875200, 15208619045076276019200, 39919072914444753469440000, 128188338317208930555828633600, 494389344738688341547326898176000, 2255096937522349816552823932846080000

Offset: 0

Washington Bomfim, Feb 02 2020

nonn

Considering the uniform model of graph evolution [Flajolet] with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at time n is P(n) = a(n)/(2n)^(2n). See the following.
Since endpoints of edges are in 1..2n, if at time n we write side by side the 2n endpoints of the included n edges, we can have any one of the (2n)^(2n) strings of length 2n in 2n characters [A085534]. A single forest G(V,E) corresponds to n! * 2^n sequences because the n edges of E(G) are exchanged for n! ways, and each permutation corresponds to 2^n sequences since each edge u-v can be in a sequence as u-v or v-u. So the number of distinct sequences of length 2n on 2n symbols formed by A302112(n) forests is a(n) = A302112(n) * n! * 2^n.
If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t), P(t) the probability of an acyclic graph in time t.
The expected value of the number of trials until the appearance of a forest at time n is ev(n) = 1/P(n) = (2*n)^(2*n) / a(n). Below is a table of n and corresponding values of ev(n) for selected values of n.
        ----------------------------------------------
n      | 1 |  10 |  100 | 1000 | 10^4 |  10^5 |  10^6 |
       |---+-----+------+------+------+-------+-------|
ev(n)  | 2 |2.63 | 3.76 | 5.48 | 8.03 | 11.79 | 17.30 |
        ----------------------------------------------
(Expected values for n >= 10^4 determined using Vaclav Kotesovec's approximation of A302112.)
To obtain a bijection h: S -> {1,2,...,n}, where S is a given set of n elements (keys) it is only necessary to determine an acyclic graph from the elements of S. Because the expected number of generated graphs is small when the number of nodes N = 2n we can use space proportional to 2n to store a graph. If n = 10^5, for example, from table above we expect to generate 11.79 graphs. For details about determination of bijections see [Havas].

			If n = 1 a(n) = 2, a(n)/(2*n)^(2*n) = 1/2. If we toss two coins we obtain one of the four ordered pairs: (H,H), (H,T), (T,H), or (T,T). The probability of a forest is 1/2, and the expected value of trials until a forest is 2.

Washington Bomfim, Experimental expected values
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
George Havas and Bohdan S. Majewski, Optimal algorithms for minimal perfect hashing

Cf. A000165, A085534, A302112, A331505.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(2*n, n)*n!*2^n:
seq(a(n), n=0..14);  # Alois P. Heinz, Jun 24 2021

Array[(-1)^#*HypergeometricPFQ[{1 - 2 #, -#}, {1, -2 #}, 4 #]*(2 #)! &, 7] (* Michael De Vlieger, Feb 07 2020, after Vaclav Kotesovec at A302112 *)

A302112(n) = { \\ From Jon E. Schoenfield's formula in A302112.
sum(j = 0, n, (-1/2)^j * binomial(n, j) * binomial(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!) / n! };
a(n) = A302112(n) * n! * 2^n;

a(n) = A302112(n) * n! * 2^n = A000165(n) * A302112(n).

Edited by Washington Bomfim, Jun 14 2021

A085529 a(n) = (2n+1)^(2n+1).

Original entry on oeis.org

1, 27, 3125, 823543, 387420489, 285311670611, 302875106592253, 437893890380859375, 827240261886336764177, 1978419655660313589123979, 5842587018385982521381124421, 20880467999847912034355032910567, 88817841970012523233890533447265625, 443426488243037769948249630619149892803

Offset: 0

N. J. A. Sloane, Jul 05 2003

nonn

a(n) == 2*n + 1 (mod 24). - Mathew Englander, Aug 16 2020

Cf. A000312, A005408, A016754, A085527, A085528, A085530, A085531, A085532, A085533, A085534, A085535.

Cf. A073009, A083648.

#^#&/@Range[1,31,2] (* Harvey P. Dale, Oct 05 2019 *)

From Mathew Englander, Aug 16 2020: (Start)
a(n) = A000312(2*n + 1).
a(n) = A016754(n)^n * (2*n + 1).
a(n) = A085527(n)^2 * (2*n + 1).
a(n) = A085528(n)^2 / (2*n + 1).
a(n) = A085530(n) * A005408(n).
a(n) = A085531(n) * A016754(n).
a(n) = A085532(n)^2 - A215265(2*n + 1).
a(n) = A085533(n) + A045531(2*n + 1).
a(n) = A085534(n+1) - A007781(2*n + 1).
a(n) = A085535(n+1) - A055869(2*n + 1).
(End)
Sum_{n>=0} 1/a(n) = (A073009 + A083648)/2 = 1.0373582538... . - Amiram Eldar, May 17 2022

A132637 Composite number C(n) raised to power C(n).

Original entry on oeis.org

256, 46656, 16777216, 387420489, 10000000000, 8916100448256, 11112006825558016, 437893890380859375, 18446744073709551616, 39346408075296537575424, 104857600000000000000000000, 5842587018385982521381124421, 341427877364219557396646723584

Offset: 1

Omar E. Pol, Aug 24 2007

nonn

Cf. A002808, A008973, A051674, A062312, A085534, A094724, A106575.

With[{nn=25},#^#&/@Complement[Range[2,nn],Prime[Range[PrimePi[nn]]]]] (* Harvey P. Dale, Aug 21 2011 *)

From Amiram Eldar, Nov 18 2020: (Start)
a(n) = A002808(n)^A002808(n).
1 + Sum_{n>=1} 1/a(n) = A094724. (End)

More terms from Harvey P. Dale, Aug 21 2011

A356568 a(n) = (4^n - 1)n^(2n).

Original entry on oeis.org

0, 3, 240, 45927, 16711680, 9990234375, 8913923665920, 11111328602485167, 18446462598732840960, 39346257980661240576303, 104857500000000000000000000, 341427795961470170556885610263, 1333735697353436921058237339402240, 6156119488473827117528057630000587767

Offset: 0

Enrique Navarrete, Sep 30 2022

If S = {1,2,3,...,2n}, a(n) is the number of functions from S to S such that at least one even number is mapped to an odd number or at least one odd number is mapped to an even number.

Note the result can be obtained as (2*n)^(2*n) - n^(2*n), which is the number of functions from S to S minus the number of functions from S to S that map each even number to an even number and each odd number to an odd number. Hence in particular a(0) = 1-1 = 0.

			For n=1, the functions are f1: (1,1),(2,1); f2: (1,2),(2,2); f3: (1,2),(2,1).

Sidney Cadot, Table of n, a(n) for n = 0..30

Cf. A062206, A085534.

a[n_] := If[n == 0, 0, (4^n - 1)*n^(2*n)] (* Sidney Cadot, Jan 05 2023 *)
Join[{0},Table[(4^n-1)n^(2n),{n,20}]] (* Harvey P. Dale, Mar 09 2025 *)

a(n) = (4^n - 1)*n^(2*n) \\ Charles R Greathouse IV, Oct 03 2022

def A356568(n): return ((1<<(m:=n<<1))-1)*n**m # Chai Wah Wu, Nov 18 2022

a(n) = A085534(n) - A062206(n).

cp's OEIS Frontend

A069895 2^a(n) divides (2n)^(2n): exponent of 2 in (2n)^(2n).

Views

Author

Keywords

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

Python

Formula

A246070 Number A(n,k) of endofunctions f on [2n] satisfying f^k(i) = i for all i in [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A331500 a(n) = A302112(n) * n! * 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A085529 a(n) = (2n+1)^(2n+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A132637 Composite number C(n) raised to power C(n).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

Extensions

A356568 a(n) = (4^n - 1)*n^(2*n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A356568 a(n) = (4^n - 1)n^(2n).