|
%I M2908 N1169 #230 Mar 18 2023 03:42:03
%S 1,1,3,11,57,361,2763,24611,250737,2873041,36581523,512343611,
%T 7828053417,129570724921,2309644635483,44110959165011,898621108880097,
%U 19450718635716001,445777636063460643,10784052561125704811,274613643571568682777,7342627959965776406281
%N Generalized Euler numbers, or Springer numbers.
%C From _Peter Bala_, Feb 02 2011: (Start)
%C The Springer numbers were originally considered by Glaisher (see references). They are a type B analog of the zigzag numbers A000111 for the group of signed permutations.
%C COMBINATORIAL INTERPRETATIONS
%C Several combinatorial interpretations of the Springer numbers are known:
%C 1) a(n) gives the number of Weyl chambers in the principal Springer cone of the Coxeter group B_n of symmetries of an n dimensional cube. An example can be found in [Arnold - The Calculus of snakes...].
%C 2) Arnold found an alternative combinatorial interpretation of the Springer numbers in terms of snakes. Snakes are a generalization of alternating permutations to the group of signed permutations. A signed permutation is a sequence (x_1,x_2,...,x_n) of integers such that {|x_1|,|x_2|,...,|x_n|} = {1,2,...,n}. They form a group, the hyperoctahedral group of order 2^n*n! = A000165(n), isomorphic to the group of symmetries of the n dimensional cube. A snake of type B_n is a signed permutation (x_1,x_2,...,x_n) such that 0 < x_1 > x_2 < ... x_n. For example, (3,-4,-2,-5,1,-6) is a snake of type B_6. a(n) gives the number of snakes of type B_n [Arnold]. The cases n=2 and n=3 are given in the Example section below.
%C 3) The Springer numbers also arise in the study of the critical points of functions; they count the topological types of odd functions with 2*n critical values [Arnold, Theorem 35].
%C 4) Let F_n be the set of plane rooted forests satisfying the following conditions:
%C ... each root has exactly one child, and each of the other internal nodes has exactly two (ordered) children,
%C ... there are n nodes labeled by integers from 1 to n, but some leaves can be non-labeled (these are called empty leaves), and labels are increasing from each root down to the leaves. Then a(n) equals the cardinality of F_n. An example and proof are given in [Verges, Theorem 4.5].
%C OTHER APPEARANCES OF THE SPRINGER NUMBERS
%C 1) Hoffman has given a connection between Springer numbers, snakes and the successive derivatives of the secant and tangent functions.
%C 2) For integer N the quarter Gauss sums Q(N) are defined by ... Q(N) := Sum_{r = 0..floor(N/4)} exp(2*Pi*I*r^2/N). In the cases N = 1 (mod 4) and N = 3 (mod 4) an asymptotic series for Q(N) as N -> inf that involves the Springer numbers has been given by Evans et al., see 1.32 and 1.33.
%C For a sequence of polynomials related to the Springer numbers see A185417. For a table to recursively compute the Springer numbers see A185418.
%C (End)
%C Similar to the way in which the signed Euler numbers A122045 are 2^n times the value of the Euler polynomials at 1/2, the generalized signed Euler numbers A188458 can be seen as 2^n times the value of generalized Euler polynomials at 1/2. These are the Swiss-Knife polynomials A153641. A recursive definition of these polynomials is given in A081658. - _Peter Luschny_, Jul 19 2012
%C a(n) is the number of reverse-complementary updown permutations of [2n]. For example, the updown permutation 241635 is reverse-complementary because its complement is 536142, which is the same as its reverse, and a(2)=3 counts 1324, 2413, 3412. - _David Callan_, Nov 29 2012
%C a(n) = |2^n G(n,1/2;-1)|, a specialization of the Appell sequence of polynomials umbrally formed by G(n,x;t) = (G(.,0;t) + x)^n from the Grassmann polynomials G(n,0;t) of A046802 enumerating the cells of the positive Grassmannians. - _Tom Copeland_, Oct 14 2015
%C Named "Springer numbers" after the Dutch mathematician Tonny Albert Springer (1926-2011). - _Amiram Eldar_, Jun 13 2021
%D V. I. Arnold, Springer numbers and Morsification spaces. J. Algebraic Geom., Vol. 1, No. 2 (1992), pp. 197-214.
%D J. W. L. Glaisher, "On the coefficients in the expansions of cos x/cos 2x and sin x/cos 2x", Quart. J. Pure and Applied Math., Vol. 45 (1914), pp. 187-222.
%D J. W. L. Glaisher, On the Bernoullian function, Q. J. Pure Appl. Math., Vol. 29 (1898), pp. 1-168.
%D Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Tonny Albert Springer, Remarks on a combinatorial problem, Nieuw Arch. Wisk., Vol. 19, No. 3 (1971), pp. 30-36.
%H T. D. Noe, <a href="/A001586/b001586.txt">Table of n, a(n) for n=0..100</a>
%H Vladimir Igorevich Arnol'd, <a href="http://mi.mathnet.ru/eng/umn4470">The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups</a>, Uspekhi Mat. nauk., Vol. 47, No. 1 (1992), pp. 3-45; <a href="http://iopscience.iop.org/article/10.1070/RM1992v047n01ABEH000861/pdf">English version</a>, Russian Math. Surveys, Vol. 47 (1992), pp. 1-51.
%H Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo and Matteo Silimbani, <a href="https://doi.org/10.26493/1855-3974.1679.ad3">Ascending runs in permutations and valued Dyck paths</a>, Ars Mathematica Contemporanea, Vol. 16, No. 2 (2019), pp. 445-463.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry3/barry84r2.html">A Note on Three Families of Orthogonal Polynomials defined by Circular Functions, and Their Moment Sequences</a>, Journal of Integer Sequences, Vol. 15 (2012), Article 12.7.2.
%H Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H William Y. C. Chen, Neil J. Y. Fan and Jeffrey Y. T. Jia, <a href="http://arxiv.org/abs/1009.2233">Labeled Ballot Paths and the Springer Numbers</a>, arXiv:1009.2233 [math.CO], Sep 12 2010. [From _Jonathan Vos Post_, Sep 13 2010]
%H Suyoung Choi, Boram Park and Hanchul Park, <a href="http://arxiv.org/abs/1602.05406">The Betti numbers of real toric varieties associated to Weyl chambers of type B</a>, arXiv preprint arXiv:1602.05406 [math.AT], 2016.
%H Chak-On Chow and Shi-Mei Ma, <a href="http://dx.doi.org/10.1016/j.disc.2014.01.015">Counting signed permutations by their alternating runs</a>, Discrete Mathematics, Vol. 323 (28 May 2014), pp. 49-57.
%H D. Dumont, <a href="http://dx.doi.org/10.1006/aama.1995.1014">Further triangles of Seidel-Arnold type and continued fractions related to Euler and Springer numbers</a> Adv. Appl. Math., Vol. 16, No. 3 (1995), pp. 275-296.
%H Ronald Evans, Marvin Minei and Bennet Yee, <a href="http://math.ucsd.edu/~revans/IncompleteGaussSums.pdf">Incomplete higher order Gauss sums</a>, J. Math. Anal. Appl., Vol. 281, No. 2 (2003), pp. 454-476. See 1.32 and 1.33.
%H Dominique Foata and Guo-Niu Han, <a href="https://arxiv.org/abs/1304.2486">Multivariable Tangent and Secant q-derivative Polynomials</a>, arXiv:1304.2486 [math.CO], 2013; <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub119derivative.pdf">alternative link</a>.
%H J. W. L. Glaisher, <a href="https://doi.org/10.1112/plms/s1-31.1.216">On a set of coefficients analogous to the Eulerian numbers</a>, Proc. London Math. Soc., 31 (1899), 216-235.
%H Christopher R. H. Hanusa, Alejandro H. Morales, and Martha Yip, <a href="https://arxiv.org/abs/2107.07326">Column convex matrices, G-cyclic orders, and flow polytopes</a>, arXiv:2107.07326 [math.CO], 2021.
%H Michael E. Hoffman, <a href="https://doi.org/10.37236/1453">Derivative Polynomials, Euler Polynomials, and Associated Integer Sequences</a>, The Electronic Journal of Combinatorics, Vol. 6 (1999), #R21 (see Th. 3.1).
%H Matthieu Josuat-Vergès, <a href="http://arxiv.org/abs/1011.0929">Enumeration of snakes and cycle-alternating permutations</a>, arXiv:1011.0929 [math.CO], 2010.
%H Matthieu Josuat-Vergès, J.-C. Novelli and J.-Y. Thibon, <a href="http://arxiv.org/abs/1110.5272">The algebraic combinatorics of snakes</a>, arXiv preprint arXiv:1110.5272 [math.CO], 2011.
%H Emanuele Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Munarini/muna25.html">Two-Parameter Identities for q-Appell Polynomials</a>, Journal of Integer Sequences, Vol. 26 (2023), Article 23.3.1.
%H Igor Pak and Andrew Soffer, <a href="http://arxiv.org/abs/1507.00411">On Higman's k(U_n(F_q)) conjecture</a>, arXiv preprint arXiv:1507.00411 [math.CO], 2015.
%H Daniel Shanks, <a href="/A000003/a000003.pdf">Generalized Euler and class numbers</a>, Math. Comp., Vol. 21, No. 100 (1967), pp. 689-694; Vol. 22, No. 103 (1968), p. 699. [Annotated scanned copy]
%H Daniel Shanks, <a href="http://dx.doi.org/10.1090/S0025-5718-1967-0223295-5">Generalized Euler and class numbers</a>. Math. Comp., Vol. 21, No. 100 (1967), pp. 689-694.
%H Daniel Shanks, <a href="http://dx.doi.org/10.1090/S0025-5718-1968-0227093-9">Corrigenda to: "Generalized Euler and class numbers"</a>, Math. Comp. 22 , No. 103 (1968), p. 699.
%H Alan D. Sokal, <a href="https://arxiv.org/abs/1804.04498">The Euler and Springer numbers as moment sequences</a>, arXiv:1804.04498 [math.CO], 2018.
%H Zhi-Hong Sun, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.038">Congruences involving Bernoulli polynomials</a>, Discr. Math., Vol. 308, No. 1 (2007), pp. 71-112.
%H Zhi-Wei Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H.-Z. Li and J.-Y. Liu), Proc. the 6th China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258; see <a href="http://arxiv.org/abs/1208.2683">Conjectures involving combinatorial sequences</a>, arXiv preprint arXiv:1208.2683 [math.CO], 2012.
%H M. S. Tokmachev, <a href="https://vestnik.susu.ru/mmph/article/viewFile/8337/6806">Correlations Between Elements and Sequences in a Numerical Prism</a>, Bulletin of the South Ural State University, Ser. Mathematics. Mechanics. Physics, Vol. 11, No. 1 (2019), pp. 24-33.
%H Andrei Vieru, <a href="http://arxiv.org/abs/1107.2938">Agoh's conjecture: its proof, its generalizations, its analogues</a>, arXiv preprint arXiv:1107.2938 [math.NT], 2011.
%F E.g.f.: 1/(cos(x) - sin(x)).
%F Values at 1 of polynomials Q_n() defined in A104035. - _N. J. A. Sloane_, Nov 06 2009
%F a(n) = numerator of abs(Euler(n,1/4)). - _N. J. A. Sloane_, Nov 07 2009
%F Let B_n(x) = Sum_{k=0.. n*(n-1)/2} b(n,k)*x^k, where b(n,k) is number of n-node acyclic digraphs with k arcs, cf. A081064; then a(n) = |B_n(-2)|. - _Vladeta Jovovic_, Jan 25 2005
%F G.f. A(x) = y satisfies y'^2 = 2y^4 - y^2, y''y = y^2 + 2y'^2. - _Michael Somos_, Feb 03 2004
%F a(n) = (-1)^floor(n/2) Sum_{k=0..n} 2^k C(n,k) Euler(k). - _Peter Luschny_, Jul 08 2009
%F From _Peter Bala_, Feb 02 2011: (Start)
%F (1)... a(n) = ((1 + i)/2)^n*B(n,(1 - i)/(1 + i)), where i = sqrt(-1) and {B(n,x)}n>=0 = [1, 1 + x, 1 + 6*x + x^2, 1 + 23*x + 23*x^2 + x^3, ...] is the sequence of type B Eulerian polynomials - see A060187.
%F This yields the explicit formula
%F (2)... a(n) = ((1 + i)/2)^n*Sum_{k = 0..n} ((1 - i)/(1 + i))^k * Sum_{j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*(2*j + 1)^n.
%F The result (2) can be used to find congruences satisfied by the Springer numbers. For example, for odd prime p
%F (3)
%F ... a(p) = 1 (mod p) when p = 4*n + 1
%F ... a(p) = -1 (mod p) when p = 4*n + 3.
%F (End)
%F E.g.f.: 1/Q(0) where Q(k) = 1 - x/((2k+1)-x*(2k+1)/(x+(2k+2)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Nov 19 2011
%F E.g.f.: 2/U(0) where U(k) = 1 + 1/(1 + x/(2*k + 1 -x - (2*k+1)/(2 - x/(x+ (2*k+2)/U(k+1))))); (continued fraction, 5-step). - _Sergei N. Gladkovskii_, Sep 24 2012
%F E.g.f.: 1/G(0) where G(k) = 1 - x/(4*k+1 - x*(4*k+1)/(4*k+2 + x + x*(4*k+2)/(4*k+3 - x - x*(4*k+3)/(x + (4*k+4)/G(k+1) )))); (continued fraction, 3rd kind, 5-step). - _Sergei N. Gladkovskii_, Oct 02 2012
%F G.f.: 1/G(0) where G(k) = 1 - x*(2*k+1) - 2*x^2*(k+1)*(k+1)/G(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Jan 11 2013
%F a(n) = | 2*4^n*lerchphi(-1, -n, 1/4) |. - _Peter Luschny_, Apr 27 2013
%F a(n) ~ 4 * n^(n+1/2) * (4/Pi)^n / (sqrt(Pi)*exp(n)). - _Vaclav Kotesovec_, Oct 07 2013
%F G.f.: T(0)/(1-x), where T(k) = 1 - 2*x^2*(k+1)^2/( 2*x^2*(k+1)^2 - (1-x-2*x*k)*(1-3*x-2*x*k)/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Oct 15 2013
%F a(n) = (-1)^C(n+1,2)*2^(3*n+1)*(Zeta(-n,1/8)-Zeta(-n,5/8)), where Zeta(a,z) is the generalized Riemann zeta function. - _Peter Luschny_, Mar 11 2015
%F E.g.f. A(x) satisfies: A(x) = exp( Integral A(x)/A(-x) dx ). - _Paul D. Hanna_, Feb 04 2017
%F E.g.f. A(x) satisfies: A'(x) = A(x)^2/A(-x). - _Paul D. Hanna_, Feb 04 2017
%e Example
%e a(2) = 3: The three snakes of type B_2 are
%e (1,-2), (2,1), (2,-1).
%e a(3) = 11: The 11 snakes of type B_3 are
%e (1,-2,3), (1,-3,2), (1,-3,-2),
%e (2,1,3), (2,-1,3), (2,-3,1), (2,-3,-1),
%e (3,1,2), (3,-1,2), (3,-2,1), (3,-2,-1).
%p a := proc(n) local k; (-1)^iquo(n,2)*add(2^k*binomial(n,k)*euler(k),k=0..n) end; # _Peter Luschny_, Jul 08 2009
%p a := n -> (-1)^(n+iquo(n,2))*2^(3*n+1)*(Zeta(0,-n,1/8) - Zeta(0,-n,5/8)):
%p seq(a(n),n=0..21); # _Peter Luschny_, Mar 11 2015
%t n=21; CoefficientList[Series[1/(Cos[x]-Sin[x]), {x, 0, n}], x] * Table[k!, {k, 0, n}] (* _Jean-François Alcover_, May 18 2011 *)
%t Table[Abs[Numerator[EulerE[n,1/4]]],{n,0,35}] (* _Harvey P. Dale_, May 18 2011 *)
%o (PARI) {a(n) = if(n<0, 0, n! * polcoeff( 1 / (cos(x + x * O(x^n)) - sin(x + x * O(x^n))), n))}; /* _Michael Somos_, Feb 03 2004 */
%o (PARI) {a(n) = my(an); if(n<2, n>=0, an = vector(n+1, m, 1); for(m=2, n, an[m+1] = 2*an[m] + an[m-1] + sum(k=0, m-3, binomial(m-2, k) * (an[k+1] * an[m-1-k] + 2*an[k+2] * an[m-k] - an[k+3] * an[m-1-k]))); an[n+1])}; /* _Michael Somos_, Feb 03 2004 */
%o (PARI) /* Explicit formula by _Peter Bala_: */
%o {a(n)=((1+I)/2)^n*sum(k=0,n,((1-I)/(1+I))^k*sum(j=0,k,(-1)^(k-j)*binomial(n+1,k-j)*(2*j+1)^n))}
%o (Sage)
%o @CachedFunction
%o def p(n,x) :
%o if n == 0 : return 1
%o w = -1 if n%2 == 0 else 0
%o v = 1 if n%2 == 0 else -1
%o return v*add(p(k,0)*binomial(n,k)*(x^(n-k)+w) for k in range(n)[::2])
%o def A001586(n) : return abs(2^n*p(n, 1/2))
%o [A001586(n) for n in (0..21)] # _Peter Luschny_, Jul 19 2012
%Y Cf. A007836, A079858, A185417, A185418, A212435.
%Y Bisections are A000281 and A000464. Overview in A349264.
%Y Related polynomials are given in A098432, A081658 and A153641.
%Y Cf. A046802.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Jan 25 2005
|
