login
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.
9
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,2
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
FORMULA
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
EXAMPLE
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}}
MATHEMATICA
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}]
PROG
(PARI) 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
CROSSREFS
Column k = 0 is A000325. Column k = 1 is A066982. Column k = 2 is A323951. Column k = 3 is A306351.
Sequence in context: A369526 A206563 A299779 * A143983 A282988 A113767
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Feb 10 2019
STATUS
approved