A002051 Steffensen's bracket function [n,2]. (Formerly M4644 N1986)

0, 0, 1, 9, 67, 525, 4651, 47229, 545707, 7087005, 102247051, 1622631549, 28091565547, 526858344285, 10641342962251, 230283190961469, 5315654681948587, 130370767029070365, 3385534663256714251, 92801587319328148989, 2677687796244383678827, 81124824998504072833245, 2574844419803190382447051

Offset

1,4

Comments

a(n) is the number of ways to arrange the blocks of the partitions of {1,2,...,n} in an undirected cycle of length 3 or more, see A000629. - Geoffrey Critzer, Nov 23 2012

From Gus Wiseman, Jun 24 2020: (Start)

Also the number of (1,2)-matching length-n sequences covering an initial interval of positive integers. For example, the a(2) = 1 and a(3) = 9 sequences are:

(1,2) (1,1,2)

(1,2,1)

(1,2,2)

(1,2,3)

(1,3,2)

(2,1,2)

(2,1,3)

(2,3,1)

(3,1,2)

Missing from this list are:

(1,1) (1,1,1)

(2,1) (2,1,1)

(2,2,1)

(3,2,1)

(End)

References

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

Steffensen, J. F. Interpolation. 2d ed. Chelsea Publishing Co., New York, N. Y., 1950. ix+248 pp. MR0036799 (12,164d)

Links

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

G. J. Simmons, Letter to N. J. Sloane, May 29 1974

J. F. Steffensen, On a class of polynomials and their application to actuarial problems, Skandinavisk Aktuarietidskrift, Vol. 11, pp. 75-97, 1928.

Wikipedia, Permutation pattern

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Formula

[n,2] = Sum_{s=2..n-1} Stirling2(n,s+1)*s!/2 (cf. A241168).

a(1)=0; for n >= 2, a(n) = A000670(n-1) - 2^(n-2). - Manfred Goebel (mkgoebel(AT)essex.ac.uk), Feb 20 2000; formula adjusted by N. J. A. Sloane, Apr 22 2014. For example, a(5) = 67 = A000670(4)-2^3 = 75-8 = 67.

E.g.f.: (1 - exp(2*x) - 2*log(2 - exp(x)))/4 = B(A(x)) where A(x) = exp(x)-1 and B(x) = (log(1/(1-x))- x - x^2/2)/2. - Geoffrey Critzer, Nov 23 2012

Example

a(4) = 9. There are 6 partitions of {1,2,3,4} into exactly three blocks and one way to put them in an undirected cycle of length three. There is one partition of {1,2,3,4} into four blocks and 3 ways to make an undirected cycle of length four. 6 + 3 = 9. - Geoffrey Critzer, Nov 23 2012

Mathematica

a[n_] := Sum[ k!*StirlingS2[n-1, k], {k, 0, n-1}] - 2^(n-2); Table[a[n], {n, 3, 17}] (* Jean-François Alcover, Nov 18 2011, after Manfred Goebel *)
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n], !GreaterEqual@@#&]], {n, 0, 5}] (* Gus Wiseman, Jun 24 2020 *)

Prog

(PARI) a(n) = sum(s=2, n-1, stirling(n, s+1, 2)*s!/2); \\ Michel Marcus, Jun 24 2020

Crossrefs

A diagonal of the triangular array in A241168.

(1,2)-avoiding patterns are counted by A011782.

(1,1)-matching patterns are counted by A019472.

(1,2)-matching permutations are counted by A033312.

(1,2)-matching compositions are counted by A056823.

(1,2)-matching permutations of prime indices are counted by A335447.

(1,2)-matching compositions are ranked by A335485.

Patterns are counted by A000670 and ranked by A333217.

Patterns matched by compositions are counted by A335456.

Cf. A056986, A335454, A335465, A335486, A335515.

Sequence in context: A115202 A287817 A155592 * A231192 A133120 A194650

Adjacent sequences: A002048 A002049 A002050 * A002052 A002053 A002054

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Entry revised by N. J. A. Sloane, Apr 22 2014

Status

approved