|
%I #38 Sep 08 2022 08:46:08
%S 3,3,9,39,153,543,1809,5799,18153,55983,171009,519159,1569753,4733823,
%T 14250609,42850119,128746953,386634063,1160688609,3483638679,
%U 10454061753,31368476703,94118013009,282379204839,847187946153,2541664501743,7625194831809,22875987148599,68628766752153,205887910869183,617666953833009
%N Number of cases of tie (no winner) in the n-person rock-paper-scissors game.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6, -11, 6).
%F a(n) = 3^n - 3*(2^n-2) = 3 * A101052(n-1), n >= 1.
%F a(n) = 5*a(n-1)-5*a(n-2)-5*a(n-3)+6*a(n-4). - _Colin Barker_, Jul 26 2014
%F G.f.: -3*x*(8*x^2-5*x+1) / ((x-1)*(2*x-1)*(3*x-1)). - _Colin Barker_, Jul 26 2014
%F 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
%e 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.
%e 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
%p A245023:=n->3^n - 3*(2^n-2): seq(A245023(n), n=1..30); # _Wesley Ivan Hurt_, Jul 26 2014
%t Table[3^n - 3 (2^n - 2), {n, 30}] (* _Wesley Ivan Hurt_, Jul 26 2014 *)
%o (PARI) a(n) = 3^n - 3*(2^n-2); \\ _Michel Marcus_, Jul 16 2014
%o (Magma) [3^n - 3*(2^n-2) : n in [1..30]]; // _Wesley Ivan Hurt_, Jul 26 2014
%Y Cf. A101052.
%K nonn,easy
%O 1,1
%A _Jaeyool Park_, Jul 10 2014
%E Typo in data fixed by _Colin Barker_, Jul 26 2014
|
