OFFSET
0,2
COMMENTS
Here we let p = 4 to produce the above sequence, but p can be an arbitrary natural number. By letting p = 2, 3, 6, 7 we produce A000975, A033138, A195904 and A117302. We denote by U[p,n,m] the number of cases in which the first player gets killed in a Russian roulette game when p players use a gun with n chambers and m bullets. They never rotate the cylinder after the game starts. The chambers can be represented by the list {1,2,...,n}.
We are going to calculate the following (0), (1), ..., (t) separately. (0) The first player gets killed when one bullet is in the first chamber and the remaining m-1 bullets are in {2,3,...,n}. We have binomial(n-1,m-1) cases for this. (1) The first gets killed when one bullet is in the (p+1)th chamber and the rest of the bullets are in {p+2,...,n}. We have binomial(n-p-1,m-1) cases for this. We continue to calculate and the last is (t), where t = floor((n-m)/p). (t) The first gets killed when one bullet is in the (pt+1)-st chamber and the remaining bullets are in {pt+2,...,n}. We have binomial(n-pt-1,m-1) cases for this. Therefore U[p,n,m] = Sum_{z=0..floor((n-m)/p)} binomial(n-pz-1,m-1). Let A[p,n] be the number of the cases in which the first player gets killed when p players use a gun with n chambers and the number of the bullets can be from 1 to n. Then A[p,n] = Sum_{m=1..n} U[p,n,m]. - Ryohei Miyadera, Tomohide Hashiba, Yuta Nakagawa, Hiroshi Matsui, Jun 04 2006
A001045(n+5) without last digit. - Paul Curtz, Apr 21 2021
a(n) is the number of partitions of n into parts 1 and 4 where there are two colors of part 1 and the order of the colors of parts 1 matters. If the order of colors doesn't matter we get A001972. - Joerg Arndt, Jan 18 2024
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,0,1,-2).
FORMULA
a(n) = 2*a(n-1) + a(n-4) - 2*a(n-5).
If n is a multiple of 4, then a(n) = 2*a(n-1) + 1, otherwise a(n) = 2*a(n-1). - Gerald McGarvey, Oct 14 2008
a(n) = floor((2^(n+5) + 1)/30). - Tani Akinari, Jul 09 2013
a(n) = 2*a(n-1) + floor(((n-1) mod 4) /3), with a(0)=1. - Andres Cicuttin, Mar 29 2016
a(n) = 2*a(n-1) + 1 - ceiling((n mod 4)/4), with a(0)=1. - Andres Cicuttin, Mar 29 2016
15*a(n) = 2^(n+4) - A133145(n). - R. J. Mathar, Feb 27 2019
MATHEMATICA
U[p_, n_, m_, v_]:=Block[{t}, t=Floor[(1+p-m+n-v)/p]; Sum[Binomial[n-v-p*z, m-1], {z, 0, t-1}]]; A[p_, n_, v_]:=Sum[U[p, n, k, v], {k, 1, n}]; (* Here we let p = 4 to produce the above sequence, but this code can produce A000975, A033138, A195904, A117302 for p=2, 3, 6, 7.*) Table[A[4, n, 1], {n, 1, 20}] (* Ryohei Miyadera, Tomohide Hashiba, Yuta Nakagawa, Hiroshi Matsui, Jun 04 2006 *)
CoefficientList[Series[1/((1-2x)(1-x^4)), {x, 0, 40}], x] (* Vincenzo Librandi, Apr 04 2012 *)
a[n_] := FromDigits[Table[(Mod[j, 4]/4) // Round, {j, 1, n + 3}], 2] (* Andres Cicuttin, Mar 25 2016 *)
a[n_] := a[n] = 2 a[n - 1] + 1 - Ceiling[Mod[n, 4]/4]; a[0] = 1;
Table[a[n], {n, 0, 31}] (* Andres Cicuttin, Mar 27 2016 *)
LinearRecurrence[{2, 0, 0, 1, -2}, {1, 2, 4, 8, 17}, 40] (* Harvey P. Dale, Apr 03 2018 *)
PROG
(PARI) Vec(1/((1-2*x)*(1-x^4))+O(x^99)) \\ Charles R Greathouse IV, May 15 2013
(PARI) a(n)=(16<<n)\15 \\ Charles R Greathouse IV, Mar 27 2016
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, May 02 2003
STATUS
approved