OFFSET
4,1
COMMENTS
4*a(n) is the number of ordered set partitions of an n-set into 3 nonempty sets such that the number of elements in a particular set (say the first one) is at least two (see example).
4*a(n) is also the number of ternary strings using digits {0,1,2} so that all digits are used and a particular digit appears at least twice; for example, for n=5, the 80 strings with at least two 0's are 00112 (30 of this type), 00122 (30 of this type), 00012 (20 of this type).
LINKS
Paolo Xausa, Table of n, a(n) for n = 4..1000
Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).
FORMULA
a(n) = (3^n - 3*(2^n - 1))/4 - (n/2)*(2^(n-2) - 1), n>=4.
G.f.: x^4*(3 - 7*x + 3*x^2)/((1 - 3*x)*(1 - 2*x)^2*(1 - x)^2). - Stefano Spezia, Jun 11 2023
a(n) = (Sum_{k=2..n-2} A000225(k-1)*binomial(n,k))/2. - R. J. Cano, Jul 27 2023
EXAMPLE
4*a(5)=80 since the ordered set partitions are the following: 30 of type {1,2}{3,4},{5}; 30 of type {1,2},{3},{4,5}; 20 of type {1,2,3},{4},{5}.
MATHEMATICA
LinearRecurrence[{9, -31, 51, -40, 12}, {3, 20, 90, 343, 1197}, 40] (* Paolo Xausa, Nov 18 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Enrique Navarrete, Jun 11 2023
STATUS
approved