Editing Bernoulli number (section)

==An algorithmic view: the Seidel triangle==

The sequence ''S''<sub>''n''</sub> has another unexpected yet important property: The denominators of ''S''<sub>''n''+1</sub> divide the factorial {{math|''n''!}}. In other words: the numbers {{math|1=''T''<sub>''n''</sub>&nbsp;=&nbsp;''S''<sub>''n'' + 1</sub> ''n''!}}, sometimes called [[Alternating permutations|Euler zigzag numbers]], are integers.

: <math> T_n = 1,\,1,\,1,\,2,\,5,\,16,\,61,\,272,\,1385,\,7936,\,50521,\,353792,\ldots \quad n=0, 1, 2, 3, \ldots </math> ({{OEIS2C|id=A000111}}). See ({{OEIS2C|id=A253671}}).

Their [[exponential generating function]] is the sum of the [[trigonometric functions#Reciprocal functions|secant]] and [[tangent (trigonometry)|tangent]] functions.

: <math> \sum_{n=0}^\infty T_n \frac{x^n}{n!} = \tan \left(\frac\pi4 + \frac x2\right) = \sec x + \tan x</math>.

Thus the above representations of the Bernoulli and Euler numbers can be rewritten in terms of this sequence as

:<math>\begin{align}
 B_n &= (-1)^{\left\lfloor \frac{n}{2}\right\rfloor} [n\text{ even}] \frac{n }{2^n-4^n}\, T_{n-1}\  & n &\geq 2 \\
 E_n &= (-1)^{\left\lfloor \frac{n}{2}\right\rfloor} [n\text{ even}] T_{n} & n &\geq 0
\end{align}</math>

These identities make it easy to compute the Bernoulli and Euler numbers: the Euler numbers {{math|''E''<sub>2''n''</sub>}} are given immediately by {{math|''T''<sub>2''n''</sub>}} and the Bernoulli numbers {{math|''B''<sub>2''n''</sub>}} are fractions obtained from {{math|''T''<sub>2''n'' - 1</sub>}} by some easy shifting, avoiding rational arithmetic.

What remains is to find a convenient way to compute the numbers {{math|''T''<sub>''n''</sub>}}. However, already in 1877 [[Philipp Ludwig von Seidel]] published an ingenious algorithm, which makes it simple to calculate {{math|''T''<sub>''n''</sub>}}.{{r|Seidel1877}}

{{image frame|align=none|caption=Seidel's algorithm for {{math|''T''<sub>''n''</sub>}}
|content=<math>
\begin{array}{crrrcc}
 { } & { } & {\color{red}1} & { } & { } & { } \\
 { } & {\rightarrow} & {\color{blue}1} & {\color{red}1} & { } \\
 { } & {\color{red}2} & {\color{blue}2} & {\color{blue}1} & {\leftarrow} \\
 {\rightarrow} & {\color{blue}2} & {\color{blue}4} & {\color{blue}5} & {\color{red}5} \\
 {\color{red}16} & {\color{blue}16} & {\color{blue}14} & {\color{blue}10} & {\color{blue}5} & {\leftarrow} 
\end{array}
</math>}}
#Start by putting 1 in row 0 and let {{math|''k''}} denote the number of the row currently being filled
#If {{math|''k''}} is odd, then put the number on the left end of the row {{math|''k'' − 1}} in the first position of the row {{math|''k''}}, and fill the row from the left to the right, with every entry being the sum of the number to the left and the number to the upper
#At the end of the row duplicate the last number.
#If {{math|''k''}} is even, proceed similar in the other direction.

Seidel's algorithm is in fact much more general (see the exposition of Dominique Dumont {{r|Dumont1981}}) and was rediscovered several times thereafter.

Similar to Seidel's approach D. E. Knuth and T. J. Buckholtz gave a recurrence equation for the numbers {{math|''T''<sub>2''n''</sub>}} and recommended this method for computing {{math|''B''<sub>2''n''</sub>}} and {{math|''E''<sub>2''n''</sub>}} 'on electronic computers using only simple operations on integers'.{{r|KnuthBuckholtz1967}}

V. I. Arnold{{r|Arnold1991}} rediscovered Seidel's algorithm and later Millar, Sloane and Young popularized Seidel's algorithm under the name [[boustrophedon transform]].

Triangular form:

:{| style="text-align:right"
| || || || || || || 1|| || || || || || 
|-
| || || || || || 1|| || 1|| || || || || 
|-
| || || || || 2|| || 2|| || 1|| || || || 
|-
| || || || 2|| || 4|| || 5|| || 5|| || || 
|-
| || || 16|| || 16|| || 14|| || 10|| || 5|| || 
|-
| || 16|| || 32|| || 46|| || 56|| || 61|| || 61|| 
|-
|272|| ||272|| ||256|| ||224|| ||178|| ||122|| || 61
|}

Only {{OEIS2C|id=A000657}}, with one 1, and {{OEIS2C|id=A214267}}, with two 1s, are in the OEIS.

Distribution with a supplementary 1 and one 0 in the following rows:

:{| style="text-align:right"
| || || || || || || 1|| || || || || ||   
|-
| || || || || || 0|| || 1|| || || || || 
|-
| || || || || −1|| || −1|| ||  0|| || || || 
|-
| || || || 0|| || −1|| || −2|| || −2|| || || 
|-
| || ||  5|| ||  5|| ||  4|| ||  2|| ||  0|| || 
|-
| || 0|| || 5|| || 10|| || 14|| || 16|| || 16|| 
|-
|−61|| ||−61|| ||−56|| ||−46|| ||−32|| ||−16|| || 0
|}

This is {{OEIS2C|id=A239005}}, a signed version of {{OEIS2C|id=A008280}}. The main andiagonal is {{OEIS2C|id=A122045}}. The main diagonal is {{OEIS2C|id=A155585}}. The central column is {{OEIS2C|id=A099023}}. Row sums: 1, 1, −2, −5, 16, 61.... See {{OEIS2C|id=A163747}}. See the array beginning with 1, 1, 0, −2, 0, 16, 0 below.

The Akiyama–Tanigawa algorithm applied to {{OEIS2C|id=A046978}} ({{math|''n'' + 1}}) / {{OEIS2C|id=A016116}}({{math|''n''}}) yields:

:{| style="text-align:right"
| 1|| 1|| {{sfrac|1|2}}|| 0|| −{{sfrac|1|4}}|| −{{sfrac|1|4}}|| −{{sfrac|1|8}}
|-
| 0|| 1|| {{sfrac|3|2}}|| 1|| 0|| −{{sfrac|3|4}}
|-
| −1|| −1|| {{sfrac|3|2}}|| 4|| {{sfrac|15|4}}
|-
| 0|| −5|| −{{sfrac|15|2}}|| 1
|-
| 5|| 5|| −{{sfrac|51|2}}
|-
| 0|| 61
|-
| −61
|}

'''1.''' The first column is {{OEIS2C|id=A122045}}. Its binomial transform leads to:

:{| style="text-align:right"
|-
| 1|| 1|| 0|| −2|| 0|| 16|| 0
|-
|0||−1||−2||2||16||−16
|-
|−1||−1||4||14||−32
|-
|0||5||10||−46
|-
|5||5||−56
|-
|0||−61
|-
|−61
|}

The first row of this array is {{OEIS2C|id=A155585}}. The absolute values of the increasing antidiagonals are {{OEIS2C|id=A008280}}. The sum of the antidiagonals is {{nowrap|−{{OEIS2C|id=A163747}} ({{math|''n'' + 1}}).}}

'''2.''' The second column is {{nowrap|1 1 −1 −5 5 61 −61 −1385 1385...}}. Its binomial transform yields:

:{| style="text-align:right"
|-
| 1|| 2|| 2|| −4|| −16|| 32|| 272
|-
|1||0||−6||−12||48||240
|-
|−1||−6||−6||60||192
|-
|−5||0||66||32
|-
|5||66||66
|-
|61||0
|-
|−61
|}

The first row of this array is {{nowrap|1 2 2 −4 −16 32 272 544 −7936 15872 353792 −707584...}}. The absolute values of the second bisection are the double of the absolute values of the first bisection.

Consider the Akiyama-Tanigawa algorithm applied to {{OEIS2C|id=A046978}} ({{math|''n''}}) / ({{OEIS2C|id=A158780}} ({{math|''n'' + 1}}) =&nbsp;abs({{OEIS2C|id=A117575}} ({{mvar|n}})) + 1 = {{nowrap|1, 2, 2, {{sfrac|3|2}}, 1, {{sfrac|3|4}}, {{sfrac|3|4}}, {{sfrac|7|8}}, 1, {{sfrac|17|16}}, {{sfrac|17|16}}, {{sfrac|33|32}}...}}.

:{| style="text-align:right"
|1||2||2||{{sfrac|3|2}}||1||{{sfrac|3|4}}||{{sfrac|3|4}}
|-
|−1||0||{{sfrac|3|2}}||2||{{sfrac|5|4}}||0
|-
|−1||−3||−{{sfrac|3|2}}||3||{{sfrac|25|4}}
|-
|2||−3||−{{sfrac|27|2}}||−13
|-
|5||21||−{{sfrac|3|2}}
|-
|−16||45
|-
|−61
|}

The first column whose the absolute values are {{OEIS2C|id=A000111}} could be the numerator of a trigonometric function.

{{OEIS2C|id=A163747}} is an autosequence of the first kind (the main diagonal is {{OEIS2C|id=A000004}}). The corresponding array is:

:{| style="text-align:right"
|0||−1||−1||2||5||−16||−61
|-
|−1||0||3||3||−21||−45
|-
|1||3||0||−24||−24
|-
|2||−3||−24||0
|-
|−5||−21||24
|-
|−16||45
|-
|−61
|}

The first two upper diagonals are {{nowrap|−1 3 −24 402...}} = {{math|(−1)<sup>''n'' + 1</sup>}}&nbsp;×&nbsp;{{OEIS2C|id=A002832}}. The sum of the antidiagonals is {{nowrap|0 −2 0 10...}} = 2&nbsp;×&nbsp;{{OEIS2C|id=A122045}}(''n''&nbsp;+&nbsp;1).

−{{OEIS2C|id=A163982}} is an autosequence of the second kind, like for instance {{OEIS2C|id=A164555}} / {{OEIS2C|id=A027642}}. Hence the array:

:{| style="text-align:right"
|-
|2||1||−1||−2||5||16||−61
|-
|−1||−2||−1||7||11||−77
|-
|−1||1||8||4||−88
|-
|2||7||−4||−92
|-
|5||−11||−88
|-
|−16||−77
|-
|−61
|}

The main diagonal, here {{nowrap|2 −2 8 −92...}}, is the double of the first upper one, here {{OEIS2C|id=A099023}}. The sum of the antidiagonals is {{nowrap|2 0 −4 0...}} = 2&nbsp;×&nbsp;{{OEIS2C|id=A155585}}({{math|''n'' + }}1). {{OEIS2C|id=A163747}}&nbsp;−&nbsp;{{OEIS2C|id=A163982}} =&nbsp;2&nbsp;×&nbsp;{{OEIS2C|id=A122045}}.