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,2

Links

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

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

Example

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

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

Prog

(PARI) T(n, k) = {1 + if(k<n, 1-n) + sum(i=1, n\k, n*binomial(n-i*k+i-1, 2*i-1)/i)} \\ Andrew Howroyd, Jan 19 2023

Crossrefs

First column is A000325. Second column is A323950.

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

Sequence in context: A126125 A221876 A128514 * A126075 A134032 A137151

Adjacent sequences: A323950 A323951 A323952 * A323954 A323955 A323956

Keyword

nonn,tabl

Author

Gus Wiseman, Feb 10 2019

Status

approved