A005251 -id:A005251 - cp's OEIS frontend

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

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

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

A002187 Sprague-Grundy values for Dawson's Chess (octal game .137).

Original entry on oeis.org

0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7, 4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7, 4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4

Offset: 0

N. J. A. Sloane

Octal game .07 (Dawson's Kayles) has values a(n-1). Octal games .4, .401, .402, .403, .42, .421, .422 and .423 have values a(n-2).

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see pp. 89 and 102.
R. K. Guy and C. A. B. Smith, The G-values of various games. Proc. Cambridge Philos. Soc. 52 (1956), 514-526.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Pratik Alladi, Neel Bhalla, Tanya Khovanova, Nathan Sheffield, Eddie Song, William Sun, Andrew The, Alan Wang, Naor Wiesel, Kevin Zhang Kevin Zhao, PRIMES STEP Plays Games, arXiv:1707.07201 [math.CO], 2017, Section 8.
Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego Manzano-Ruiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, Nimber Sequences of Node-Kayles Games, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.
Achim Flammenkamp, Octal games
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]

a002187 n = a002187_list !! n
a002187_list = tail g where
   g = 0 : 0 : [mex [xor (g !! (a + 1)) (g !! (n - a - 2)) |
                     a <- [-1 .. n - 2]] | n <- [1 ..]]
   xor 0 0 = 0
   xor x y = let ((q,r), (s,t)) = (divMod x 2, divMod y 2)
              in (if r == t then 0 else 1) + 2 * xor q s
   mex xs = head [x | x <- [0..], not (elem x xs)]
-- Paul Stoeber (pstoeber(AT)uni-potsdam.de), Oct 08 2005; edited by Reinhard Zumkeller, Dec 16 2013

Has period 34 with the only exceptions at n=0, 14, 16, 17, 31, 34 and 51.

Edited by Christian G. Bower, Oct 22 2002

A099098 Quadrisection of a Padovan sequence.

Original entry on oeis.org

1, 1, 4, 12, 37, 114, 351, 1081, 3329, 10252, 31572, 97229, 299426, 922111, 2839729, 8745217, 26931732, 82938844, 255418101, 786584466, 2422362079, 7459895657, 22973462017, 70748973084, 217878227876, 670976837021, 2066337330754

Offset: 0

Paul Barry, Sep 29 2004

Quadrisection of sequence with g.f. 1/(1-x^2-x^3), or A000931(n+3).

			1 + x + 4*x^2 + 12*x^3 + 37*x^4 + 114*x^5 + 351*x^6 + ...

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 4.
Index entries for linear recurrences with constant coefficients, signature (2,3,1).

Bisection of A005251.

LinearRecurrence[{2,3,1},{1,1,4},40] (* Harvey P. Dale, Aug 23 2011 *)

G.f.: (1-x-x^2)/(1-2x-3x^2-x^3);
a(n)=sum{k=0..2n, binomial(k, 4n-2k)};
a(n)=2a(n-1)+3a(n-2)+a(n-3);
a(n)=A000931(4n+3).
a(n) = Sum [k=0..n, C(2n-k, 2k) ].

A113235 Number of partitions of {1,..,n} into any number of lists of size not equal to 2, where a list means an ordered subset, cf. A000262.

Original entry on oeis.org

1, 1, 1, 7, 49, 301, 2281, 21211, 220417, 2528569, 32014801, 442974511, 6638604721, 107089487077, 1849731389689, 34051409587651, 665366551059841, 13751213558077681, 299644435399909537, 6864906328749052759, 164941239260973870001, 4146673091958686331421

Offset: 0

Karol A. Penson, Oct 19 2005

nonn

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

Cf. A000262, A000266, A005251, A052845, A097514.

This sequence, A113236 and A113237 all describe the same type of mathematical structure: lists with some restrictions.

I:=[1, 1, 7, 49]; [1] cat [n le 4 select I[n] else (2*n-1)*Self(n -1) - (n-1)*n*Self(n-2) +4*(n-1)*(n-2)*Self(n-3) -2*(n-1)*(n-2)*(n-3)* Self(n-4): n in [1..30]]; // G. C. Greubel, May 16 2018

a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*binomial(n-1, j-1)*j!, j=[1, $3..n]))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 10 2016

f[n_] := n!*Sum[(-1)^k*LaguerreL[n - 2*k, -1, -1]/k!, {k, 0, Floor[n/2]}]; Table[ f[n], {n, 0, 19}]
Range[0, 19]!*CoefficientList[ Series[ Exp[x*(1 - x + x^2)/(1 - x)], {x, 0, 19}], x] (* Robert G. Wilson v, Oct 21 2005 *)

m=30; v=concat([1,1,7,49], vector(m-4)); for(n=5, m, v[n]=(2*n-1)*v[n-1]-(n-1)*n*v[n-2]+4*(n-1)*(n-2)*v[n-3]-2*(n-1)*(n-2)*(n-3)*v[n -4]); concat([1], v) \\ G. C. Greubel, May 16 2018

x='x+O('x^99); Vec(serlaplace(exp(x*(1-x+x^2)/(1-x)))) \\ Altug Alkan, May 17 2018

Expression as a sum involving generalized Laguerre polynomials, in Mathematica notation: a(n)=n!*Sum[(-1)^k*LaguerreL[n - 2*k, -1, -1]/k!, {k, 0, Floor[n/2]}], n=0, 1... .
E.g.f.: exp(x*(1-x+x^2)/(1-x)).
From Vaclav Kotesovec, Nov 13 2017: (Start)
a(n) = (2*n - 1)*a(n-1) - (n-1)*n*a(n-2) + 4*(n-2)*(n-1)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*a(n-4).
a(n) ~ exp(-3/2 + 2*sqrt(n) - n) * n^(n-1/4) / sqrt(2) * (1 + 91/(48*sqrt(n))).
(End)

A188695 T(n,k)=Number of nXk binary arrays without the pattern 0 1 0 diagonally, vertically, antidiagonally or horizontally.

Original entry on oeis.org

2, 4, 4, 7, 16, 7, 12, 49, 49, 12, 21, 144, 218, 144, 21, 37, 441, 857, 857, 441, 37, 65, 1369, 3609, 4008, 3609, 1369, 65, 114, 4225, 15942, 20662, 20662, 15942, 4225, 114, 200, 12996, 69852, 120839, 139307, 120839, 69852, 12996, 200, 351, 40000, 302053

Offset: 1

R. H. Hardin Apr 08 2011

Table starts
...2......4.......7........12.........21...........37.............65
...4.....16......49.......144........441.........1369...........4225
...7.....49.....218.......857.......3609........15942..........69852
..12....144.....857......4008......20662.......120839.........708519
..21....441....3609.....20662.....139307......1181340........9908740
..37...1369...15942....120839....1181340.....15547072......196218615
..65...4225...69852....708519....9908740....196218615.....3647921173
.114..12996..302053...3984317...75877068...2192313402....58576420100
.200..40000.1305379..22096751..567455273..24054473035...923989193674
.351.123201.5658937.123685638.4366586742.276006561506.15401563228402

			Some solutions for 6X4
..0..0..0..0....0..0..0..1....1..1..0..1....1..1..1..0....0..1..1..1
..1..0..0..0....1..1..0..0....0..0..0..0....1..0..0..0....0..0..1..1
..1..0..0..0....1..1..1..0....1..0..0..1....1..0..0..0....0..0..1..1
..0..0..0..0....1..1..1..1....1..0..0..1....1..0..0..0....1..0..0..1
..1..0..0..0....1..1..0..1....1..0..1..1....1..0..0..0....1..0..0..1
..1..0..0..0....1..1..0..0....1..0..1..1....1..0..0..1....1..0..0..0

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

Column 1 is A005251(n+3)

Column 2 is A188501

A188774 T(n,k)=Number of nXk binary arrays without the pattern 0 1 0 vertically or horizontally.

Original entry on oeis.org

2, 4, 4, 7, 16, 7, 12, 49, 49, 12, 21, 144, 240, 144, 21, 37, 441, 1103, 1103, 441, 37, 65, 1369, 5357, 7868, 5357, 1369, 65, 114, 4225, 26564, 60215, 60215, 26564, 4225, 114, 200, 12996, 130828, 471349, 738031, 471349, 130828, 12996, 200, 351, 40000, 641137

Offset: 1

R. H. Hardin Apr 09 2011

Table starts
...2......4........7.........12...........21.............37...............65
...4.....16.......49........144..........441...........1369.............4225
...7.....49......240.......1103.........5357..........26564...........130828
..12....144.....1103.......7868........60215.........471349..........3658041
..21....441.....5357......60215.......738031........9260851........114928827
..37...1369....26564.....471349......9260851......186969392.......3725504150
..65...4225...130828....3658041....114928827.....3725504150.....118984786902
.114..12996...641137...28240356...1418719059....73772281769....3772804871287
.200..40000..3143331..218167554..17534258973..1462969839335..119816916752612
.351.123201.15426387.1687182731.216934553467.29048017912245.3810670337663147

			Some solutions for 5X3
..0..1..1....1..1..1....1..1..0....0..0..1....0..0..1....0..0..0....1..0..0
..0..0..0....1..1..0....1..1..0....0..0..0....1..0..1....0..0..0....1..1..1
..1..1..0....0..0..0....1..0..0....0..0..1....1..0..1....0..0..1....1..1..1
..1..1..1....0..0..1....1..1..1....0..1..1....1..0..0....0..0..1....0..0..1
..0..1..1....0..1..1....0..1..1....1..1..1....0..0..0....1..0..0....0..0..1

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

Column 1 is A005251(n+3)

Column 2 is A188501

A202795 T(n,k)=Number of nXk binary arrays with every one adjacent to another one horizontally, diagonally, antidiagonally or vertically.

Original entry on oeis.org

1, 2, 2, 4, 12, 4, 7, 50, 50, 7, 12, 188, 398, 188, 12, 21, 724, 3018, 3018, 724, 21, 37, 2820, 23436, 45519, 23436, 2820, 37, 65, 10960, 182430, 702846, 702846, 182430, 10960, 65, 114, 42544, 1417772, 10892633, 21649928, 10892633, 1417772, 42544, 114

Offset: 1

R. H. Hardin Dec 24 2011

Table starts
...1......2.........4............7..............12.................21
...2.....12........50..........188.............724...............2820
...4.....50.......398.........3018...........23436.............182430
...7....188......3018........45519..........702846...........10892633
..12....724.....23436.......702846........21649928..........669872090
..21...2820....182430.....10892633.......669872090........41382940317
..37..10960...1417772....168585867.....20696263392......2552520578945
..65..42544..11017196...2608652667....639259508770....157398925950921
.114.165176..85621362..40368680378..19746821708510...9706685199080140
.200.641376.665418194.624709738658.609991818060458.598614098605286252

			Some solutions for n=5 k=3
..0..1..1....0..1..0....0..1..0....1..0..1....1..0..1....0..1..0....0..1..1
..0..0..0....1..1..1....1..0..1....1..1..0....1..0..1....1..0..0....0..1..1
..0..1..1....0..1..1....1..1..0....0..0..0....0..1..0....0..1..0....0..1..1
..0..1..1....1..0..1....0..1..0....1..0..0....0..1..1....1..1..1....1..0..0
..0..1..1....1..1..0....1..0..1....1..1..0....1..0..0....1..0..1....1..0..0

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

Column 1 is A005251(n+2)

A218765 T(n,k)=Unmatched value maps: number of nXk binary arrays indicating the locations of corresponding elements not equal to any horizontal or vertical neighbor in a random 0..1 nXk array.

Original entry on oeis.org

1, 2, 2, 4, 6, 4, 7, 18, 18, 7, 12, 47, 90, 47, 12, 21, 134, 403, 403, 134, 21, 37, 373, 1876, 2942, 1876, 373, 37, 65, 1035, 8697, 22439, 22439, 8697, 1035, 65, 114, 2889, 40383, 170148, 280850, 170148, 40383, 2889, 114, 200, 8050, 187413, 1291662, 3488015

Offset: 1

R. H. Hardin Nov 05 2012

Table starts
...1......2........4...........7............12.............21.............37
...2......6.......18..........47...........134............373...........1035
...4.....18.......90.........403..........1876...........8697..........40383
...7.....47......403........2942.........22439.........170148........1291662
..12....134.....1876.......22439........280850........3488015.......43403573
..21....373.....8697......170148.......3488015.......70915451.....1444700004
..37...1035....40383.....1291662......43403573.....1444700004....48186998294
..65...2889...187413.....9807350.....540089167....29426750811..1606766223984
.114...8050...869598....74441043....6717643958...599056249102.53537060426191
.200..22420..4035492...565067801...83563261332.12196183065261
.351..62477.18727387..4289417212.1039486332867
.616.174072.86907272.32560993753

			Some solutions for n=3 k=4
..0..0..1..1....0..0..1..0....1..1..1..1....1..0..0..0....0..0..0..0
..0..0..0..1....0..1..0..0....1..0..0..0....0..0..1..0....0..0..1..0
..1..0..0..1....1..1..0..0....0..0..0..0....0..1..0..0....0..0..0..0

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

Column 1 is A005251(n+2)

A219106 T(n,k)=Unmatched value maps: number of nXk binary arrays indicating the locations of corresponding elements not equal to any horizontal, vertical or antidiagonal neighbor in a random 0..2 nXk array.

Original entry on oeis.org

1, 2, 2, 4, 11, 4, 7, 42, 42, 7, 12, 154, 288, 154, 12, 21, 582, 1971, 1971, 582, 21, 37, 2199, 13674, 26145, 13674, 2199, 37, 65, 8287, 95146, 345529, 345529, 95146, 8287, 65, 114, 31240, 660556, 4591348, 8647530, 4591348, 660556, 31240, 114, 200, 117789

Offset: 1

R. H. Hardin Nov 11 2012

Table starts
...1......2........4.........7.........12..........21.........37........65
...2.....11.......42.......154........582........2199.......8287.....31240
...4.....42......288......1971......13674.......95146.....660556...4584620
...7....154.....1971.....26145.....345529.....4591348...60957131.808775383
..12....582....13674....345529....8647530...217909019.5486836181
..21...2199....95146...4591348..217909019.10432278539
..37...8287...660556..60957131.5486836181
..65..31240..4584620.808775383
.114.117789.31824915
.200.444096
.351

			Some solutions for n=3 k=4
..0..1..0..0....0..1..1..0....1..0..0..1....1..0..0..0....1..0..0..0
..0..1..0..0....0..1..0..0....0..1..0..0....0..0..0..0....0..0..1..0
..0..0..1..0....0..0..0..0....0..1..1..1....0..1..0..0....0..0..1..0

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

Column 1 is A005251(n+2)

cp's OEIS Frontend

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

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

A002187 Sprague-Grundy values for Dawson's Chess (octal game .137).

Views

Author

Keywords

Comments

References

Links

Programs

Haskell

Formula

Extensions

A099098 Quadrisection of a Padovan sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A113235 Number of partitions of {1,..,n} into any number of lists of size not equal to 2, where a list means an ordered subset, cf. A000262.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A188695 T(n,k)=Number of nXk binary arrays without the pattern 0 1 0 diagonally, vertically, antidiagonally or horizontally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A188774 T(n,k)=Number of nXk binary arrays without the pattern 0 1 0 vertically or horizontally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A202795 T(n,k)=Number of nXk binary arrays with every one adjacent to another one horizontally, diagonally, antidiagonally or vertically.

Views

Author

Keywords

Comments

Examples