A002051 Steffensen's bracket function [n,2].

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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)

Examples

			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
		

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.

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.

Programs

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 *)

PARI

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

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

Extensions

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