0,3

a(n) is the number of Boolean functions of n variables whose ROBDD (reduced ordered binary decision diagram) contains exactly n branch nodes, one for each variable. - Don Knuth, Jul 11 2007

The earliest known reference for these numbers is Seidel (1877, pages 185 and 186). - Don Knuth, Jul 13 2007

Hankel transform of 1,1,2,8,... is A168488. - Paul Barry, Nov 27 2009

According to Hetyei [2017], alternation acyclic tournaments "are counted by the median Genocchi numbers"; an alternation acyclic tournament "does not contain a cycle in which descents and ascents alternate." - Danny Rorabaugh, Apr 25 2017

The n-th Genocchi number of the second kind is also the number of collapsed permutations in (2n) letters. A permutation pi of size 2n is said to be collapsed if 1+floor(k/2) <= pi^{-1}(k) <= n + floor(k/2). There are 2 collapsed permutations of size 4, namely 1234 and 1324. - Arvind Ayyer, Oct 23 2020

For any positive integer n, a(n) is (-1)^n times the permanent of the 2n X 2n matrix M with M(j, k) = floor((2*j-k-1)/(2*n)). This former conjecture of Luschny, inspired by a conjecture of Zhi-Wei Sun in A036968, was proven by Fu, Lin and Sun (see link). - Peter Luschny, Sep 07 2021 [updated Sep 24 2021]

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Muniru A Asiru, Table of n, a(n) for n = 0..270 (terms n = 1..100 from T. D. Noe)

Alan Sokal, Table of n, a(n) for n = 1..10000 [315 MB file]

Arvind Ayyer, Daniel Hathcock, and Prasad Tetali, Toppleable Permutations, Excedances and Acyclic Orientations, arXiv:2010.11236 [math.CO], 2020.

Paul Barry, Series reversion with Jacobi and Thron continued fractions, arXiv:2107.14278 [math.NT], 2021.

Beáta Bényi, A Bijection for the Boolean Numbers of Ferrers Graphs, Graphs Combin. (2022) Vol. 38, No. 10.

Ange Bigeni, The universal sl2 weight system and the Kreweras triangle, arXiv:1712.05475 [math.CO], 2017.

Ange Bigeni, Combinatorial interpretations of the Kreweras triangle in terms of subset tuples, arXiv:1712.01929 [math.CO], 2017.

Ange Bigeni, A generalization of the Kreweras triangle through the universal sl_2 weight system, Journal of Combinatorial Theory, Series A (2019) Vol. 161, 309-326.

Natasha Blitvic and Leonid Petrov, Colored interlacing triangles and Genocchi medians, arXiv:2602.04390 [math.CO], 2026. See p. 4.

Alin Bostan, Lucia Di Vizio, and Kilian Raschel, Singular walks in the quarter plane and Bernoulli numbers, arXiv:2504.13542 [math.CO], 2025. See p. 28.

Alexander Burstein, Sergi Elizalde, and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv:math/0610234 [math.CO], 2006. [Theorem 3.5]

Kwang-Wu Chen, An Interesting Lemma for Regular C-fractions, J. Int. Seq. (2003) Vol. 6, Art. 03.4.8.

Shane Chern, Parity considerations for drops in cycles on {1,2,...,n}, arXiv:2112.02074 [math.CO], 2021.

Bishal Deb and Alan D. Sokal, Classical continued fractions for some multivariate polynomials generalizing the Genocchi and median Genocchi numbers, arXiv:2212.07232 [math.CO], 2022. See pp. 14-15.

Bishal Deb, Continued fractions using a Laguerre digraph interpretation of the Foata-Zeilberger bijection and its variants, arXiv:2304.14487 [math.CO], 2023. See p. 4.

Bishal Deb, Cyclic sieving phenomena via combinatorics of continued fractions, arXiv:2508.13709 [math.CO], 2025. See p. 38.

Dominique Dumont and Jiang Zeng, Polynômes d'Euler et les fractions continues de Stieltjes-Rogers, Ramanujan J. (1998) Vol. 2, No. 3, 387-410.

Richard Ehrenborg and Einar Steingrímsson, Yet another triangle for the Genocchi numbers, European J. Combin. (2000) Vol. 21, No. 5, 593-600. MR1771988 (2001h:05008).

Sen-Peng Eu, Tung-Shan Fu, Hsin-Hao Lai, and Yuan-Hsun Lo, Gamma-positivity for a Refinement of Median Genocchi Numbers, arXiv:2103.09130 [math.CO], 2021.

Vincent Froese and Malte Renken, Terrain-like Graphs and the Median Genocchi Numbers, arXiv:2210.16281 [math.CO], 2022.

Shishuo Fu, Zhicong Lin, and Zhi-Wei Sun, Proofs of five conjectures relating permanents to combinatorial sequences, arXiv:2109.11506 [math.CO], 2021.

Shishuo Fu, Zhicong Lin, and Zhi-Wei Sun, Permanent identities, combinatorial sequences, and permutation statistics, Adv. Appl. Math. (2025), Vol. 163 Part A, Art. 102789.

Ira M. Gessel, Applications of the classical umbral calculus, arXiv:math/0108121 [math.CO], 2001.

Guo-Niu Han and Jiang Zeng, On a q-sequence that generalizes the median Genocchi numbers, Annal Sci. Math. Quebec, (1999) Vol. 23, No. 1, 63-72.

Gábor Hetyei, Alternation acyclic tournaments, arXiv:math/1704.07245 [math.CO], 2017.

Germain Kreweras, Sur les permutations comptées par les nombres de Genocchi de 1-ière et 2-ième espèce, Europ. J. Comb. (1997) Vol. 18, Issue 1, 49-58. (See also page 76.)

Alexander Lazar and Michelle L. Wachs, The Homogenized Linial Arrangement and Genocchi Numbers, arXiv:1910.07651 [math.CO], 2019.

Qiongqiong Pan and Jiang Zeng, Cycles of even-odd drop permutations and continued fractions of Genocchi numbers, arXiv:2108.03200 [math.CO], 2021.

Vincent Pilaud, Plumbing bijections, arXiv:2512.05001 [math.CO], 2025. See pp. 3, 5.

Arthur Randrianarivony and Jiang Zeng, Une famille de polynômes qui interpole plusieurs suites classiques de nombres, Adv. Appl. Math. (1996) Vol. 17, 1-26. In French.

Philipp Ludwig Seidel, Über eine einfache Entstehungsweise der Bernoulli'schen Zahlen und einiger verwandten Reihen, Sitzungsberichte der mathematisch-physikalischen Classe der königlich bayerischen Akademie der Wissenschaften zu München, volume 7 (1877), 157-187.

Zhi-Wei Sun, Arithmetic properties of some permanents, arXiv:2108.07723 [math.GM], 2021.

Gérard Viennot, Interprétations combinatoires des nombres d'Euler et de Genocchi, Seminar on Number Theory, 1981/1982, Exp. No. 11, 94 pp., Univ. Bordeaux I, Talence, 1982.

a(n) = T(n, 1) where T(1, x) = 1; T(n, x) = (x+1)*((x+1)*T(n-1, x+1)-x*T(n-1, x)); see A058942.

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

a(n) = 2 * (-1)^n * Sum_{k=0..n} binomial(n, k)*(1-2^(n+k+1))*B(n+k+1), with B(n) the Bernoulli numbers. - Ralf Stephan, Apr 17 2004

O.g.f.: 1 + x*A(x) = 1/(1-x/(1-x/(1-4*x/(1-4*x/(1-9*x/(1-9*x/(... -[(n+1)/2]^2*x/(1-...)))))))) (continued fraction). - Paul D. Hanna, Oct 07 2005

G.f.: (of 1,1,2,8,...) 1/(1-x-x^2/(1-5*x-16*x^2/(1-13*x-81*x^2/(1-25*x-256*x^2/(1-41*x-625*x^2/(1-... (continued fraction). - Paul Barry, Nov 27 2009

O.g.f.: Sum_{n>=0} n!*(n+1)! * x^(n+1) / Product_{k=1..n} (1 + k*(k+1)*x). - Paul D. Hanna, May 10 2012

From Sergei N. Gladkovskii, Dec 14 2011, Dec 27 2012, May 29 2013, Oct 09 2013, Oct 24 2013, Oct 27 2013: (Start)

Continued fractions:

G.f.: A(x) = 1/S(0), S(k) = 1 - x*(k+1)*(k+2)/(1 - x*(k+1)*(k+2)/S(k+1)).

G.f.: A(x) = -1/S(0), S(k) = 2*x*(k+1)^2 - 1 - x^2*(k+1)^2*(k+2)^2/S(k+1).

G.f.: A(x) = 1/G(0) where G(k) = 1 - x*(k+1)^2/(1 - x*(k+1)^2/G(k+1)).

G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 1/(1 - 1/(4*x*(k+1)) + 1/G(k+1))).

G.f.: Q(0)/x - 1/x, where Q(k) = 1 - x*(k+1)^2/( x*(k+1)^2 - 1/(1 - x*(k+1)^2/( x*(k+1)^2 - 1/Q(k+1)))).

G.f.: T(0)/(1-2*x), where T(k) = 1 - x^2*((k + 2)*(k+1))^2/(x^2*((k + 2)*(k+1))^2 - (1 - 2*x*k^2 - 4*x*k - 2*x)*(1 - 2*x*k^2 - 8*x*k - 8*x)/T(k+1)).

G.f.: R(0), where R(k) = 1 - x*(k+1)*(k+2)/( x*(k+1)*(k+2) - 1/(1 - x*(k+1)*(k+2)/( x*(k+1)*(k+2) - 1/R(k+1) ))). (End)

a(n) ~ 2^(2*n+4) * n^(2*n+3/2) / (exp(2*n) * Pi^(2*n+1/2)). - Vaclav Kotesovec, Oct 28 2014

Rewriting the above: a(n) ~ 4*(2*n+1)! / Pi^(2*n+1). Compare to Genocchi numbers A110501(n) = g_n ~ 4*(2*n)! / Pi^(2*n). So these are indeed like "Genocchi medians" g_{n + 1/2}. - Alan Sokal, May 13 2022

Asymptotic expansion: a(n) ~ 4*(2*n+1)! * Pi^(-(2*n+1)) * (1 + (Pi^2/16)/n + (Pi^2 (Pi^2 - 16)/512)/n^2 + (Pi^2 (Pi^4 + 384)/24576)/n^3 + (Pi^2 (Pi^6 + 96*Pi^4 + 768*Pi^2 - 12288)/1572864)/n^4 + (Pi^2 (Pi^8 + 320*Pi^6 + 12800*Pi^4 + 491520)/125829120)/n^5 + ...) --- Proof uses binomial sum for Genocchi medians in terms of Genocchi or Bernoulli numbers, combined with leading term of convergent sum (with exponentially small corrections) for the latter. Can also check against the 10000 term a-file. - Alan Sokal, May 23 2022.

a(n) = n!^2 * [x^n*y^n] exp(x)*f(x-y), where f(x) is the derivative of the Genocchi number generating function 2*x/(exp(x)+1). - Ira M. Gessel, Jul 23 2024

seq(2*(-1)^n*add(binomial(n, k)*(1 - 2^(n+k+1))*bernoulli(n+k+1), k=0..n), n=0..20); # G. C. Greubel, Oct 18 2019

a[n_]:= 2*(-1)^(n-2)*Sum[Binomial[n, k]*(1 -2^(n+k+1))*BernoulliB[n+k+1], {k, 0, n}]; Table[a[n], {n, 16}] (* Jean-François Alcover, Jul 18 2011, after PARI prog. *)

(PARI) a(n)=2*(-1)^n*sum(k=0, n, binomial(n, k)*(1-2^(n+k+1))* bernfrac(n+k+1))

(PARI) a(n)=local(CF=1+x*O(x^(n+2))); if(n<0, return(0), for(k=1, n+1, CF=1/(1-((n-k+1)\2+1)^2*x*CF)); return(Vec(CF)[n+2])) \\ Paul D. Hanna

(SageMath) # Algorithm of L. Seidel (1877)

# n -> [a(1), ..., a(n)] for n >= 1.

def A005439_list(n) :

D = []; [D.append(0) for i in (0..n+2)]; D[1] = 1

R = [] ; b = True

for i in(0..2*n-1) :

h = i//2 + 1

if b :

for k in range(h-1, 0, -1) : D[k] += D[k+1]

else :

for k in range(1, h+1, 1) : D[k] += D[k-1]

if b : R.append(D[1])

b = not b

return R

A005439_list(18) # Peter Luschny, Apr 01 2012

(SageMath) [2*(-1)^n*sum(binomial(n, k)*(1-2^(n+k+1))*bernoulli(n+k+1) for k in (0..n)) for n in (1..20)] # G. C. Greubel, Oct 18 2019

(Magma) [2*(-1)^n*(&+[Binomial(n, k)*(1-2^(n+k+1))*Bernoulli(n+k+1): k in [0..n]]): n in [1..20]]; // G. C. Greubel, Nov 28 2018

(GAP) List([1..20], n->2*(-1)^n*Sum([0..n], k->Binomial(n, k)*(1-2^(n+k+1))*Bernoulli(n+k+1))); # Muniru A Asiru, Nov 29 2018

(Python)

from math import comb

from sympy import bernoulli

def A005439(n): return (-2 if n&1 else 2)*sum(comb(n, k)*(1-(1<<n+k+1))*bernoulli(n+k+1) for k in range(n+1)) # Chai Wah Wu, Apr 14 2023

Cf. A000366, A036968, A110501, A297703.

Sequence in context: A197949 A363589 A243953 * A128814 A108208 A203199

Adjacent sequences: A005436 A005437 A005438 * A005440 A005441 A005442

nonn,nice,easy

More terms and additional comments from David W. Wilson, Jan 11 2001

a(0)=1 prepended by Peter Luschny, Apr 14 2023

approved