A323954 -id:A323954 - cp's OEIS frontend

A066982 a(n) = Lucas(n+1) - (n+1).

1, 1, 3, 6, 12, 22, 39, 67, 113, 188, 310, 508, 829, 1349, 2191, 3554, 5760, 9330, 15107, 24455, 39581, 64056, 103658, 167736, 271417, 439177, 710619, 1149822, 1860468, 3010318, 4870815, 7881163, 12752009, 20633204, 33385246, 54018484, 87403765, 141422285

Offset: 1

Benoit Cloitre, Jan 27 2002

From Gus Wiseman, Feb 12 2019: (Start)
Also the number of ways to split an (n + 1)-cycle into nonempty connected subgraphs with no singletons. For example, the a(1) = 1 through a(5) = 12 partitions are:
  {{12}}  {{123}}  {{1234}}    {{12345}}    {{123456}}
                   {{12}{34}}  {{12}{345}}  {{12}{3456}}
                   {{14}{23}}  {{123}{45}}  {{123}{456}}
                               {{125}{34}}  {{1234}{56}}
                               {{145}{23}}  {{1236}{45}}
                               {{15}{234}}  {{1256}{34}}
                                            {{126}{345}}
                                            {{1456}{23}}
                                            {{156}{234}}
                                            {{16}{2345}}
                                            {{12}{34}{56}}
                                            {{16}{23}{45}}
Also the number of non-singleton subsets of {1, ..., (n + 1)} with no cyclically successive elements (cyclically successive means 1 succeeds n + 1). For example, the a(1) = 1 through a(5) = 12 subsets are:
  {}  {}  {}     {}     {}
          {1,3}  {1,3}  {1,3}
          {2,4}  {1,4}  {1,4}
                 {2,4}  {1,5}
                 {2,5}  {2,4}
                 {3,5}  {2,5}
                        {2,6}
                        {3,5}
                        {3,6}
                        {4,6}
                        {1,3,5}
                        {2,4,6}
(End)

Harry J. Smith, Table of n, a(n) for n = 1..250
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A000032, A000045, A000126, A000325, A005251, A169985, A323953, A323954, A352744.

List([1..40], n-> Lucas(1,-1,n+1)[2] -n-1); # G. C. Greubel, Jul 09 2019

[Lucas(n+1)-n-1: n in [1..40]]; // G. C. Greubel, Jul 09 2019

a[1]=a[2]=1; a[n_]:= a[n] = a[n-1] +a[n-2] +n-2; Table[a[n], {n, 40}]
LinearRecurrence[{3, -2, -1, 1}, {1, 1, 3, 6}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 13 2012 *)
Table[LucasL[n+1]-n-1, {n, 40}] (* Vladimir Reshetnikov, Sep 15 2016 *)
CoefficientList[Series[(1-2*x+2*x^2)/((1-x)^2*(1-x-x^2)), {x, 0, 40}], x] (* L. Edson Jeffery, Sep 28 2017 *)

vector(40, n, my(f=fibonacci); f(n+2)+f(n)-n-1) \\ G. C. Greubel, Jul 09 2019

[lucas_number2(n+1,1,-1) -n-1 for n in (1..40)] # G. C. Greubel, Jul 09 2019

a(1) = a(2) = 1, a(n + 2) = a(n + 1) + a(n) + n.
For n > 2, a(n) = floor(phi^(n+1) - (n+1)) + (1-(-1)^n)/2.
From Colin Barker, Jun 30 2012: (Start)
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4).
G.f.: x*(1-2*x+2*x^2)/((1-x)^2*(1-x-x^2)). (End)
a(n) is the sum of the n-th antidiagonal of A352744 (assuming offset 0). - Peter Luschny, Nov 16 2023

Corrected and extended by Harvey P. Dale, Feb 08 2002

A323950 Number of ways to split an n-cycle into connected subgraphs, none having exactly two vertices.

Original entry on oeis.org

1, 1, 1, 2, 6, 12, 23, 44, 82, 149, 267, 475, 841, 1484, 2613, 4595, 8074, 14180, 24896, 43702, 76705, 134622, 236260, 414623, 727629, 1276917, 2240851, 3932438, 6900967, 12110373, 21252244, 37295110, 65448378, 114853920, 201554603, 353703696, 620706742

Offset: 0

Gus Wiseman, Feb 10 2019

			The a(1) = 1 through a(5) = 12 partitions:
  {{1}}  {{1}{2}}  {{123}}      {{1234}}        {{12345}}
                   {{1}{2}{3}}  {{1}{234}}      {{1}{2345}}
                                {{123}{4}}      {{1234}{5}}
                                {{124}{3}}      {{1235}{4}}
                                {{134}{2}}      {{1245}{3}}
                                {{1}{2}{3}{4}}  {{1345}{2}}
                                                {{1}{2}{345}}
                                                {{1}{234}{5}}
                                                {{123}{4}{5}}
                                                {{125}{3}{4}}
                                                {{145}{2}{3}}
                                                {{1}{2}{3}{4}{5}}

Index entries for linear recurrences with constant coefficients, signature (4,-6,5,-3,1).

Cf. A000325, A001610, A001680, A005251, A066982, A306351, A323950, A323951, A323952, A323954.

cyceds[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,Prepend[Range[i+k,n+i-1],i]}]];
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[cyceds[n,2],Range[n]]],{n,15}]

G.f.: (x^7-3*x^6+3*x^5-2*x^4+x^3-3*x^2+3*x-1)/((x^3-x^2+2*x-1)*(x-1)^2). - Alois P. Heinz, Feb 10 2019

More terms from Alois P. Heinz, Feb 10 2019

A306351 Number of ways to split an n-cycle into connected subgraphs all having at least 4 vertices.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 5, 10, 16, 23, 35, 53, 78, 111, 157, 222, 313, 438, 610, 848, 1178, 1634, 2263, 3131, 4330, 5986, 8272, 11427, 15782, 21794, 30093, 41548, 57359, 79183, 109307, 150887, 208279, 287496, 396838, 547761, 756077, 1043611, 1440488, 1988289

Offset: 0

Gus Wiseman, Feb 10 2019

			The a(7) = 1 through a(9) = 10 partitions:
  {{1234567}}  {{12345678}}    {{123456789}}
               {{1234}{5678}}  {{1234}{56789}}
               {{1238}{4567}}  {{12345}{6789}}
               {{1278}{3456}}  {{12349}{5678}}
               {{1678}{2345}}  {{12389}{4567}}
                               {{1239}{45678}}
                               {{12789}{3456}}
                               {{1289}{34567}}
                               {{16789}{2345}}
                               {{1789}{23456}}

Index entries for linear recurrences with constant coefficients, signature (3,-3,1,1,-2,1).

Column k = 3 of A323954.

Cf. A000325, A005251, A066982, A078012, A323950, A323951, A323953.

cycedsprop[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,i+k,n+i-1}]];
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[cycedsprop[n,3],Range[n]]],{n,15}]

G.f.: (2*x^9-3*x^8+x^3-3*x^2+3*x-1)/((x^4+x-1)*(x-1)^2). - Alois P. Heinz, Feb 10 2019

More terms from Alois P. Heinz, Feb 10 2019

A323951 Number of ways to split an n-cycle into connected subgraphs, all having at least three vertices.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 4, 8, 13, 22, 36, 56, 86, 131, 197, 294, 437, 647, 955, 1407, 2070, 3042, 4467, 6556, 9618, 14106, 20684, 30325, 44455, 65164, 95515, 139997, 205189, 300733, 440760, 645980, 946745, 1387538, 2033552, 2980332, 4367906, 6401495, 9381865, 13749810

Offset: 0

Gus Wiseman, Feb 10 2019

			The a(3) = 1 through a(7) = 8 partitions:
  {{123}}  {{1234}}  {{12345}}  {{123456}}    {{1234567}}
                                {{123}{456}}  {{123}{4567}}
                                {{126}{345}}  {{1234}{567}}
                                {{156}{234}}  {{1237}{456}}
                                              {{1267}{345}}
                                              {{127}{3456}}
                                              {{1567}{234}}
                                              {{167}{2345}}

Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Cf. A000325, A001610, A001680, A005251, A066982, A306351, A323950, A323952, A323954.

cycedsprop[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,i+k,n+i-1}]];
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[cycedsprop[n,2],Range[n]]],{n,15}]

G.f.: (x^7-2*x^6+x^3-3*x^2+3*x-1)/((x^3+x-1)*(x-1)^2). - Alois P. Heinz, Feb 10 2019

More terms from Alois P. Heinz, Feb 10 2019

A323952 Regular triangle read by rows where if k > 1 then T(n, k) is the number of connected subgraphs of an n-cycle with any number of vertices other than 2 through k - 1, n >= 1, 1 <= k <= n - 1. Otherwise T(n, 1) = n.

Original entry on oeis.org

1, 2, 3, 3, 7, 4, 4, 13, 9, 5, 5, 21, 16, 11, 6, 6, 31, 25, 19, 13, 7, 7, 43, 36, 29, 22, 15, 8, 8, 57, 49, 41, 33, 25, 17, 9, 9, 73, 64, 55, 46, 37, 28, 19, 10, 10, 91, 81, 71, 61, 51, 41, 31, 21, 11, 11, 111, 100, 89, 78, 67, 56, 45, 34, 23, 12, 12, 133, 121

Offset: 1

Gus Wiseman, Feb 10 2019

			Triangle begins:
   1
   2   3
   3   7   4
   4  13   9   5
   5  21  16  11   6
   6  31  25  19  13   7
   7  43  36  29  22  15   8
   8  57  49  41  33  25  17   9
   9  73  64  55  46  37  28  19  10
  10  91  81  71  61  51  41  31  21  11
  11 111 100  89  78  67  56  45  34  23  12
  12 133 121 109  97  85  73  61  49  37  25  13
Row 4 counts the following connected sets:
  {1}  {1}     {1}     {1}
  {2}  {2}     {2}     {2}
  {3}  {3}     {3}     {3}
  {4}  {4}     {4}     {4}
       {12}    {123}   {1234}
       {14}    {124}
       {23}    {134}
       {34}    {234}
       {123}   {1234}
       {124}
       {134}
       {234}
       {1234}

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

First column is A000027. Second column is A002061. Third column is A000290. Fourth column is A028387.

Cf. A000126, A000325, A306351, A323950, A323951, A323953, A323954, A323956.

anesw[n_,k_]:=Length[If[k==1,List/@Range[n],Union[Sort/@Select[Union[List/@Range[n],Join@@Table[Partition[Range[n],i,1,1],{i,k,n}]],UnsameQ@@#&&#!={}&]]]];
Table[anesw[n,k],{n,0,16},{k,n}]

T(n,k) = if(k==1, n, 1 + n * (n - k + 1)) \\ Andrew Howroyd, Jan 18 2023

T(n, 1) = n; T(n, k) = 1 + n * (n - k + 1).

A323953 Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into singletons and connected subsequences of sizes > k.

Original entry on oeis.org

1, 2, 1, 5, 2, 1, 12, 6, 2, 1, 27, 12, 7, 2, 1, 58, 23, 14, 8, 2, 1, 121, 44, 23, 16, 9, 2, 1, 248, 82, 38, 26, 18, 10, 2, 1, 503, 149, 65, 38, 29, 20, 11, 2, 1, 1014, 267, 112, 57, 42, 32, 22, 12, 2, 1, 2037, 475, 189, 90, 57, 46, 35, 24, 13, 2, 1

Offset: 1

Gus Wiseman, Feb 10 2019

			Triangle begins:
     1
     2    1
     5    2    1
    12    6    2    1
    27   12    7    2    1
    58   23   14    8    2    1
   121   44   23   16    9    2    1
   248   82   38   26   18   10    2    1
   503  149   65   38   29   20   11    2    1
  1014  267  112   57   42   32   22   12    2    1
  2037  475  189   90   57   46   35   24   13    2    1
  4084  841  312  146   80   62   50   38   26   14    2    1
Row 4 counts the following connected partitions:
  {{1234}}        {{1234}}        {{1234}}        {{1}{2}{3}{4}}
  {{1}{234}}      {{1}{234}}      {{1}{2}{3}{4}}
  {{12}{34}}      {{123}{4}}
  {{123}{4}}      {{124}{3}}
  {{124}{3}}      {{134}{2}}
  {{134}{2}}      {{1}{2}{3}{4}}
  {{14}{23}}
  {{1}{2}{34}}
  {{1}{23}{4}}
  {{12}{3}{4}}
  {{14}{2}{3}}
  {{1}{2}{3}{4}}

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

First column is A000325. Second column is A323950.

Cf. A001610, A001680, A005251, A066982, A306351, A323951, A323952, A323954.

cyceds[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,Prepend[Range[i+k,n+i-1],i]}]];
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[cyceds[n,k],Range[n]]],{n,10},{k,n}]

T(n,k) = {1 + if(kAndrew Howroyd, Jan 19 2023

T(n,k) = 2 - n + Sum_{i=1..floor(n/k)} n*binomial(n-i*k+i-1, 2*i-1)/i for 1 <= k < n. - Andrew Howroyd, Jan 19 2023

A323949 Number of set partitions of {1, ..., n} with no block containing three distinct cyclically successive vertices.

Original entry on oeis.org

1, 1, 2, 4, 10, 36, 145, 631, 3015, 15563, 86144, 508311, 3180930, 21018999, 146111543, 1065040886, 8117566366, 64531949885, 533880211566, 4587373155544, 40865048111424, 376788283806743, 3590485953393739, 35312436594162173, 357995171351223109, 3736806713651177702

Offset: 0

Gus Wiseman, Feb 10 2019

nonn

Cyclically successive means 1 is a successor of n.

			The a(1) = 1 through a(4) = 10 set partitions:
  {{1}}  {{1,2}}    {{1},{2,3}}    {{1,2},{3,4}}
         {{1},{2}}  {{1,2},{3}}    {{1,3},{2,4}}
                    {{1,3},{2}}    {{1,4},{2,3}}
                    {{1},{2},{3}}  {{1},{2},{3,4}}
                                   {{1},{2,3},{4}}
                                   {{1,2},{3},{4}}
                                   {{1},{2,4},{3}}
                                   {{1,3},{2},{4}}
                                   {{1,4},{2},{3}}
                                   {{1},{2},{3},{4}}

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

Cf. A000085, A000110, A000126, A000296, A000325, A001610, A001644, A078012, A169985.

Cf. A306351, A306357, A323950, A323951, A323953, A323954, A323955, A323956.

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],3,1,1],Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&],Range[n]]],{n,8}]

a(12)-a(25) from Alois P. Heinz, Feb 10 2019

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

A066982 a(n) = Lucas(n+1) - (n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A323950 Number of ways to split an n-cycle into connected subgraphs, none having exactly two vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A306351 Number of ways to split an n-cycle into connected subgraphs all having at least 4 vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A323951 Number of ways to split an n-cycle into connected subgraphs, all having at least three vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A323952 Regular triangle read by rows where if k > 1 then T(n, k) is the number of connected subgraphs of an n-cycle with any number of vertices other than 2 through k - 1, n >= 1, 1 <= k <= n - 1. Otherwise T(n, 1) = n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A323953 Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into singletons and connected subsequences of sizes > k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A323949 Number of set partitions of {1, ..., n} with no block containing three distinct cyclically successive vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs