A247100 -id:A247100 - 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)

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

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

Original entry on oeis.org

1, 2, 4, 8, 25, 82, 313, 1318, 6098, 30603, 165282, 954065, 5853242, 37987146, 259751877, 1864926846, 14016442573, 109985575616, 898948324164, 7637000950875, 67310106587314, 614420757079213, 5799709014601124, 56530981389520624, 568255134674637557

Offset: 0

Alois P. Heinz, Aug 21 2015

nonn

			a(3) = 8: {}, 1, 2, 3, 1|2, 1|3, 2|3, 1|2|3.
a(4) = 25: {}, 1, 2, 3, 4, 1|2, 1|3, 13, 1|4, 2|3, 2|4, 24, 3|4, 1|2|3, 13|2, 1|2|4, 1|24, 1|3|4, 13|4, 2|3|4, 24|3, 1|2|3|4, 13|2|4, 1|3|24, 13|24.

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

Cf. A247100, A261134, A261041, A261492.

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

g[n_, l_, t_, f_] := g[n, l, t, f] = If[n==0, 1, Sum[If[l>0 && j==l || f==1 && n==1 && j==1, 0, g[n-1, j, t+If[j==t, 1, 0], f]], {j, 0, t}]]; a[n_] := If[n==0, 1, g[n-1, 0, 1, 0]+g[n-1, 1, 2, 1]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 02 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.

A243634 Number of length n+2 0..n arrays with no three unequal elements in a row and new values 0..n introduced in 0..n order.

Original entry on oeis.org

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

Offset: 1

R. H. Hardin, Jun 08 2014

nonn

Diagonal of A243641.

			Some solutions for n=6
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..1....1....0....1....1....1....1....1....0....1....0....1....1....0....1....0
..1....0....1....0....1....1....1....1....1....0....0....0....1....1....0....1
..1....1....1....0....2....0....2....1....1....1....1....0....0....0....1....1
..2....1....0....0....1....1....2....1....1....0....1....1....0....0....1....1
..2....2....0....0....1....0....1....2....2....0....1....1....2....1....2....1
..2....1....2....1....3....0....1....2....2....2....1....1....2....1....2....0
..2....1....2....0....3....1....1....1....2....0....0....0....1....0....1....0

R. H. Hardin, Table of n, a(n) for n = 1..209

Cf. A247100.

A253409 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, and each run of zeros as an element in a second equivalence relation.

Original entry on oeis.org

1, 2, 4, 10, 28, 86, 282, 984, 3630, 14138, 57904, 248854, 1118554, 5246980, 25619018, 129961850, 683561488, 3722029314, 20946195078, 121671375312, 728511702462, 4491224518274, 28475638336144, 185499720543262, 1240358846060122, 8505894459387628, 59771243719783410

Offset: 0

Andrew Woods, Jan 01 2015

nonn

Included are the cases in which there are no zeros or no ones, producing an empty relation.

			For n = 3, taking 3-bit binary strings and replacing zeros with ABC... and ones with 123... to represent equivalence relations, we have a(3) = 10 labeled-run binary strings: AAA, AA1, A1A, A1B, 1AA, A11, 11A, 111, 1A1, 1A2.

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

Cf. A000110, A247100.

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

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

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

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

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

A261489 Number of partitions of subsets of {1,...,n}, where consecutive integers and the elements in {1, n} 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

A243634 Number of length n+2 0..n arrays with no three unequal elements in a row and new values 0..n introduced in 0..n order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A253409 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, and each run of zeros as an element in a second equivalence relation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions