A080599 -id:A080599 - cp's OEIS frontend

A335513 Numbers k such that the k-th composition in standard order (A066099) avoids the pattern (1,1,1).

0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 35, 36, 37, 38, 40, 41, 43, 44, 45, 46, 48, 49, 50, 52, 53, 54, 56, 58, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 80, 81, 82, 83, 84, 88, 89

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

These are compositions with no part appearing more than twice.
A composition of n is a finite sequence of positive integers summing to n. 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.
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 sequence of terms together with the corresponding compositions begins:
   0: ()         17: (4,1)      37: (3,2,1)
   1: (1)        18: (3,2)      38: (3,1,2)
   2: (2)        19: (3,1,1)    40: (2,4)
   3: (1,1)      20: (2,3)      41: (2,3,1)
   4: (3)        21: (2,2,1)    43: (2,2,1,1)
   5: (2,1)      22: (2,1,2)    44: (2,1,3)
   6: (1,2)      24: (1,4)      45: (2,1,2,1)
   8: (4)        25: (1,3,1)    46: (2,1,1,2)
   9: (3,1)      26: (1,2,2)    48: (1,5)
  10: (2,2)      28: (1,1,3)    49: (1,4,1)
  11: (2,1,1)    32: (6)        50: (1,3,2)
  12: (1,3)      33: (5,1)      52: (1,2,3)
  13: (1,2,1)    34: (4,2)      53: (1,2,2,1)
  14: (1,1,2)    35: (4,1,1)    54: (1,2,1,2)
  16: (5)        36: (3,3)      56: (1,1,4)

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

These compositions are counted by A232432 (by sum).
The (1,1)-avoiding version is A233564.
The complement A335512 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.
Patterns avoiding (1,1,1) are counted by A080599 (by length).
Non-unimodal compositions are counted by A115981 and ranked by A335373.
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.
Permutations of prime indices avoiding (1,1,1) are counted by A335511.
Cf. A034691, A056986, A108917, A114994, A238279, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],!MatchQ[stc[#],{_,x_,_,x_,_,x_,_}]&]

A052611 Expansion of e.g.f. 1/(1-2x-2x^2).

Original entry on oeis.org

1, 2, 12, 96, 1056, 14400, 236160, 4515840, 98703360, 2426941440, 66305433600, 1992646656000, 65328154214400, 2320237766246400, 88746105588940800, 3636883029491712000, 158978387626426368000, 7383729547341987840000

Offset: 0

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

G. C. Greubel, Table of n, a(n) for n = 0..380
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 556

Cf. A002605, A080599.

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

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

With[{nn=20},CoefficientList[Series[1/(1-2x-2x^2),{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Apr 14 2015 *)
Table[n!*(-I*Sqrt[2])^(n)*ChebyshevU[n,I/Sqrt[2]], {n,0,40}] (* G. C. Greubel, Jan 31 2023 *)

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

E.g.f.: 1/(1 - 2*x - 2*x^2).
a(n) = 2^n * A080599(n).
a(n) = 2*n*a(n+1) + 2*n*(n-1)*a(n), a(0) = 1, a(1) = 2.
a(n) = (n!/6) * Sum_{p = RootOf(2*z^2+2*z-1)} (1+2*p)*p^(-n-1).
a(n) = n!*A002605(n+1). - R. J. Mathar, Nov 27 2011

A240798 Total number of occurrences of the pattern 1=2=3 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 0, 1, 12, 130, 1500, 18935, 262248, 3972612, 65500200, 1169398065, 22494463860, 464072915878, 10225330604580, 239720548513355, 5959152063448080, 156592569864940040, 4337574220496785680, 126329273251232688069, 3859509516112803668220, 123426111134706786806890

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.

The number that avoid the pattern 1=2=3 is given in A080599.

Alois P. Heinz, Table of n, a(n) for n = 1..420

Cf. A000670, A240763, A240796-A240800, A080599.

b:= proc(n) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*binomial(j, 3)])(b(n-j))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_] := b[n] = If[n==0, {1, 0}, Sum[Function[p, p+{0, p[[1]]*Binomial[j, 3]} ][b[n-j]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Feb 28 2017, after Alois P. Heinz *)

a(n) ~ n! * n / (12 * (log(2))^(n-1)). - Vaclav Kotesovec, May 03 2015

a(8)-a(21) from Alois P. Heinz, Dec 08 2014

A320758 Number of ordered set partitions of [n] where the maximal block size equals two.

Original entry on oeis.org

1, 6, 42, 330, 2970, 30240, 345240, 4377240, 61122600, 933055200, 15470254800, 277005128400, 5329454130000, 109681187616000, 2404894892400000, 55977698400624000, 1378748676601296000, 35829233832135744000, 979763376201049440000, 28124715476056399200000

Offset: 2

Alois P. Heinz, Oct 20 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..428

Column k=2 of A276922.

Cf. A000142, A080599.

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-> (k-> b(n, k) -b(n, k-1))(2):
seq(a(n), n=2..25);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - i, k] Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := With[{k = 2}, b[n, k] - b[n, k-1]];
a /@ Range[2, 25] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

E.g.f.: 1/(1-Sum_{i=1..2} x^i/i!) - 1/(1-x).

A(n) = A080599(n) - A000142(n).

A320759 Number of ordered set partitions of [n] where the maximal block size equals three.

Original entry on oeis.org

1, 8, 80, 860, 10290, 136080, 1977360, 31365600, 539847000, 10026139200, 199937337600, 4262167509600, 96744738090000, 2329950823200000, 59348032327584000, 1594257675506496000, 45047749044458160000, 1335740755933584000000, 41473196779273459200000

Offset: 3

Alois P. Heinz, Oct 20 2018

nonn

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

Column k=3 of A276922.

Cf. A080599, A189886.

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-> (k-> b(n, k) -b(n, k-1))(3):
seq(a(n), n=3..25);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - i, k] Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := With[{k = 3}, b[n, k] - b[n, k-1]];
a /@ Range[3, 25] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

E.g.f.: 1/(1-Sum_{i=1..3} x^i/i!) - 1/(1-Sum_{i=1..2} x^i/i!).

a(n) = A189886(n) - A080599(n).

A355293 Expansion of e.g.f. 1 / (1 - x - x^2/2 - x^3/3).

Original entry on oeis.org

1, 1, 3, 14, 82, 610, 5450, 56700, 674520, 9027480, 134236200, 2195701200, 39180094800, 757389032400, 15767305554000, 351689317980000, 8367381470448000, 211518767796336000, 5661504152255952000, 159954273475764768000, 4757034049019572320000, 148547713504322452320000, 4859583724723970642400000

Offset: 0

Ilya Gutkovskiy, Jun 27 2022

nonn

Cf. A007840, A057693, A080599, A189886, A355294.

nmax = 22; CoefficientList[Series[1/(1 - x - x^2/2 - x^3/3), {x, 0, nmax}], x] Range[0, nmax]!
a[0] = a[1] = 1; a[2] = 3; a[n_] := a[n] = n a[n - 1] + n (n - 1) a[n - 2]/2 + n (n - 1) (n - 2) a[n - 3]/3; Table[a[n], {n, 0, 22}]

a(n) = n * a(n-1) + n * (n-1) * a(n-2) / 2 + n * (n-1) * (n-2) * a(n-3) / 3.

A355294 Expansion of e.g.f. 1 / (1 - x - x^2/2 - x^3/3 - x^4/4).

Original entry on oeis.org

1, 1, 3, 14, 88, 670, 6170, 66360, 815640, 11272800, 173132400, 2925014400, 53909394000, 1076365290000, 23144112591600, 533193460800000, 13102608591072000, 342105146182800000, 9457689380931792000, 275988880808825184000, 8477631163592791200000, 273430368958004818560000, 9238944655686318693120000

Offset: 0

Ilya Gutkovskiy, Jun 27 2022

nonn

Cf. A007840, A070945, A080599, A276924, A355293.

nmax = 22; CoefficientList[Series[1/(1 - x - x^2/2 - x^3/3 - x^4/4), {x, 0, nmax}], x] Range[0, nmax]!
a[0] = a[1] = 1; a[2] = 3; a[3] = 14; a[n_] := a[n] = n a[n - 1] + n (n - 1) a[n - 2]/2 + n (n - 1) (n - 2) a[n - 3]/3 + n (n - 1) (n - 2) (n - 3) a[n - 4]/4; Table[a[n], {n, 0, 22}]

a(n) = n * a(n-1) + n * (n-1) * a(n-2) / 2 + n * (n-1) * (n-2) * a(n-3) / 3 + n * (n-1) * (n-2) * (n-3) * a(n-4) / 4.

A328286 Expansion of e.g.f. -log(1 - x - x^2/2).

Original entry on oeis.org

1, 2, 5, 21, 114, 780, 6390, 61110, 667800, 8210160, 112152600, 1685237400, 27624920400, 490572482400, 9381882510000, 192238348302000, 4201639474032000, 97572286427616000, 2399151995223984000, 62268748888378032000, 1701213856860117600000

Offset: 1

Ilya Gutkovskiy, Oct 11 2019

nonn

Cf. A009014, A039647, A080040, A080599 (exponential transform).

b:= proc(n) b(n):= n! * (<<1|1>, <1/2|0>>^n)[1, 1] end:
a:= proc(n) option remember; `if`(n=0, 0, b(n)-add(
      binomial(n, j)*j*b(n-j)*a(j), j=1..n-1)/n)
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Oct 11 2019

nmax = 21; CoefficientList[Series[-Log[1 - x - x^2/2], {x, 0, nmax}], x] Range[0, nmax]! // Rest
FullSimplify[Table[(n - 1)! ((1 - Sqrt[3])^n + (1 + Sqrt[3])^n)/2^n, {n, 1, 21}]]

my(x='x+O('x^25)); Vec(serlaplace(-log(1 - x - x^2/2))) \\ Michel Marcus, Oct 11 2019

a(n) = (n - 1)! * ((1 - sqrt(3))^n + (1 + sqrt(3))^n) / 2^n.

D-finite with recurrence +2*a(n) +2*(-n+1)*a(n-1) -(n-1)*(n-2)*a(n-2)=0. - R. J. Mathar, Aug 20 2021

A346224 a(n) = (n!)^2 * Sum_{k=0..floor(n/2)} 1 / ((n-2k)! 4^k * k!).

Original entry on oeis.org

1, 1, 3, 15, 114, 1170, 15570, 256410, 5103000, 119773080, 3264445800, 101784097800, 3591396824400, 141958074258000, 6236035482877200, 302218901402418000, 16060366291617648000, 930654556409161584000, 58524794739862410960000, 3976525824684785163792000

Offset: 0

Ilya Gutkovskiy, Jul 16 2021

Cf. A000085, A000898, A023998, A080599, A239840.

Table[(n!)^2 Sum[1/((n - 2 k)! 4^k k!), {k, 0, Floor[n/2]}], {n, 0, 19}]
nmax = 19; CoefficientList[Series[Exp[x + x^2/4], {x, 0, nmax}], x] Range[0, nmax]!^2

a(n) = (n!)^2 * sum(k=0, n\2, 1/((n-2*k)!*4^k*k!)); \\ Michel Marcus, Jul 17 2021

Sum_{n>=0} a(n) * x^n / (n!)^2 = exp( x + x^2 / 4 ).
a(n) = n! * Sum_{k=0..n} Stirling1(n,k) * Bell(k) / 2^(n-k).
D-finite with recurrence a(0) = a(1) = 1; a(n) = n * a(n-1) + n * (n-1)^2 * a(n-2) / 2.
a(n) ~ sqrt(Pi) * n^((3*n + 1)/2) / (2^(n/2) * exp((3*n + 1)/2 - sqrt(2*n))). - Vaclav Kotesovec, Jul 17 2021

cp's OEIS Frontend

A335513 Numbers k such that the k-th composition in standard order (A066099) avoids the pattern (1,1,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A052611 Expansion of e.g.f. 1/(1-2*x-2*x^2).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A240798 Total number of occurrences of the pattern 1=2=3 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A320758 Number of ordered set partitions of [n] where the maximal block size equals two.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320759 Number of ordered set partitions of [n] where the maximal block size equals three.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A355293 Expansion of e.g.f. 1 / (1 - x - x^2/2 - x^3/3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A355294 Expansion of e.g.f. 1 / (1 - x - x^2/2 - x^3/3 - x^4/4).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A328286 Expansion of e.g.f. -log(1 - x - x^2/2).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

A052611 Expansion of e.g.f. 1/(1-2x-2x^2).

A346224 a(n) = (n!)^2 * Sum_{k=0..floor(n/2)} 1 / ((n-2k)! 4^k * k!).