A232464 -id:A232464 - cp's OEIS frontend

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

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

A243081 Number A(n,k) of compositions of n into parts with multiplicity not larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 3, 0, 1, 1, 2, 3, 3, 0, 1, 1, 2, 4, 7, 5, 0, 1, 1, 2, 4, 7, 11, 11, 0, 1, 1, 2, 4, 8, 15, 21, 13, 0, 1, 1, 2, 4, 8, 15, 26, 34, 19, 0, 1, 1, 2, 4, 8, 16, 31, 52, 59, 27, 0, 1, 1, 2, 4, 8, 16, 31, 57, 93, 114, 57, 0, 1, 1, 2, 4, 8, 16, 32, 63, 114, 173, 178, 65, 0

Offset: 0

Alois P. Heinz, May 29 2014

A(n,k) is the number of compositions of n avoiding the pattern {1}^(k+1).

			Square array A(n,k) begins:
  1,  1,  1,  1,   1,   1,   1,   1,   1, ...
  0,  1,  1,  1,   1,   1,   1,   1,   1, ...
  0,  1,  2,  2,   2,   2,   2,   2,   2, ...
  0,  3,  3,  4,   4,   4,   4,   4,   4, ...
  0,  3,  7,  7,   8,   8,   8,   8,   8, ...
  0,  5, 11, 15,  15,  16,  16,  16,  16, ...
  0, 11, 21, 26,  31,  31,  32,  32,  32, ...
  0, 13, 34, 52,  57,  63,  63,  64,  64, ...
  0, 19, 59, 93, 114, 120, 127, 127, 128, ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A032020, A232432, A232464, A243082, A243083, A243084, A243085, A243086, A243087, A243088.
Main diagonal gives A011782.
A(2n,n) gives A232605.

b:= proc(n, i, p, k) option remember; `if`(n=0, p!, `if`(i<1, 0,
      add(b(n-i*j, i-1, p+j, k)/j!, j=0..min(n/i, k))))
    end:
A:= (n, k)-> `if`(k>=n, `if`(n=0, 1, 2^(n-1)), b(n$2, 0, k)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[n == 0, p!, If[i<1, 0,
     Sum[b[n-i*j, i-1, p+j, k]/j!, {j, 0, Min[n/i, k]}]]];
A[n_, k_] := If[k >= n, If[n == 0, 1, 2^(n-1)], b[n, n, 0, k]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 02 2015, after Alois P. Heinz *)

A(n,k) = Sum_{i=0..k} A242447(n,i).

A080599 Expansion of e.g.f.: 2/(2-2*x-x^2).

Original entry on oeis.org

1, 1, 3, 12, 66, 450, 3690, 35280, 385560, 4740120, 64751400, 972972000, 15949256400, 283232149200, 5416632421200, 110988861984000, 2425817682288000, 56333385828720000, 1385151050307024000, 35950878932544576000, 982196278209226080000, 28175806418228108640000

Offset: 0

Detlef Pauly (dettodet(AT)yahoo.de), Feb 24 2003

Number of ordered partitions of {1,..,n} with at most 2 elements per block. - Bob Proctor, Apr 18 2005
In other words, number of preferential arrangements of n things (see A000670) in which each clump has size 1 or 2. - N. J. A. Sloane, Apr 13 2014
Recurrences (of the hypergeometric type of the Jovovic formula) mean: multiplying the sequence vector from the left with the associated matrix of the recurrence coefficients (here: an infinite lower triangular matrix with the natural numbers in the main diagonal and the triangular series in the subdiagonal) recovers the sequence up to an index shift. In that sense, this sequence here and many other sequences of the OEIS are eigensequences. - Gary W. Adamson, Feb 14 2011
Number of intervals in the weak (Bruhat) order of S_n that are Boolean algebras. - Richard Stanley, May 09 2011
a(n) = D^n(1/(1-x)) evaluated at x = 0, where D is the operator sqrt(1+2*x)*d/dx. Cf. A000085, A005442 and A052585. - Peter Bala, Dec 07 2011
From Gus Wiseman, Jul 04 2020: (Start)
Also the number of (1,1,1)-avoiding or cubefree sequences of length n covering an initial interval of positive integers. For example, the a(0) = 1 through a(3) = 12 sequences are:
  ()  (1)  (11)  (112)
           (12)  (121)
           (21)  (122)
                 (123)
                 (132)
                 (211)
                 (212)
                 (213)
                 (221)
                 (231)
                 (312)
                 (321)
(End)

			From _Gus Wiseman_, Jul 04 2020: (Start)
The a(0) = 1 through a(3) = 12 ordered set partitions with block sizes <= 2 are:
  {}  {{1}}  {{1,2}}    {{1},{2,3}}
             {{1},{2}}  {{1,2},{3}}
             {{2},{1}}  {{1,3},{2}}
                        {{2},{1,3}}
                        {{2,3},{1}}
                        {{3},{1,2}}
                        {{1},{2},{3}}
                        {{1},{3},{2}}
                        {{2},{1},{3}}
                        {{2},{3},{1}}
                        {{3},{1},{2}}
                        {{3},{2},{1}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Alex Bradt, Jennifer Elder, Pamela E. Harris, Gordon Rojas Kirby, Eva Reutercrona, Yuxuan (Susan) Wang, and Juliet Whidden, Unit interval parking functions and the r-Fubini numbers, arXiv:2401.06937 [math.CO], 2024. See page 10.
Jennifer Elder, Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Boolean intervals in the weak order of S_n, arXiv:2306.14734 [math.CO], 2023.
Laura Gellert and Raman Sanyal, On degree sequences of undirected, directed, and bidirected graphs, arXiv preprint arXiv:1512.08448 [math.CO], 2015.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 36.
Harri Hakula, Helmut Harbrecht, Vesa Kaarnioja, Frances Y. Kuo, and Ian H. Sloan, Uncertainty quantification for random domains using periodic random variables, arXiv:2210.17329 [math.NA], 2022.
Dixy Msapato, Counting the number of tau-exceptional sequences over Nakayama algebras, arXiv:2002.12194 [math.RT], 2020.
Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Index entries for related partition-counting sequences

Cf. A000085, A000670, A002530, A002605, A005442, A052585, A052611.
Cf. A090932, A102726, A106356, A232464, A333755, A335455, A335456.
Column k=2 of A276921.
Cubefree numbers are A004709.
(1,1)-avoiding patterns are A000142.
(1,1,1)-avoiding compositions are A232432.
(1,1,1)-matching patterns are A335508.
(1,1,1)-avoiding permutations of prime indices are A335511.
(1,1,1)-avoiding compositions are ranked by A335513.
(1,1,1,1)-avoiding patterns are A189886.

[n le 2 select 1 else (n-1)*Self(n-1) + Binomial(n-1,2)*Self(n-2): n in [1..31]]; // G. C. Greubel, Jan 31 2023

a:= n-> n! *(Matrix([[1,1], [1/2,0]])^n)[1,1]:
seq(a(n), n=0..40);  # Alois P. Heinz, Jun 01 2009
a:= gfun:-rectoproc({a(n) = n*a(n-1)+(n*(n-1)/2)*a(n-2),a(0)=1,a(1)=1},a(n),remember):
seq(a(n), n=0..40); # Robert Israel, Nov 01 2015

Table[n!*SeriesCoefficient[-2/(-2+2*x+x^2),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 13 2012 *)
Round@Table[n! ((1+Sqrt[3])^(n+1) - (1-Sqrt[3])^(n+1))/(2^(n+1) Sqrt[3]), {n, 0, 20}] (* Vladimir Reshetnikov, Oct 31 2015 *)

Vec(serlaplace((2/(2-2*x-x^2) + O(x^30)))) \\ Michel Marcus, Nov 02 2015

A002605=BinaryRecurrenceSequence(2,2,0,1)
def A080599(n): return factorial(n)*A002605(n+1)/2^n
[A080599(n) for n in range(41)] # G. C. Greubel, Jan 31 2023

a(n) = n*a(n-1) + (n*(n-1)/2)*a(n-2). - Vladeta Jovovic, Aug 22 2003
E.g.f.: 1/(1-x-x^2/2). - Richard Stanley, May 09 2011
a(n) ~ n!*((1+sqrt(3))/2)^(n+1)/sqrt(3). - Vaclav Kotesovec, Oct 13 2012
a(n) = n!*((1+sqrt(3))^(n+1) - (1-sqrt(3))^(n+1))/(2^(n+1)*sqrt(3)). - Vladimir Reshetnikov, Oct 31 2015
a(n) = A090932(n) * A002530(n+1). - Robert Israel, Nov 01 2015

A232432 Number of compositions of n avoiding the pattern 111.

Original entry on oeis.org

1, 1, 2, 3, 7, 11, 21, 34, 59, 114, 178, 284, 522, 823, 1352, 2133, 3739, 5807, 9063, 14074, 23639, 36006, 56914, 87296, 131142, 214933, 324644, 487659, 739291, 1108457, 1724673, 2558386, 3879335, 5772348, 8471344, 12413666, 19109304, 27886339, 40816496

Offset: 0

Alois P. Heinz, Nov 23 2013

nonn

Number of compositions of n into parts with multiplicity <= 2.

			a(4) = 7: [4], [3,1], [2,2], [1,3], [2,1,1], [1,2,1], [1,1,2].
a(5) = 11: [5], [4,1], [3,2], [2,3], [1,4], [3,1,1], [2,2,1], [1,3,1], [2,1,2], [1,2,2], [1,1,3].
a(6) = 21: [6], [4,2], [3,3], [5,1], [2,4], [1,5], [2,1,3], [1,2,3], [1,1,4], [4,1,1], [3,2,1], [2,3,1], [1,4,1], [3,1,2], [1,3,2], [1,2,2,1], [2,1,1,2], [1,2,1,2], [1,1,2,2], [2,2,1,1], [2,1,2,1].

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

Cf. A000726 (partitions avoiding 111), A032020 (pattern 11), A128695 (adjacent pattern 111).
Column k=2 of A243081.
The case of partitions is ranked by A004709.
The version for patterns is A080599.
(1,1,1,1)-avoiding partitions are counted by A232464.
The (1,1,1)-matching version is A335455.
Patterns matched by compositions are counted by A335456.
The version for prime indices is A335511.
(1,1,1)-avoiding compositions are ranked by A335513.
Cf. A011782, A006918, A102726, A106356, A238279, A333755.

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

f[list_]:=Apply[And,Table[Count[list,i]<3,{i,1,Max[list]}]];
g[list_]:=Length[list]!/Apply[Times,Table[Count[list,i]!,{i,1,Max[list]}]];
a[n_] := If[n == 0, 1, Total[Map[g, Select[IntegerPartitions[n], f]]]];
Table[a[n], {n, 0, 35}] (* Geoffrey Critzer, Nov 25 2013, updated by Jean-François Alcover, Nov 20 2023 *)

A335471 Number of compositions of n avoiding the pattern (1,2,1).

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 23, 40, 67, 115, 190, 311, 505, 807, 1285, 2031, 3164, 4896, 7550, 11499, 17480, 26379, 39558, 58946, 87469, 129051, 189484, 277143, 403477, 584653, 844236, 1213743, 1738372, 2481770, 3528698, 5003364, 7070225, 9958387, 13982822, 19580613, 27333403

Offset: 0

Gus Wiseman, Jun 17 2020

nonn

Also the number of (1,1,2)-avoiding or (2,1,1)-avoiding compositions.
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).
A composition of n is a finite sequence of positive integers summing to n.

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (13)    (14)
                 (21)   (22)    (23)
                 (111)  (31)    (32)
                        (112)   (41)
                        (211)   (113)
                        (1111)  (122)
                                (212)
                                (221)
                                (311)
                                (1112)
                                (2111)
                                (11111)

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

The version for patterns is A001710.
The version for prime indices is A335449.
These compositions are ranked by A335467.
The complement A335470 is the matching version.
The (2,1,2)-avoiding version is A335473.
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.
Compositions avoiding (1,2,3) are counted by A102726.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A056986, A106356, A232464, A238279, A333213, A333755.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,_,y_,_,x_,_}/;x

a(n)={local(Cache=Map()); my(F(n,m,k)=if(m>n, m=n); if(m==0, n==0, my(hk=[n,m,k], z); if(!mapisdefined(Cache,hk,&z), z=self()(n,m-1,k) + k*sum(i=1,n\m, self()(n-i*m, m-1, k+i)); mapput(Cache, hk, z)); z)); F(n,n,1)} \\ Andrew Howroyd, Dec 31 2020

a(n > 0) = 2^(n - 1) - A335470(n).

a(n) = F(n,n,1) where F(n,m,k) = F(n,m-1,k) + k*(Sum_{i=1..floor(n/m)} F(n-i*m, m-1, k+i)) for m > 0 with F(0,m,k)=1 and F(n,0,k)=0 otherwise. - Andrew Howroyd, Dec 31 2020

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A335473 Number of compositions of n avoiding the pattern (2,1,2).

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 29, 55, 103, 190, 347, 630, 1134, 2028, 3585, 6291, 10950, 18944, 32574, 55692, 94618, 159758, 268147, 447502, 743097, 1227910, 2020110, 3308302, 5394617, 8757108, 14155386, 22784542, 36529813, 58343498, 92850871, 147254007, 232750871, 366671436

Offset: 0

Gus Wiseman, Jun 17 2020

nonn

Also the number of (1,2,2) or (2,2,1)-avoiding compositions.
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).
A composition of n is a finite sequence of positive integers summing to n.

			The a(0) = 1 through a(5) = 15 compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (13)    (14)
                 (21)   (22)    (23)
                 (111)  (31)    (32)
                        (112)   (41)
                        (121)   (113)
                        (211)   (122)
                        (1111)  (131)
                                (221)
                                (311)
                                (1112)
                                (1121)
                                (1211)
                                (2111)
                                (11111)

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

The version for patterns is A001710.
The version for prime indices is A335450.
These compositions are ranked by A335469.
The (1,2,1)-avoiding version is A335471.
The complement A335472 is the matching version.
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.
Compositions avoiding (1,2,3) are counted by A102726.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A261982, A034691, A056986, A106356, A232464, A238279, A333755.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,_,y_,_,x_,_}/;x>y]&]],{n,0,10}]

a(n)={local(Cache=Map()); my(F(n,m,k) = if(m>n, n==0, my(hk=[n,m,k], z); if(!mapisdefined(Cache,hk,&z), z=self()(n,m+1,k) + k*sum(i=1,n\m, self()(n-i*m, m+1, k+i)); mapput(Cache, hk, z)); z)); F(n,1,1)} \\ Andrew Howroyd, Dec 31 2020

a(n > 0) = 2^(n - 1) - A335472(n).

a(n) = F(n,1,1) where F(n,m,k) = F(n,m+1,k) + k*(Sum_{i=1..floor(n/m)} F(n-i*m, m+1, k+i)) for m <= n with F(0,m,k)=1 and F(n,m,k)=0 otherwise. - Andrew Howroyd, Dec 31 2020

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A335455 Number of compositions of n with some part appearing more than twice.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 11, 30, 69, 142, 334, 740, 1526, 3273, 6840, 14251, 29029, 59729, 122009, 248070, 500649, 1012570, 2040238, 4107008, 8257466, 16562283, 33229788, 66621205, 133478437, 267326999, 535146239, 1071183438, 2143604313, 4289194948, 8581463248

Offset: 0

Gus Wiseman, Jun 15 2020

nonn

Also the number of compositions of n matching the pattern (1,1,1).

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

			The a(3) = 1 through a(6) = 11 compositions:
  (111)  (1111)  (1112)   (222)
                 (1121)   (1113)
                 (1211)   (1131)
                 (2111)   (1311)
                 (11111)  (3111)
                          (11112)
                          (11121)
                          (11211)
                          (12111)
                          (21111)
                          (111111)

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

The case of partitions is A000726.
The avoiding version is A232432.
The (1,1)-matching version is A261982.
The version for patterns is A335508.
The version for prime indices is A335510.
These compositions are ranked by A335512.
Compositions are counted by A011782.
Combinatory separations are counted by A269134.
Normal patterns matched by compositions are counted by A335456.
Cf. A000740, A034691, A056986, A080599, A106356, A181796, A232464, A238279, A333755.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Max@@Length/@Split[Sort[#]]>=3&]],{n,0,10}]

a(n > 0) = 2^(n - 1) - A232432(n).

A335508 Number of patterns of length n matching the pattern (1,1,1).

Original entry on oeis.org

0, 0, 0, 1, 9, 91, 993, 12013, 160275, 2347141, 37496163, 649660573, 12142311195, 243626199181, 5224710549243, 119294328993853, 2889836999693355, 74037381200415901, 2000383612949821323, 56850708386783835133, 1695491518035158123115, 52949018580275965241821

Offset: 0

Gus Wiseman, Jun 18 2020

nonn

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 a(3) = 1 through a(4) = 9 patterns:
  (1,1,1)  (1,1,1,1)
           (1,1,1,2)
           (1,1,2,1)
           (1,2,1,1)
           (1,2,2,2)
           (2,1,1,1)
           (2,1,2,2)
           (2,2,1,2)
           (2,2,2,1)

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

The complement A080599 is the avoiding version.
Permutations of prime indices matching this pattern are counted by A335510.
Compositions matching this pattern are counted by A335455 and ranked by A335512.
Patterns are counted by A000670 and ranked by A333217.
Patterns matching the pattern (1,1) are counted by A019472.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Patterns matching (1,2,3) are counted by A335515.
Cf. A034691, A056986, A232464, A238279, A292884, A333175, A333755, A335451, A335456, A335457, A335458.
Cf. A276922.

b:= proc(n, k) option remember; `if`(n=0, 1, add(
      b(n-i, k)*binomial(n, i), i=1..min(n, k)))
    end:
a:= n-> b(n$2)-b(n, 2):
seq(a(n), n=0..21);  # Alois P. Heinz, Jan 28 2024

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],MatchQ[#,{_,x_,_,x_,_,x_,_}]&]],{n,0,6}]

a(n) = Sum_{k=3..n} A276922(n,k). - Alois P. Heinz, Jan 28 2024

a(n) = A000670(n) - A080599(n). - Andrew Howroyd, Jan 28 2024

a(9)-a(21) from Alois P. Heinz, Jan 28 2024

A232394 The number of compositions of n with no more than 3 consecutive identical parts (summands).

Original entry on oeis.org

1, 1, 2, 4, 7, 15, 29, 57, 111, 218, 429, 841, 1651, 3239, 6355, 12473, 24475, 48029, 94249, 184946, 362932, 712194, 1397569, 2742507, 5381729, 10560797, 20723884, 40667338, 79803197, 156601100, 307304821, 603036937, 1183364302, 2322164658, 4556879623

Offset: 0

Geoffrey Critzer, Nov 23 2013

nonn

			a(6) = 29 because there are 32 compositions of 6 but we exclude: 1+1+1+1+1+1, 1+1+1+1+2, 2+1+1+1+1.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A003242, A128695, A232464.

b:= proc(n, t, c) option remember;
       `if`(n=0, 1, add(`if`(t<>j, b(n-j, j, 1),
       `if`(c<3, b(n-j, j, c+1), 0)), j=1..n))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 24 2013

nn=34; CoefficientList[Series[1/(1-Sum[(z^j+z^(2j)+z^(3j))/(1+z^j+z^(2j)+z^(3j)),{j,1,nn}]),{z,0,nn}],z]

The g.f. for the number of compositions of n with no more than m consecutive identical parts is 1/( 1 - sum_{j>=1} x^j*(1 - x^(j*m))/(1 - x^j)/ (1 + x^j*(1 - x^(j*m))/(1 - x^j)) ); set m = 3 for this sequence.

a(n) ~ c * d^n, where d=1.962341312018097075518216734398388302205091029921968626465436021267458..., c=0.506212613637348069558928622560083229757824786467201325660889396545904... - Vaclav Kotesovec, May 01 2014

A243120 Number of compositions of n in which the maximal multiplicity of parts equals 3.

Original entry on oeis.org

1, 0, 4, 5, 18, 34, 59, 132, 272, 519, 966, 1746, 3487, 5986, 10570, 19701, 34444, 59250, 101155, 180588, 302788, 515205, 841042, 1449392, 2420163, 3959442, 6472636, 10656987, 17332640, 28234296, 45337971, 72306544, 117761744, 185704091, 295918788, 466574348

Offset: 3

Alois P. Heinz, May 29 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..1000

Column k=3 of A242447.

b:= proc(n, i, p, k) option remember; `if`(n=0, p!, `if`(i<1, 0,
      add(b(n-i*j, i-1, p+j, k)/j!, j=0..min(n/i, k))))
    end:
a:= n-> b(n$2, 0, 3) -b(n$2, 0, 2):
seq(a(n), n=3..50);

a(n) = A232464(n) - A232432(n) = A243081(n,3) - A243081(n,2).

cp's OEIS Frontend

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

A243081 Number A(n,k) of compositions of n into parts with multiplicity not larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A080599 Expansion of e.g.f.: 2/(2-2*x-x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A232432 Number of compositions of n avoiding the pattern 111.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A335471 Number of compositions of n avoiding the pattern (1,2,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A335473 Number of compositions of n avoiding the pattern (2,1,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A335455 Number of compositions of n with some part appearing more than twice.