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
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
Comments