|
%I M5200 #92 Jan 05 2024 23:32:28
%S 3,6,28,165,1092,7752,57684,444015,3506100,28242984,231180144,
%T 1917334783,16077354108,136074334200,1160946392760,9973891723635,
%U 86210635955220,749191930237608,6541908910355280,57369142749576660,505045163173167760,4461713825057817120
%N a(n) = 3*binomial(4*n,n)/(n+1).
%C For n >= 1, a(n) is the number of distinct perforation patterns for deriving (v,b) = (n+1,n) punctured convolutional codes from (4,1). [Edited by _Petros Hadjicostas_, Jul 27 2020]
%C Apparently Bégin's (1992) paper was presented at a poster session at the conference and was never published.
%C a(n) is the total number of down steps between the first and second up steps in all 3-Dyck paths of length 4*(n+1). A 3-Dyck path is a nonnegative lattice path with steps (1,3), (1,-1) that starts and ends at y = 0. - _Sarah Selkirk_, May 07 2020
%C From _Petros Hadjicostas_, Jul 27 2020: (Start)
%C "A punctured convolutional code is a high-rate code obtained by the periodic elimination (i.e., puncturing) of specific code symbols from the output of a low-rate encoder. The resulting high-rate code depends on both the low-rate code, called the original code, and the number and specific positions of the punctured symbols." (The quote is from Haccoun and Bégin (1989).)
%C A high-rate code (v,b) (written as R = b/v) can be constructed from a low-rate code (v0,1) (written as R = 1/v0) by deleting from every v0*b code symbols a number of v0*b - v symbols (so that the resulting rate is R = b/v).
%C Even though my formulas below do not appear in the two published papers in the IEEE Transactions on Communications, from the theory in those two papers, it makes sense to replace "k|b" with "k|v0*b" (and "k|gcd(v,b)" with "k|gcd(v,v0*b)"). Pab Ter, however, uses "k|b" in the Maple programs in the related sequences A007223, A007224, A007225, A007227, and A007229. (End)
%C Conjecture: for n >= 1, a(n) is odd iff n = 4*A263133(k) + 3 for some k. - _Peter Bala_, Mar 13 2023
%D Guy Bégin, On the enumeration of perforation patterns for punctured convolutional codes, Séries Formelles et Combinatoire Algébrique, 4th colloquium, 15-19 Juin 1992, Montréal, Université du Québec à Montréal, pp. 1-10.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Andrew Howroyd, <a href="/A007228/b007228.txt">Table of n, a(n) for n = 0..500</a>
%H A. Asinowski, B. Hackl, and S. Selkirk, <a href="https://arxiv.org/abs/2007.15562">Down step statistics in generalized Dyck paths</a>, arXiv:2007.15562 [math.CO], 2020.
%H Guy Bégin and David Haccoun, <a href="https://doi.org/10.1109/26.44210">High rate punctured convolutions codes: Structure properties and construction techniques</a>, IEEE Transactions on Communications 37(12) (1989), 1381-1385.
%H Fabio Deelan Cunden, Marilena Ligabò, and Tommaso Monni, <a href="https://arxiv.org/abs/2301.13555">Random matrices associated to Young diagrams</a>, arXiv:2301.13555 [math.PR], 2023. See p. 7.
%H N. S. S. Gu, H. Prodinger, and S. Wagner, <a href="https://doi.org/10.1016/j.ejc.2009.10.007">Bijections for a class of labeled plane trees</a>, Eur. J. Combinat. 31 (2010), 720-732, Theorem 2 at k=3.
%H David Haccoun and Guy Bégin, <a href="https://doi.org/10.1109/26.46505">High rate punctured convolutional codes for Viterbi and sequential coding</a>, IEEE Transactions on Communications, 37(11) (1989), 1113-1125; see Section II.
%F a(n) = C(4*n,n)/(3*n+1) + 2*C(4*n+1,n)/(3*n+2) + 3*C(4*n+2,n)/(3*n+3). - _Paul Barry_, Nov 05 2006
%F G.f.: g + g^2 + g^3 where g = 1 + x*g^4 is the g.f. of A002293. - _Mark van Hoeij_, Nov 11 2011
%F 3*(3*n-1)*(3*n-2)*(n+1)*a(n) - 8*(4*n-3)*(2*n-1)*(4*n-1)*a(n-1) = 0. - _R. J. Mathar_, Nov 24 2012
%F From _Petros Hadjicostas_, Jul 27 2020: (Start)
%F The number of perforation patterns to derive high-rate convolutional code (v,b) (written as R = b/v) from a given low-rate convolutional code (v0, 1) (written as R = 1/v0) is (1/b)*Sum_{k|gcd(v,b)} phi(k)*binomial(v0*b/k, v/k).
%F According to Pab Ter's Maple code in the related sequences (see above), this is the coefficient of z^v in the polynomial (1/b)*Sum_{k|b} phi(k)*(1 + z^k)^(v0*b/k).
%F Here (v,b) = (n+1,n) and (v0,1) = (4,1), so for n >= 1,
%F a(n) = (1/n)*Sum_{k|gcd(n+1,n)} phi(k)*binomial(4*n/k, (n+1)/k).
%F This simplifies to
%F a(n) = (1/n)*binomial(4*n, n+1) for n >= 1. (End)
%e From _Petros Hadjicostas_, Jul 29 2020: (Start)
%e We give some examples to illustrate the comment by _Sarah Selkirk_ about the total number of downs between the 1st and 2nd ups in a 2-Dyck path of length 4*(n+1). We denote by (+3) an up movement by a vector of (1,3) and by (-1) a down movement by a vector of (1,-1). We use powers to denote repetition of the same movement.
%e (i) For n = 0, we have the following 2-Dyck path of length 4 that contributes to a(0) = 3: (+3)(-1)^3 (no 2nd up here) with a total of 3 downs after the 1st up.
%e (ii) For n = 1, we have the following 2-Dyck paths of length 8 that contribute to a(1) = 6: (+3)(-1)(+3)(-1)^5, (+3)(-1)^2(+3)(-1)^4, and (+3)(-1)^3(+3)(-1)^3 with a contribution of 1 + 2 + 3 = 6 downs between the 1st and 2nd ups.
%e (iii) For n = 2, we have the following 2-Dyck paths of length 12 that contribute to a(2) = 28: (+3)(-1)(+3)(-1)^i(+3)(-1)^(8-i) for i = 0..5, (+3)(-1)^2(+3)(-1)^i(+3)^(7-i) for i = 0..4, and (+3)(-1)^3(+3)(-1)^i(+3)(-1)^(6-i) for i = 0..3 with a contribution of 1 x 6 + 2 x 5 + 3 x 4 = 28 downs between the 1st and 2nd ups. (End)
%t Table[3/(n+1) Binomial[4n,n],{n,0,30}] (* _Harvey P. Dale_, Nov 14 2013 *)
%o (PARI) a(n)={3*binomial(4*n,n)/(n+1)} \\ _Andrew Howroyd_, May 08 2020
%o (Magma) [3*Binomial(4*n,n)/(n+1) : n in [0..25]]; // _Wesley Ivan Hurt_, Jul 27 2020
%Y Cf. A002293, A007223, A007224, A007225, A007226, A007227, A007229, A124724, A263133, A006632.
%K nonn,easy
%O 0,1
%A _Simon Plouffe_
%E Edited by _N. J. A. Sloane_, Feb 07 2004 following a suggestion of _Ralf Stephan_
%E Reedited by _N. J. A. Sloane_, May 31 2008 following a suggestion of _R. J. Mathar_
|
