OFFSET
1,1
LINKS
Index entries for linear recurrences with constant coefficients, signature (6, -11, 6).
FORMULA
a(n) = 3^n - 3*(2^n-2) = 3 * A101052(n-1), n >= 1.
a(n) = 5*a(n-1)-5*a(n-2)-5*a(n-3)+6*a(n-4). - Colin Barker, Jul 26 2014
G.f.: -3*x*(8*x^2-5*x+1) / ((x-1)*(2*x-1)*(3*x-1)). - Colin Barker, Jul 26 2014
a(n) = 3 + 3!*S2(n, 3) with S2(n, k) = A008277(n, k) (Stirling numbers of the second kind). S2(n,3)= A000392(n). Proof: Use the formula given in A000392. Hint for an independent proof: consider the partition array A036040 for the multinomial M_3 numbers. Only partitions of n with number of parts m = 1, 2 and 3 matter here. Each partition defines a pattern for a multilist, like 2^1,3^2 defines the n=8, m=3 pattern [..][...][...]. The corresponding M_3 number 280 = C(8,2)*C(6,3)/2 gives the number of possibilities to form from objects, here R,R,P,P,P,S,S,S, lists of length 8 (the order is relevant). If m=1 then M_3 = 1 and for n one has 3 lists [n times R], [n times P] and [n times S] (no winner), If m=2 or 3 each of the M_3(n,m,j) (j=1..p(n,m), the number of partitions of n with m parts) comes 3! times from the permutation of the R, P and S symbols. The sum of the M_3 numbers over like m gives the Stirling2 numbers. If m=2 there are always winners for each n (only two symbols are present in each list). If m=1 or m=3 there is no winner. - Wolfdieter Lang, Aug 01 2014
EXAMPLE
R, P, S = each Rock, Paper, Scissors. For n = 2 RR, PP, SS. 3 cases. and for n = 3 RRR, PPP, SSS, RPS, PRS, RSP, PSR, SPR, SRP. 9 cases.
RRS (and RSR, SRR) is not a tie case because there are two winners. SPP (and PPS, PSP) is not a tie case because there is a winner even though the 2nd and 3rd places cannot be determined. - Wolfdieter Lang, Jul 31 2014
MAPLE
MATHEMATICA
Table[3^n - 3 (2^n - 2), {n, 30}] (* Wesley Ivan Hurt, Jul 26 2014 *)
PROG
(PARI) a(n) = 3^n - 3*(2^n-2); \\ Michel Marcus, Jul 16 2014
(Magma) [3^n - 3*(2^n-2) : n in [1..30]]; // Wesley Ivan Hurt, Jul 26 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jaeyool Park, Jul 10 2014
EXTENSIONS
Typo in data fixed by Colin Barker, Jul 26 2014
STATUS
approved