A323949 -id:A323949 - cp's OEIS frontend

A306357 Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.

0, 1, 3, 6, 10, 20, 38, 70, 130, 240, 442, 814, 1498, 2756, 5070, 9326, 17154, 31552, 58034, 106742, 196330, 361108, 664182, 1221622, 2246914, 4132720, 7601258, 13980894, 25714874, 47297028, 86992798, 160004702, 294294530, 541292032, 995591266, 1831177830

Offset: 0

Gus Wiseman, Feb 10 2019

nonn

Cyclically successive means 1 is a successor of n.

Set partitions using these subsets are counted by A323949.

			The a(1) = 1 through a(5) = 20 stable subsets:
  {1}  {1}    {1}    {1}    {1}
       {2}    {2}    {2}    {2}
       {1,2}  {3}    {3}    {3}
              {1,2}  {4}    {4}
              {1,3}  {1,2}  {5}
              {2,3}  {1,3}  {1,2}
                     {1,4}  {1,3}
                     {2,3}  {1,4}
                     {2,4}  {1,5}
                     {3,4}  {2,3}
                            {2,4}
                            {2,5}
                            {3,4}
                            {3,5}
                            {4,5}
                            {1,2,4}
                            {1,3,4}
                            {1,3,5}
                            {2,3,5}
                            {2,4,5}

Cf. A000126, A000296, A001610, A001644, A169985, A306357, A323949, A323952, A323955.

stabsubs[g_]:=Select[Rest[Subsets[Union@@g]],Select[g,Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&];
Table[Length[stabsubs[Partition[Range[n],3,1,1]]],{n,15}]

For n >= 3 we have a(n) = A001644(n) - 1.
From Chai Wah Wu, Jan 06 2020: (Start)
a(n) = 2*a(n-1) - a(n-4) for n > 6.
G.f.: x*(x^5 + x^4 - 2*x^3 + x + 1)/(x^4 - 2*x + 1). (End)

A323955 Regular triangle read by rows where T(n, k) is the number of set partitions of {1, ..., n} with no block containing k cyclically successive vertices, n >= 1, 2 <= k <= n + 1.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 4, 10, 14, 15, 11, 36, 46, 51, 52, 41, 145, 184, 196, 202, 203, 162, 631, 806, 855, 869, 876, 877, 715, 3015, 3847, 4059, 4115, 4131, 4139, 4140, 3425, 15563, 19805, 20813, 21056, 21119, 21137, 21146, 21147, 17722, 86144, 109339, 114469

Offset: 1

Gus Wiseman, Feb 10 2019

Cyclically successive means 1 is a successor of n.

			Triangle begins:
    1
    1    2
    1    4    5
    4   10   14   15
   11   36   46   51   52
   41  145  184  196  202  203
  162  631  806  855  869  876  877
  715 3015 3847 4059 4115 4131 4139 4140
Row 4 counts the following partitions:
  {{13}{24}}      {{12}{34}}      {{1}{234}}      {{1234}}
  {{1}{24}{3}}    {{13}{24}}      {{12}{34}}      {{1}{234}}
  {{13}{2}{4}}    {{14}{23}}      {{123}{4}}      {{12}{34}}
  {{1}{2}{3}{4}}  {{1}{2}{34}}    {{124}{3}}      {{123}{4}}
                  {{1}{23}{4}}    {{13}{24}}      {{124}{3}}
                  {{12}{3}{4}}    {{134}{2}}      {{13}{24}}
                  {{1}{24}{3}}    {{14}{23}}      {{134}{2}}
                  {{13}{2}{4}}    {{1}{2}{34}}    {{14}{23}}
                  {{14}{2}{3}}    {{1}{23}{4}}    {{1}{2}{34}}
                  {{1}{2}{3}{4}}  {{12}{3}{4}}    {{1}{23}{4}}
                                  {{1}{24}{3}}    {{12}{3}{4}}
                                  {{13}{2}{4}}    {{1}{24}{3}}
                                  {{14}{2}{3}}    {{13}{2}{4}}
                                  {{1}{2}{3}{4}}  {{14}{2}{3}}
                                                  {{1}{2}{3}{4}}

First column (k = 2) is A000296. Second column (k = 3) is A323949. Rightmost terms are A000110. Second to rightmost terms are A058692.

Cf. A000126, A000325, A001610, A001644, A169985, A306351, A306357, A323950, A323954.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
Table[Length[spsu[Select[Subsets[Range[n]],Select[Partition[Range[n],k,1,1],Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&],Range[n]]],{n,7},{k,2,n+1}]

cp's OEIS Frontend

A306357 Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula