A056986 -id:A056986 - cp's OEIS frontend

A001250 Number of alternating permutations of order n.

1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, 44736512, 398721962, 3807514624, 38783024290, 419730685952, 4809759350882, 58177770225664, 740742376475050, 9902996106248192, 138697748786275802, 2030847773013704704, 31029068327114173810

Offset: 0

N. J. A. Sloane

For n>1, a(n) is the number of permutations of order n with the length of longest run equal 2.
Boustrophedon transform of the Euler numbers (A000111). [Berry et al., 2013] - N. J. A. Sloane, Nov 18 2013
Number of inversion sequences of length n where all consecutive subsequences i,j,k satisfy i >= j < k or i < j >= k. a(4) = 10: 0010, 0011, 0020, 0021, 0022, 0101, 0102, 0103, 0112, 0113. - Alois P. Heinz, Oct 16 2019

			1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 32*x^5 + 122*x^6 + 544*x^7 + 2770*x^8 + ...
From _Gus Wiseman_, Jun 21 2021: (Start)
The a(0) = 1 through a(4) = 10 permutations:
  ()  (1)  (1,2)  (1,3,2)  (1,3,2,4)
           (2,1)  (2,1,3)  (1,4,2,3)
                  (2,3,1)  (2,1,4,3)
                  (3,1,2)  (2,3,1,4)
                           (2,4,1,3)
                           (3,1,4,2)
                           (3,2,4,1)
                           (3,4,1,2)
                           (4,1,3,2)
                           (4,2,3,1)
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..500 (terms n=1..100 from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv:1205.4581 [math.CO], 2012-2013.
Désiré André, Sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Étude sur les maxima, minima et séquences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
Stefano Barbero, Umberto Cerruti, and Nadir Murru, Some combinatorial properties of the Hurwitz series ring arXiv:1710.05665 [math.NT], 2017.
D. Berry, J. Broom, D. Dixon, and A. Flaherty, Umbral Calculus and the Boustrophedon Transform, 2013.
C. K. Cook, M. R. Bacon, and R. A. Hillman, Higher-order Boustrophedon transforms for certain well-known sequences, Fib. Q., 55(3) (2017), 201-208.
C. Davis, Problem 4755, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534.
Chandler Davis, Problem 4755: A Permutation Problem, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] [Annotated scanned copy]
S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math., 260 (2003), 89-100. (See p. 100.)
S. T. Thompson, Problem E754: Skew Ordered Sequences, Amer. Math. Monthly, 54 (1947), 416-417. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Alternating Permutation

Cf. A000111. A diagonal of A010094.
Cf. A001251, A001252, A001253, A010026, A211318, A260786.
The version for permutations of prime indices is A345164.
The version for compositions is A025047, ranked by A345167.
The version for patterns is A345194.
A049774 counts permutations avoiding adjacent (1,2,3).
A344614 counts compositions avoiding adjacent (1,2,3) and (3,2,1).
A344615 counts compositions avoiding the weak adjacent pattern (1,2,3).
A344654 counts partitions without a wiggly permutation, ranked by A344653.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
A345192 counts non-wiggly compositions, ranked by A345168.
Cf. A000041, A003242, A032020, A056986, A261962, A325534, A325535, A335452, A344652, A344740, A345165.
Row sums of A104345.

a001250 n = if n == 1 then 1 else 2 * a000111 n
-- Reinhard Zumkeller, Sep 17 2014

# With Eulerian polynomials:
A := (n, x) -> `if`(n<2, 1/2/(1+I)^(1-n), add(add((-1)^j*binomial(n+1, j)*(m+1-j)^n, j=0..m)*x^m, m=0..n-1)):
A001250 := n -> 2*(I-1)^(1-n)*exp(I*(n-1)*Pi/2)*A(n,I);
seq(A001250(i), i=0..22); # Peter Luschny, May 27 2012
# second Maple program:
b:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
    end:
a:= n-> `if`(n<2, 1, 2)*b(n, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 29 2015

a[n_] := 4*Abs[PolyLog[-n, I]]; a[0] = a[1] = 1; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 09 2016, after M. F. Hasler *)
Table[Length[Select[Permutations[Range[n]],And@@(!(OrderedQ[#]||OrderedQ[Reverse[#]])&/@Partition[#,3,1])&]],{n,8}] (* Gus Wiseman, Jun 21 2021 *)
a[0]:=1; a[1]:=1; a[n_]:=a[n]=1/(n (n-1)) Sum[a[n-1-k] a[k] k, {k,1, n-1}]; Join[{a[0], a[1]}, Map[2 #! a[#]&, Range[2,24]]] (* Oliver Seipel, May 27 2024 *)

{a(n) = local(v=[1], t); if( n<0, 0, for( k=2, n+3, t=0; v = vector( k, i, if( i>1, t += v[k+1 - i]))); v[3])} /* Michael Somos, Feb 03 2004 */

{a(n) = if( n<0, 0, n! * polcoeff( (tan(x + x * O(x^n)) + 1 / cos(x + x * O(x^n)))^2, n))} /* Michael Somos, Feb 05 2011 */

A001250(n)=sum(m=0,n\2,my(k);(-1)^m*sum(j=0,k=n+1-2*m,binomial(k,j)*(-1)^j*(k-2*j)^(n+1))/k>>k)*2-(n==1)  \\ M. F. Hasler, May 19 2012

A001250(n)=4*abs(polylog(-n,I))-(n==1)  \\ M. F. Hasler, May 20 2012

my(x='x+O('x^66), egf=1+2*(tan(x)+1/cos(x))-2-x); Vec(serlaplace(egf)) /* Joerg Arndt, May 28 2012 */

from itertools import accumulate, islice
def A001250_gen(): # generator of terms
    yield from (1,1)
    blist = (0,2)
    while True:
        yield (blist := tuple(accumulate(reversed(blist),initial=0)))[-1]
A001250_list = list(islice(A001250_gen(),40)) # Chai Wah Wu, Jun 09-11 2022

from sympy import bernoulli, euler
def A001250(n): return 1 if n<2 else abs(((1<Chai Wah Wu, Nov 13 2024

# Algorithm of L. Seidel (1877)
def A001250_list(n) :
    R = [1]; A = {-1:0, 0:2}; k = 0; e = 1
    for i in (0..n) :
        Am = 0; A[k + e] = 0; e = -e
        for j in (0..i) : Am += A[k]; A[k] = Am; k += e
        if i > 1 : R.append(A[-i//2] if i%2 == 0 else A[i//2])
    return R
A001250_list(22) # Peter Luschny, Mar 31 2012

a(n) = coefficient of x^(n-1)/(n-1)! in power series expansion of (tan(x) + sec(x))^2 = (tan(x)+1/cos(x))^2.
a(n) = coefficient of x^n/n! in power series expansion of 2*(tan(x) + sec(x)) - 2 - x. - Michael Somos, Feb 05 2011
For n>1, a(n) = 2 * A000111(n). - Michael Somos, Mar 19 2011
a(n) = 4*|Li_{-n}(i)| - [n=1] = Sum_{m=0..n/2} (-1)^m*2^(1-k)*Sum_{j=0..k} binomial(k,j)*(-1)^j*(k-2*j)^(n+1)/k - [n=1], where k = k(m) = n+1-2*m and [n=1] equals 1 if n=1 and zero else; Li denotes the polylogarithm (and i^2 = -1). - M. F. Hasler, May 20 2012
From Sergei N. Gladkovskii, Jun 18 2012: (Start)
Let E(x) = 2/(1-sin(x))-1 (essentially the e.g.f.), then
E(x) = -1 + 2*(-1/x + 1/(1-x)/x - x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k) = (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1); (continued fraction, Euler's 1st kind, 1-step).
E(x) = -1 + 2*(-1/x + 1/(1-x)/x - x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k) = 8*k + 6 - x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)); (continued fraction, Euler's 2nd kind, 2-step).
E(x) = (tan(x) + sec(x))^2 = -1 + 2/(1-x*G(0)) where G(k) = 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End)
G.f.: conjecture: 2*T(0)/(1-x) -1, where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2013
a(n) ~ 2^(n+3) * n! / Pi^(n+1). - Vaclav Kotesovec, Sep 06 2014
a(n) = Sum_{k=0..n-1} A109449(n-1,k)*A000111(k). - Reinhard Zumkeller, Sep 17 2014

Edited by Max Alekseyev, May 04 2012

a(0)=1 prepended by Alois P. Heinz, Nov 29 2015

A274174 Number of compositions of n if all summand runs are kept together.

Original entry on oeis.org

1, 1, 2, 4, 7, 12, 22, 36, 60, 97, 162, 254, 406, 628, 974, 1514, 2305, 3492, 5254, 7842, 11598, 17292, 25294, 37090, 53866, 78113, 112224, 161092, 230788, 328352, 466040, 658846, 928132, 1302290, 1821770, 2537156, 3536445, 4897310, 6777806, 9341456, 12858960, 17625970, 24133832, 32910898, 44813228, 60922160, 82569722

Offset: 0

Gregory L. Simay, Jun 12 2016

nonn

a(n^2) is odd. - Gregory L. Simay, Jun 23 2019

Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). - Gus Wiseman, Jul 07 2020

			If the summand runs are blocked together, there are 22 compositions of a(6): 6; 5+1, 1+5, 4+2, 2+4, (3+3), 4+(1+1), (1+1)+4, 1+2+3, 1+3+2, 2+1+3, 2+3+1, 3+1+2, 3+2+1, (2+2+2), 3+(1+1+1), (1+1+1)+3, (2+2)+(1+1), (1+1)+(2+2), 2+(1+1+1+1), (1+1+1+1)+2, (1+1+1+1+1+1).
a(0)=1; a(1)= 1; a(4) = 7; a(9) = 97; a(16) = 2305; a(25) = 78113 and a(36) = 3536445. - _Gregory L. Simay_, Jun 23 2019

Alois P. Heinz, Table of n, a(n) for n = 0..5000
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A000070, A101880, A116608.
The version for patterns is A001339.
The version for prime indices is A333175.
The complement (i.e., the matching version) is A335548.
Anti-run compositions are A003242.
(1,2,1)- and (2,1,2)-matching permutations of prime indices are A335462.
(1,2,1)-matching compositions are A335470.
(1,2,1)-avoiding compositions are A335471.
(2,1,2)-matching compositions are A335472.
(2,1,2)-avoiding compositions are A335473.
Cf. A000670, A056986, A181796, A335451, A335452, A335460, A335463.

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
       add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Jun 12 2016

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]==Length[Union[#]]&]],{n,0,10}] (* Gus Wiseman, Jul 07 2020 *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0,
    Sum[b[n - i*j, i - 1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 11 2021, after Alois P. Heinz *)

a(n) = Sum_{k>=0} k! * A116608(n,k). - Joerg Arndt, Jun 12 2016

Terms a(9) and beyond from Joerg Arndt, Jun 12 2016

A158423 Number of permutations of 1..n containing the relative rank sequence { 23145 } at any spacing.

Original entry on oeis.org

1, 26, 459, 7034, 101953, 1454402, 20863742, 304906732, 4578822750, 71092815624, 1146499731400, 19270199314388, 338394827020511, 6218127006568582, 119650035623211443, 2410982527835022898, 50846926185692443237, 1121251553648267523078, 25820703260713964268656, 620088145746453017943268

Offset: 5

R. H. Hardin, Mar 18 2009

nonn

Same series for 43521 12534 54132 35421 31245 12453 54213 43512 23154 21534 45132 35412 31254 21453 45213.

Martin Fuller, Table of n, a(n) for n = 5..38
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A056986, A158005, A116485.

Conjecture: a(n) + A116485(n) = n!. - Benedict W. J. Irwin, Mar 15 2016

Proof: see A116485.

a(17) onwards from A116485, by Martin Fuller, Aug 26 2023

A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 31, 60, 114, 214, 398, 732, 1334, 2410, 4321, 7688, 13590, 23869, 41686, 72405, 125144, 215286, 368778, 629156, 1069396, 1811336, 3058130, 5147484, 8639976, 14463901, 24154348, 40244877, 66911558, 111026746, 183886685, 304034456, 501877227

Offset: 0

Herbert S. Wilf, Feb 07 2005

The sequence is the same no matter which of the six patterns of three letters is chosen as the one to be avoided.

			a(6) = 31 because there are 32 compositions of 6 into positive parts and only one of these, namely 6 = 1+2+3, contains the pattern (123), the other 31 compositions of 6 avoid that pattern.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..900 (first 400 terms from Alois P. Heinz)
M. Elder and V. Vatter, Problems and conjectures presented at the third international conference on permutation petterns
Carla D. Savage and Herbert S. Wilf, Pattern avoidance in compositions and multiset permutations, Advances in Applied Mathematics 36 (2006), pp.194-201.
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for patterns is A226316.
These compositions are ranked by the complement of A335479.
The matching version is A335514.
The version for prime indices is A335521.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Compositions are counted by A011782.
Strict compositions are counted by A032020 and ranked by A233564.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a given composition are counted by A335465.
Cf. A056986, A106356, A232464, A269134, A333755.

b:= proc(n, m, t) option remember; `if`(n=0, 1,
      add(b(n-i, min(m, i, n-i), min(t, n-i,
      `if`(i>m, i, t))), i=1..min(n, t)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 18 2014

b[n_, m_, t_] := b[n, m, t] = If[n == 0, 1, Sum[b[n - i, Min[m, i, n - i], Min[t, n - i, If[i > m, i, t]]], {i, 1, Min[n, t]}]];
a[n_] := b[n, n, n];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union[mstype/@Subsets[#]],{1,2,3}]&]],{n,0,10}] (* Gus Wiseman, Jun 22 2020 *)

seq(n)={Vec(sum(i=1, n, prod(j=1, n, if(i==j, 1, (1-x^i)/((1-x^(j-i))*(1-x^i-x^j))) + O(x*x^n))/(1-x^i)))} \\ Andrew Howroyd, Dec 31 2020

G.f.: Sum_{i>=1} (1/(1-x^i))*Product_{j>=1, j<>i} (1-x^i)/((1-x^(j-i))*(1-x^i-x^j)).

Asymptotics (Savage and Wilf, 2005): a(n) ~ c * ((1+sqrt(5))/2)^n, where c = r/(r-1)/(r-s) * (r * Product_{j>=3} (1-1/r)/(1-r^(1-j))/(1-1/r-r^(-j)) - Product_{j>=3} (1-1/r^2)/(1-r^(2-j))/(1-1/r^2-r^(-j)) ) = 18.9399867283479198666671671745270505487677312850521421513193261105... and r = (1+sqrt(5))/2, s = (1-sqrt(5))/2. - Vaclav Kotesovec, May 02 2014

More terms from Ralf Stephan, May 27 2005

A335456 Number of normal patterns matched by compositions of n.

Original entry on oeis.org

1, 2, 5, 12, 32, 84, 211, 556, 1446, 3750, 9824, 25837, 67681, 178160, 468941, 1233837, 3248788, 8554709

Offset: 0

Gus Wiseman, Jun 16 2020

A composition of n is a finite sequence of positive integers summing to n.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The 8 compositions of 4 together with the a(4) = 32 patterns they match:
  4:   31:   13:   22:   211:   121:   112:   1111:
-----------------------------------------------------
  ()   ()    ()    ()    ()     ()     ()     ()
  (1)  (1)   (1)   (1)   (1)    (1)    (1)    (1)
       (21)  (12)  (11)  (11)   (11)   (11)   (11)
                         (21)   (12)   (12)   (111)
                         (211)  (21)   (112)  (1111)
                                (121)

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

References found in the link are not all included here.
The version for standard compositions is A335454.
The contiguous case is A335457.
The version for Heinz numbers of partitions is A335549.
Patterns are counted by A000670 and ranked by A333217.
The n-th composition has A124771(n) distinct consecutive subsequences.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A056986, A106356, A108917, A124770, A269134, A329744, A333224, A335458.

mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,Join@@Permutations/@IntegerPartitions[n]}],{n,0,8}]

a(14)-a(16) from Jinyuan Wang, Jun 26 2020

a(17) from John Tyler Rascoe, Mar 14 2025

A335465 Number of minimal normal patterns avoided by the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 12, 4, 3, 3, 3, 3, 4, 3, 4, 12, 4, 3, 12, 4, 12, 4, 12, 4, 3, 3, 3, 3, 4, 3, 3, 6, 4, 3, 6, 3, 3, 6, 10, 10, 4, 3, 12, 6, 12, 3, 10, 10, 12, 4, 12, 3, 12, 4, 12, 4, 3, 3, 3, 3, 4, 3, 3, 6

Offset: 0

Gus Wiseman, Jun 20 2020

These patterns comprise the basis of the class of patterns generated by this composition.
We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The bases of classes generated by (), (1), (2,1,1), (3,1,2), (2,1,2,1), and (1,2,1), corresponding to n = 0, 1, 11, 38, 45, 13, are the respective columns below.
  (1)  (1,1)  (1,2)    (1,1)    (1,1,1)    (1,1,1)
       (1,2)  (1,1,1)  (1,2,3)  (1,1,2)    (1,1,2)
       (2,1)  (2,2,1)  (1,3,2)  (1,2,2)    (1,2,2)
              (3,2,1)  (2,1,3)  (1,2,3)    (1,2,3)
                       (2,3,1)  (1,3,2)    (1,3,2)
                       (3,2,1)  (2,1,3)    (2,1,1)
                                (2,3,1)    (2,1,2)
                                (3,1,2)    (2,1,3)
                                (3,2,1)    (2,2,1)
                                (2,2,1,1)  (2,3,1)
                                           (3,1,2)
                                           (3,2,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

Patterns matched by standard compositions are counted by A335454.
Patterns matched by compositions of n are counted by A335456(n).
The version for Heinz numbers of partitions is A335550.
Patterns are counted by A000670 and ranked by A333217.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A334299(n) distinct subsequences.
Cf. A056986, A124767, A124770, A124771, A269134, A333218, A333257, A335549.

A261982 Number of compositions of n with some part repeated.

Original entry on oeis.org

0, 0, 1, 1, 5, 11, 21, 51, 109, 229, 455, 959, 1947, 3963, 7999, 16033, 32333, 64919, 130221, 260967, 522733, 1045825, 2093855, 4189547, 8382315, 16768455, 33543127, 67093261, 134193413, 268404995, 536829045, 1073686083, 2147408773, 4294869253, 8589803783

Offset: 0

Alois P. Heinz, Sep 07 2015

nonn

Also compositions matching the pattern (1,1). - Gus Wiseman, Jun 23 2020

			a(2) = 1: 11.
a(3) = 1: 111.
a(4) = 5: 22, 211, 121, 112, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..3322
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Row sums of A261981 and of A262191.
Cf. A262047.
The version for patterns is A019472.
The (1,1)-avoiding version is A032020.
The case of partitions is A047967.
(1,1,1)-matching compositions are counted by A335455.
Patterns matched by compositions are counted by A335456.
(1,1)-matching compositions are ranked by A335488.
Cf. A011782, A056986, A106356, A181796, A238279, A269134, A333755.

b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
    end:
a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..40);

b[n_, k_] := b[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], b[n-k, k] + k*b[n-k, k-1]]]; a[n_] := Ceiling[2^(n-1)]-Sum[b[n, k], {k, 0, Floor[ (Sqrt[8n+1]-1)/2]}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 08 2017, translated from Maple *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>Length[Split[#]]&]],{n,0,10}] (* Gus Wiseman, Jun 24 2020 *)

a(n) = A011782(n) - A032020(n).

G.f.: (1 - x) / (1 - 2*x) - Sum_{k>=0} k! * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - Ilya Gutkovskiy, Jan 30 2020

A335454 Number of normal patterns matched by the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 5, 3, 6, 5, 5, 2, 3, 3, 5, 3, 5, 6, 7, 3, 6, 5, 9, 5, 9, 7, 6, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 4, 7, 5, 10, 9, 9, 3, 6, 5, 9, 4, 9, 10, 12, 5, 9, 7, 13, 7, 12, 9, 7, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 5, 7, 6, 10, 9, 9, 3, 5, 6, 8, 5

Offset: 0

Gus Wiseman, Jun 14 2020

We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The a(n) patterns for n = 0, 1, 3, 7, 11, 13, 23, 83, 27, 45:
  0:  1:   11:   111:   211:   121:   2111:   2311:   1211:   2121:
---------------------------------------------------------------------
  ()  ()   ()    ()     ()     ()     ()      ()      ()      ()
      (1)  (1)   (1)    (1)    (1)    (1)     (1)     (1)     (1)
           (11)  (11)   (11)   (11)   (11)    (11)    (11)    (11)
                 (111)  (21)   (12)   (21)    (12)    (12)    (12)
                        (211)  (21)   (111)   (21)    (21)    (21)
                               (121)  (211)   (211)   (111)   (121)
                                      (2111)  (231)   (121)   (211)
                                              (2311)  (211)   (212)
                                                      (1211)  (221)
                                                              (2121)

John Tyler Rascoe, Table of n, a(n) for n = 0..8192
Wikipedia, Permutation pattern
Gus Wiseman, Statistics, classes, and transformations of standard compositions
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

References found in the links are not all included here.
Summing over indices with binary length n gives A335456(n).
The contiguous case is A335458.
The version for Heinz numbers of partitions is A335549.
Patterns are counted by A000670 and ranked by A333217.
The n-th composition has A124771(n) distinct consecutive subsequences.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal avoided patterns are counted by A335465.
Cf. A034691, A056986, A108917, A124767, A124770, A158005, A269134, A333218, A333222, A333224, A334030.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Union[mstype/@Subsets[stc[n]]]],{n,0,30}]

from itertools import combinations
def comp(n):
    # see A357625
    return
def A335465(n):
    A,B,C = set(),set(),comp(n)
    c = range(len(C))
    for j in c:
        for k in combinations(c, j):
            A.add(tuple(C[i] for i in k))
    for i in A:
        D = {v: rank + 1 for rank, v in enumerate(sorted(set(i)))}
        B.add(tuple(D[v] for v in i))
    return len(B)+1 # John Tyler Rascoe, Mar 12 2025

A344614 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x < y < z or x > y > z.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 30, 58, 110, 209, 397, 753, 1429, 2711, 5143, 9757, 18511, 35117, 66621, 126389, 239781, 454897, 863010, 1637260, 3106138, 5892821, 11179603, 21209446, 40237641, 76337091, 144823431, 274752731, 521249018, 988891100, 1876081530, 3559220898, 6752400377

Offset: 0

Gus Wiseman, May 27 2021

nonn

These compositions avoid the strict consecutive patterns (1,2,3) and (3,2,1), the weak version being A344604.

			The a(6) = 30 compositions are:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (24)  (132)  (1122)  (11121)
       (33)  (141)  (1131)  (11211)
       (42)  (213)  (1212)  (12111)
       (51)  (222)  (1221)  (21111)
             (231)  (1311)
             (312)  (2112)
             (411)  (2121)
                    (2211)
                    (3111)
Missing are: (123), (321).

A001250 counts alternating permutations.
A005649 counts anti-run patterns.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A325534 counts separable partitions.
A325535 counts inseparable partitions.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime factors with twins.
Counting compositions by patterns:
- A003242 avoiding (1,1) adjacent.
- A011782 no conditions.
- A106351 avoiding (1,1) adjacent by sum and length.
- A128695 avoiding (1,1,1) adjacent.
- A128761 avoiding (1,2,3).
- A232432 avoiding (1,1,1).
- A335456 all patterns.
- A335457 all patterns adjacent.
- A335514 matching (1,2,3).
- A344604 weakly avoiding (1,2,3) and (3,2,1) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000041, A006330, A008965, A049774, A056986, A238279/A333755, A333213, A335515, A344612, A344652.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,z_,_}/;xy>z]&]],{n,0,15}]

More terms from Bert Dobbelaere, Jun 12 2021

A052709 Expansion of g.f. (1-sqrt(1-4x-4x^2))/(2*(1+x)).

Original entry on oeis.org

0, 1, 1, 3, 9, 31, 113, 431, 1697, 6847, 28161, 117631, 497665, 2128127, 9183489, 39940863, 174897665, 770452479, 3411959809, 15181264895, 67833868289, 304256253951, 1369404661761, 6182858317823, 27995941060609, 127100310290431, 578433619525633, 2638370120138751

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A simple context-free grammar.
Number of lattice paths from (0,0) to (2n-2,0) that stay (weakly) in the first quadrant and such that each step is either U=(1,1), D=(1,-1), or L=(3,1). Equivalently, underdiagonal lattice paths from (0,0) to (n-1,n-1) and such that each step is either (1,0), (0,1), or (2,1). E.g., a(4)=9 because in addition to the five Dyck paths from (0,0) to (6,0) [UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD] we have LDUD, LUDD, ULDD and UDLD. - Emeric Deutsch, Dec 21 2003
Hankel transform of a(n+1) is A006125(n+1). - Paul Barry, Apr 01 2007
Also, a(n+1) is the number of walks from (0,0) to (n,0) using steps (1,1), (1,-1) and (0,-1). See the U(n,k) array in A071943, where A052709(n+1) = U(n,0). - N. J. A. Sloane, Mar 29 2013
Diagonal sums of triangle in A085880. - Philippe Deléham, Nov 15 2013
From Gus Wiseman, Jun 17 2021: (Start)
Conjecture: For n > 0, also the number of sequences of length n - 1 covering an initial interval of positive integers and avoiding three terms (..., x, ..., y, ..., z, ...) such that x <= y <= z. The version avoiding the strict pattern (1,2,3) is A226316. Sequences covering an initial interval are counted by A000670. The a(1) = 1 through a(4) = 9 sequences are:
  ()  (1)  (1,1)  (1,2,1)
           (1,2)  (1,3,2)
           (2,1)  (2,1,1)
                  (2,1,2)
                  (2,1,3)
                  (2,2,1)
                  (2,3,1)
                  (3,1,2)
                  (3,2,1)
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..499
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Ascending runs in permutations and valued Dyck paths, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.
Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and Michael D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, arXiv:1602.03550 [math.CO], 2016.
Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
James East and Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math., 271 (2003), 29-50.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 664
J. P. S. Kung and A. de Mier, Catalan lattice paths with rook, bishop and spider steps, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - _N. J. A. Sloane_, Dec 27 2012
D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.

Diagonal entries of A071943 and A071945.
Cf. A000108, A000670, A025227, A052709, A056986, A071943, A085880.
Cf. A102726, A117434, A158005, A226316, A333217, A335479.

[0] cat [(&+[Binomial(n,k+1)*Binomial(2*k,n-1): k in [0..n-1]])/n: n in [1..30]]; // G. C. Greubel, May 30 2022

spec := [S,{C=Prod(B,Z),S=Union(B,C,Z),B=Prod(S,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

InverseSeries[Series[(y-y^2)/(1+y^2), {y, 0, 24}], x] (* then A(x)= y(x) *) (* Len Smiley, Apr 12 2000 *)
CoefficientList[Series[(1 -Sqrt[1 -4x -4x^2])/(2(1+x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 12 2016 *)

a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x),n)

[sum(binomial(k, n-k-1)*catalan_number(k) for k in (0..n-1)) for n in (0..30)] # G. C. Greubel, May 30 2022

a(n) + a(n-1) = A025227(n).
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-2-2*k)!/(k!*(n-k)!*(n-1-2*k)!). - Emeric Deutsch, Nov 14 2001
D-finite with recurrence: n*a(n) = (3*n-6)*a(n-1) + (8*n-18)*a(n-2) + (4*n-12)*a(n-3), n>2. a(1)=a(2)=1.
a(n) = b(1)*a(n-1) + b(2)*a(n-2) + ... + b(n-1)*a(1) for n>1 where b(n)=A025227(n).
G.f.: A(x) = x/(1-(1+x)*A(x)). - Paul D. Hanna, Aug 16 2002
G.f.: A(x) = x/(1-z/(1-z/(1-z/(...)))) where z=x+x^2 (continued fraction). - Paul D. Hanna, Aug 16 2002; revised by Joerg Arndt, Mar 18 2011
a(n+1) = Sum_{k=0..n} Catalan(k)*binomial(k, n-k). - Paul Barry, Feb 22 2005
From Paul Barry, Mar 14 2006: (Start)
G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108.
Row sums of A117434. (End)
a(n+1) = (1/(2*Pi))*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*(4+4x-x^2)/(2*(1+x)). - Paul Barry, Apr 01 2007
From Gary W. Adamson, Jul 22 2011: (Start)
For n>0, a(n) is the upper left term in M^(n-1), where M is an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 1, 1, 0, 0, 0, ...
  2, 2, 1, 1, 0, 0, ...
  2, 2, 2, 1, 1, 0, ...
  2, 2, 2, 2, 1, 1, ...
  ... (End)
G.f.: x*Q(0), where Q(k) = 1 + (4*k+1)*x*(1+x)/(k+1 - x*(1+x)*(2*k+2)*(4*k+3)/(2*x*(1+x)*(4*k+3) + (2*k+3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ sqrt(2-sqrt(2))*2^(n-1/2)*(1+sqrt(2))^(n-1)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Jun 29 2013
a(n+1) = Sum_{k=0..floor(n/2)} A085880(n-k,k). - Philippe Deléham, Nov 15 2013

Better g.f. and recurrence from Michael Somos, Aug 03 2000

More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000

cp's OEIS Frontend

A001250 Number of alternating permutations of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Python

Sage

Formula

Extensions

A274174 Number of compositions of n if all summand runs are kept together.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A158423 Number of permutations of 1..n containing the relative rank sequence { 23145 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A335456 Number of normal patterns matched by compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A335465 Number of minimal normal patterns avoided by the n-th composition in standard order (A066099).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A261982 Number of compositions of n with some part repeated.

A052709 Expansion of g.f. (1-sqrt(1-4x-4x^2))/(2*(1+x)).