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

Links

Table of n, a(n) for n=1..31.

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

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 *)

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

Cf. A101052.

Sequence in context: A032086 A241278 A100239 * A038080 A257621 A190960

Adjacent sequences: A245020 A245021 A245022 * A245024 A245025 A245026

Keyword

nonn,easy

Author

Jaeyool Park, Jul 10 2014

Extensions

Typo in data fixed by Colin Barker, Jul 26 2014

Status

approved