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

%I M4644 N1986 #61 Jun 24 2020 19:05:01

%S 0,0,1,9,67,525,4651,47229,545707,7087005,102247051,1622631549,

%T 28091565547,526858344285,10641342962251,230283190961469,

%U 5315654681948587,130370767029070365,3385534663256714251,92801587319328148989,2677687796244383678827,81124824998504072833245,2574844419803190382447051

%N Steffensen's bracket function [n,2].

%C 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

%C From _Gus Wiseman_, Jun 24 2020: (Start)

%C 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:

%C (1,2) (1,1,2)

%C (1,2,1)

%C (1,2,2)

%C (1,2,3)

%C (1,3,2)

%C (2,1,2)

%C (2,1,3)

%C (2,3,1)

%C (3,1,2)

%C Missing from this list are:

%C (1,1) (1,1,1)

%C (2,1) (2,1,1)

%C (2,2,1)

%C (3,2,1)

%C (End)

%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 Steffensen, J. F. Interpolation. 2d ed. Chelsea Publishing Co., New York, N. Y., 1950. ix+248 pp. MR0036799 (12,164d)

%H T. D. Noe, <a href="/A002051/b002051.txt">Table of n, a(n) for n = 1..100</a>

%H G. J. Simmons, <a href="/A002050/a002050_2.pdf">Letter to N. J. Sloane, May 29 1974</a>

%H J. F. Steffensen, <a href="http://dx.doi.org/10.1080/03461238.1928.10416863">On a class of polynomials and their application to actuarial problems</a>, Skandinavisk Aktuarietidskrift, Vol. 11, pp. 75-97, 1928.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>

%H Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>

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

%F 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.

%F 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

%e 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

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

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];

%t Table[Length[Select[Join@@Permutations/@allnorm[n],!GreaterEqual@@#&]],{n,0,5}] (* _Gus Wiseman_, Jun 24 2020 *)

%o (PARI) a(n) = sum(s=2, n-1, stirling(n,s+1,2)*s!/2); \\ _Michel Marcus_, Jun 24 2020

%Y A diagonal of the triangular array in A241168.

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

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

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

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

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

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

%Y Patterns are counted by A000670 and ranked by A333217.

%Y Patterns matched by compositions are counted by A335456.

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

%K nonn,easy,nice

%O 1,4

%A _N. J. A. Sloane_

%E Entry revised by _N. J. A. Sloane_, Apr 22 2014