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.

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

Author

Gus Wiseman, Feb 10 2019

Keywords

• nonn
• tabl

Examples

			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}}
		

Links

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

Crossrefs

First column is A000325. Second column is A323950.

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

Programs

Mathematica

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}]

PARI

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

Formula

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