A323953 -id:A323953 - 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

A323954 Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into connected subsequences of sizes > k, n >=1, 0 <= k < n.

Original entry on oeis.org

1, 2, 1, 5, 1, 1, 12, 3, 1, 1, 27, 6, 1, 1, 1, 58, 12, 4, 1, 1, 1, 121, 22, 8, 1, 1, 1, 1, 248, 39, 13, 5, 1, 1, 1, 1, 503, 67, 22, 10, 1, 1, 1, 1, 1, 1014, 113, 36, 16, 6, 1, 1, 1, 1, 1, 2037, 188, 56, 23, 12, 1, 1, 1, 1, 1, 1, 4084, 310, 86, 35, 19, 7, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, Feb 10 2019

			Triangle begins:
     1
     2    1
     5    1    1
    12    3    1    1
    27    6    1    1    1
    58   12    4    1    1    1
   121   22    8    1    1    1    1
   248   39   13    5    1    1    1    1
   503   67   22   10    1    1    1    1    1
  1014  113   36   16    6    1    1    1    1    1
  2037  188   56   23   12    1    1    1    1    1    1
  4084  310   86   35   19    7    1    1    1    1    1    1
Row 4 counts the following partitions:
  {{1234}}        {{1234}}    {{1234}}  {{1234}}
  {{1}{234}}      {{12}{34}}
  {{12}{34}}      {{14}{23}}
  {{123}{4}}
  {{124}{3}}
  {{134}{2}}
  {{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)

Column k = 0 is A000325. Column k = 1 is A066982. Column k = 2 is A323951. Column k = 3 is A306351.

Cf. A001610, A001680, A005251, A323950, A323951, A323952, 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,k],Range[n]]],{n,12},{k,0,n-1}]

T(n,k) = 1 - n + sum(i=1, n\(k+1), n*binomial(n-i*k-1, i-1)/i) \\ Andrew Howroyd, Jan 19 2023

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

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

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

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

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

A323954 Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into connected subsequences of sizes > k, n >=1, 0 <= k < n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

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

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

Mathematica

Extensions