A000366 Genocchi numbers of second kind (A005439) divided by 2^(n-1).

1, 1, 2, 7, 38, 295, 3098, 42271, 726734, 15366679, 391888514, 11860602415, 420258768950, 17233254330343, 809698074358250, 43212125903877439, 2599512037272630686, 175079893678534943287, 13122303354155987156306

Offset

1,3

Comments

The earliest known reference to these numbers is the Dellac Marseille memoir. - Don Knuth, Jul 11 2007

According to Ira Gessel, Dellac's interpretation is the following: start with a 2n X n array of cells and consider the set D of cells in rows i through i+n of column i, for i from 1 to n. Then a(n) is the number of subsets of D containing two cells in each column and one cell in each row.

Barsky proved that for even n>1, a(n) is congruent to 3 mod 4 and for odd n>1, congruent to 2 mod 4. Gessel shows that for even n>5, a(n) is congruent to 4n-1 mod 16 and for odd n>2 that a(n)/2 is congruent to 2-n mod 8.

The entry for A005439 has further information.

The number of sequences (I_1,...,I_{n-1}) consisting of subsets of the set {1,...,n} such that the number of elements in I_k is exactly k and I_k\subset I_{k+1}\cup {k+1}. The Euler characteristics of the degenerate flag varieties of type A. - Evgeny Feigin, Dec 15 2011

Kreweras proved that for n>2, a(n) is alternatively congruent to 2 and to 7 mod 36. - Michel Marcus, Nov 06 2012

References

Anonymous, L'Intermédiaire des Mathématiciens, 7 (1900), p. 328.

Hippolyte Dellac, Problem 1735, L'Intermédiaire des Mathématiciens, Vol. 7 (1900), p. 9 ff.

E. Lemoine, L'Intermédiaire des Mathématiciens, 8 (1901), 168-169.

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

L. 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.

Links

T. D. Noe, Table of n, a(n) for n=1..100

D. Barsky, Congruences pour les nombres de Genocchi de 2e espèce, Groupe d'étude d'Analyse ultramétrique, 8e année, no. 34, 1980/81, 13 pp.

Ange Bigeni, Enumerating the symplectic Dellac configurations, arXiv:1705.03804 [math.CO], 2017.

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.

Ange Bigeni and Evgeny Feigin, Symmetric Dellac configurations, arXiv:1808.04275 [math.CO], 2018.

Hippolyte Dellac, Note sur l'élimination, méthode de parallélogramme, Annales de la Faculté des Sciences de Marseille, XI (1901), 141-164.

E. Feigin, Degenerate flag varieties and the median Genocchi numbers, arXiv:1101.1898 [math.AG], 2011.

E. Feigin, The median Genocchi numbers, Q-analogues and continued fractions, arXiv:1111.0740 [math.CO], 2011-2012.

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

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

G. Han and J. Zeng, On a q-sequence that generalizes the median Genocchi numbers, Annal Sci. Math. Quebec, 23(1999), no. 1, 63-72

G. Kreweras, Sur les permutations comptées par les nombres de Genocchi de 1-ière et 2-ième espèce, Europ. J. Comb., vol. 18, pp. 49-58, 1997.

G. Kreweras and D. Dumont, Sur les anagrammes alternés, Discrete Mathematics, Volume 211, Issues 1-3, 28 January 2000, Pages 103-110.

Formula

From Don Knuth, Jul 11 2007: (Start)

The anonymous 1900 note in Interm. Math. gives a formula that is equivalent to a nice generating function:

For example, the first four terms on the right are

1

... 2x - 2x^2 + 2x^3 + ...

........ 9x^2 - 36x^3 + ...

............... 72x^3 + ...

summing to 1 + 2x + 7x^2 + 38x^3 + ... . Of course one can replace x with 2x and get a generating function for A005439. (End)

(-2)^(2-n) * Sum_{k=0..n} C(n, k)*(1-2^(n+k+1))*B(n+k+1), with B(n) the Bernoulli numbers.

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

Sum_{n>0} a(n)x^n = Sum_{n>0} (n!^2/2^{n-1}) (x^n/((1+x)(1+3x)...(1+binomial(n,2)x))).

a(n+1) = Sum_{k=0..n} A211183(n,k). - Philippe Deléham, Feb 03 2013

G.f.: Q(0)*2 - 2, where Q(k) = 1 - x*(k+1)^2/( x*(k+1)^2 - 2/(1 - x*(k+1)^2/( x*(k+1)^2 - 2/Q(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Oct 22 2013

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

Example

G.f. = x + x^2 + 2*x^3 + 7*x^4 + 38*x^5 + 295*x^6 + 3098*x^7 + ...

Mathematica

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, 19}] (* Jean-François Alcover, Jul 18 2011, after PARI prog. *)

Prog

(PARI) a(n)=(-1/2)^(n-2)*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)); if(n<1, return(0), for(k=1, n, CF=1/(1-((n-k)\2+1)*((n-k)\2+2)/2*x*CF)); return(Vec(CF)[n]))} (Hanna)
(PARI) {a(n)=polcoeff( x*sum(m=0, n, m!*(m+1)!*(x/2)^m / prod(k=1, m, 1 + k*(k+1)*x/2 +x*O(x^n)) ), n)} \\ Paul D. Hanna, Feb 03 2013
(Sage) # Algorithm of L. Seidel (1877)
# n -> [a(1), ..., a(n)] for n >= 1.
def A000366_list(n) :
    D = [0]*(n+2); D[1] = 1
    R = []; z = 1/2; b = False
    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]
            z *= 2
        else :
            for k in range(1, h+1, 1) :  D[k] += D[k-1]
        b = not b
        if not b : R.append(D[1]/z)
    return R
A000366_list(19) # Peter Luschny, Jun 29 2012
(Python)
from math import comb
from sympy import bernoulli
def A000366(n): return (-1 if n&1 else 1)*sum(comb(n, k)*(1-(1<<n+k+1))*bernoulli(n+k+1) for k in range(n+1))>>n-2 if n>1 else 1 # Chai Wah Wu, Apr 14 2023

Crossrefs

Cf. A001469, A005439, A130168, A130169.

First column, first diagonal and row sums of triangle A014784.

Also row sums of triangle A239894.

Sequence in context: A094664 A001858 A233335 * A341381 A106211 A222034

Adjacent sequences: A000363 A000364 A000365 * A000367 A000368 A000369

Keyword

nonn,easy,nice

Author

Don Knuth, N. J. A. Sloane

Extensions

More terms from David W. Wilson, Jan 11 2001

Edited by Ralf Stephan, Apr 17 2004

Status

approved