A245023 Number of cases of tie (no winner) in the n-person rock-paper-scissors game.

3, 3, 9, 39, 153, 543, 1809, 5799, 18153, 55983, 171009, 519159, 1569753, 4733823, 14250609, 42850119, 128746953, 386634063, 1160688609, 3483638679, 10454061753, 31368476703, 94118013009, 282379204839, 847187946153, 2541664501743, 7625194831809, 22875987148599, 68628766752153, 205887910869183, 617666953833009

Offset: 1

Author

Jaeyool Park, Jul 10 2014

Keywords

• nonn
• easy

Examples

			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
		

Links

• Index entries for linear recurrences with constant coefficients, signature (6, -11, 6).

Crossrefs

Cf. A101052.

Programs

Magma

[3^n - 3*(2^n-2) : n in [1..30]]; // Wesley Ivan Hurt, Jul 26 2014

Maple

A245023:=n->3^n - 3*(2^n-2): seq(A245023(n), n=1..30); # Wesley Ivan Hurt, Jul 26 2014

Mathematica

Table[3^n - 3 (2^n - 2), {n, 30}] (* Wesley Ivan Hurt, Jul 26 2014 *)

PARI

a(n) = 3^n - 3*(2^n-2); \\ Michel Marcus, Jul 16 2014

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

Extensions

Typo in data fixed by Colin Barker, Jul 26 2014