A261489 -id:A261489 - cp's OEIS frontend

A261041 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in different parts.

1, 2, 4, 10, 29, 97, 366, 1534, 7050, 35167, 188835, 1084180, 6618472, 42756208, 291120551, 2081922515, 15590248868, 121920095674, 993343650912, 8414029179365, 73953763887277, 673316834487162, 6340176007793060, 61657373569634586, 618445940056365121

Offset: 0

Alois P. Heinz, Aug 09 2015

nonn

From Gus Wiseman, Nov 25 2019: (Start)
Conjecture: Also the number of set partitions of {1, ..., n + 1} where, if x and x + 2 belong to the same block, then so does x + 1. For example, the a(0) = 1 through a(3) = 10 set partitions are:
  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}
         {{1},{2}}  {{1},{2,3}}    {{1},{2,3,4}}
                    {{1,2},{3}}    {{1,2},{3,4}}
                    {{1},{2},{3}}  {{1,2,3},{4}}
                                   {{1,4},{2,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{2,3},{4}}
                                   {{1,2},{3},{4}}
                                   {{1,4},{2},{3}}
                                   {{1},{2},{3},{4}}
(End)

			For n=3 the a(3) = 10 partitions are {}, 1, 2, 3, 1|2, 13, 1|3, 2|3, 13|2, 1|2|3.
From _Gus Wiseman_, Nov 25 2019: (Start)
The a(0) = 1 through a(3) = 10 set partitions:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{2}}      {{2}}
             {{1},{2}}  {{3}}
                        {{1,3}}
                        {{1},{2}}
                        {{1},{3}}
                        {{2},{3}}
                        {{1,3},{2}}
                        {{1},{2},{3}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..576
Notamathematician et al., Generating function for A261041, MathOverflow, 2024.

Cf. A000110, A003242, A114901, A247100, A261134, A261489, A261492, A273461, A274174.

Partial sums of A376077.

g:= proc(n, l, t) option remember; `if`(n=0, 1, add(`if`(l>0
      and j=l, 0, g(n-1, j, `if`(j=t, t+1, t))), j=0..t))
    end:
a:= n-> g(n, 0, 1):
seq(a(n), n=0..30);

g[n_, l_, t_] := g[n, l, t] = If[n==0, 1, Sum[If[l>0 && j==l, 0, g[n-1, j, If[j==t, t+1, t]]], {j, 0, t}]]; a[n_] := g[n, 0, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 04 2017, translated from Maple *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[Join@@sps/@Subsets[Range[n]],!MemberQ[#,{_,x_,y_,_}/;x+1==y]&]],{n,0,6}] (* Gus Wiseman, Nov 25 2019 *)

a261041(n) = sum(k=0,n, sum(j=0,k,stirling(k,j,2)) * sum(j=0,(n-k)\2, binomial(k+j-1,j))); \\ Max Alekseyev, Sep 08 2024

From Max Alekseyev, Sep 08 2024: (Start)
a(n) = Sum_{k=0..n} A000110(k) * Sum_{j=0..[(n-k)/2]} binomial(k+j-1,j).
G.f.: 1/(1-x) * Sum_{k>=0} A000110(k) * (x/(1-x^2))^k. (End)

A247100 The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation.

Original entry on oeis.org

1, 2, 4, 9, 21, 51, 127, 324, 844, 2243, 6073, 16737, 46905, 133556, 386062, 1132107, 3365627, 10137559, 30920943, 95457178, 298128278, 941574417, 3006040523, 9697677885, 31602993021, 104001763258, 345524136076, 1158570129917, 3919771027105, 13377907523151

Offset: 0

Andrew Woods, Jan 01 2015

nonn

Also the number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in the same part. Example: For n=3 the a(3)=9 partitions are {}, 1, 2, 3, 12, 23, 13, 1|3, 123. - Don Knuth, Aug 07 2015

			The labeled-run binary strings can be written as follows.
For n=1: 0, 1.
For n=2: 00, 01, 10, 11.
For n=3: 000, 001, 010, 100, 011, 110, 111, 101, 102.
For n=4: 0000, 0001, 0010, 0100, 1000, 0011, 0110, 1100, 0111, 1110, 1111, 0101, 0102, 1001, 1002, 1010, 1020, 1011, 1022, 1101, 1102.
For n=5, the original binary string 10101 can be written as 10101, 10102, 10201, 10202, or 10203 because there are 3 runs of ones and Bell(3)=5.

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

Cf. A000110, A243634, A253409, A255706, A261041, A261134, A261489, A261492.

with(combinat):
a:= n-> (t-> add(binomial(t, 2*j)*bell(j), j=0..t/2))(n+1):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 10 2015

Table[1 + Sum[Binomial[n+1,2*k] * BellB[k],{k,1,Ceiling[n/2]}],{n,1,40}] (* Vaclav Kotesovec, Jan 08 2015 after Andrew Woods *)

a(n) = 1 + Sum_{k=1..ceiling(n/2)} binomial(n+1, 2k)*Bell(k), where Bell(x) refers to Bell numbers (A000110).

a(0)=1 prepended by Alois P. Heinz, Aug 08 2015

A261134 Number of partitions of subsets s of {1,...,n}, where all integers belonging to a run of consecutive members of s are required to be in different parts.

Original entry on oeis.org

1, 2, 4, 9, 23, 66, 209, 722, 2697, 10825, 46429, 211799, 1023304, 5217048, 27974458, 157310519, 925326848, 5680341820, 36315837763, 241348819913, 1664484383610, 11893800649953, 87931422125632, 671699288516773, 5295185052962371, 43029828113547685

Offset: 0

Alois P. Heinz, Aug 10 2015

nonn

			a(3) = 9: {}, 1, 2, 3, 1|2, 2|3, 13, 1|3, 1|2|3.
a(4) = 23: {}, 1, 2, 3, 4, 1|2, 1|3, 13, 1|4, 14, 2|3, 2|4, 24, 3|4, 1|2|3, 1|2|4, 1|24, 14|2, 1|3|4, 13|4, 14|3, 2|3|4, 1|2|3|4.

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

Cf. A247100, A261041, A261489, A261492.

g:= proc(n, s, t) option remember; `if`(n=0, 1, add(
      `if`(j in s, 0, g(n-1, `if`(j=0, {}, s union {j}),
      `if`(j=t, t+1, t))), j=0..t))
    end:
a:= n-> g(n, {}, 1):
seq(a(n), n=0..20);

g[n_, s_List, t_] := g[n, s, t] = If[n == 0, 1, Sum[If[MemberQ[s, j], 0, g[n-1, If[j == 0, {}, s ~Union~ {j}], If[j == t, t+1, t]]], {j, 0, t}]]; a[n_] := g[n, {}, 1]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 04 2017, translated from Maple *)

A261492 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in the same part and the elements of {1, n} are required to be in the same part if they are both members of a subset.

Original entry on oeis.org

1, 2, 4, 8, 18, 42, 102, 254, 648, 1688, 4486, 12146, 33474, 93810, 267112, 772124, 2264214, 6731254, 20275118, 61841886, 190914356, 596256556, 1883148834, 6012081046, 19395355770, 63205986042, 208003526516, 691048272152, 2317140259834, 7839542054210

Offset: 0

Alois P. Heinz, Aug 21 2015

nonn

			a(3) = 8: {}, 1, 2, 3, 12, 23, 13, 123.
a(4) = 18: {}, 1, 2, 3, 4, 12, 13, 1|3, 14, 23, 24, 2|4, 34, 123, 124, 134, 234, 1234.

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

Cf. A000110, A247100, A261134, A261041, A261489.

with(combinat):
a:= n-> `if`(n=0, 1, 2*add(binomial(n, 2*j)*bell(j), j=0..n/2)):
seq(a(n), n=0..35);

a[n_] := If[n==0, 1, 2*Sum[Binomial[n, 2*j]*BellB[j], {j, 0, n/2}]]; Table[ a[n], {n, 0, 35}] (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

a(n) = 2 * Sum_{j=0..floor(n/2)} C(n,2*j) * A000110(j) for n>0, a(0) = 1.

cp's OEIS Frontend

A261041 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in different parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A247100 The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A261134 Number of partitions of subsets s of {1,...,n}, where all integers belonging to a run of consecutive members of s are required to be in different parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A261492 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in the same part and the elements of {1, n} are required to be in the same part if they are both members of a subset.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula