cp's OEIS Frontend

A003149 a(n) = Sum_{k=0..n} k!*(n - k)!.

%I A003149 M1496 #170 Aug 08 2025 14:54:03
%S A003149 1,2,5,16,64,312,1812,12288,95616,840960,8254080,89441280,1060369920,
%T A003149 13649610240,189550368000,2824077312000,44927447040000,
%U A003149 760034451456000,13622700994560000,257872110354432000,5140559166898176000,107637093007589376000,2361827297364885504000
%N A003149 a(n) = Sum_{k=0..n} k!*(n - k)!.
%C A003149 From _Michael Somos_, Feb 14 2002: (Start)
%C A003149 The sequence is the resistance between opposite corners of an (n+1)-dimensional hypercube of unit resistors, multiplied by (n+1)!.
%C A003149 The resistances for n+1 = 1,2,3,... are 1, 1, 5/6, 2/3, 8/15, 13/30, 151/420, 32/105, 83/315, 73/315, 1433/6930, ... (see A046878/A046879). (End)
%C A003149 Number of {12,21*,2*1}-avoiding signed permutations in the hyperoctahedral group.
%C A003149 a(n) is the sum of the reciprocals of the binomial coefficients C(n,k), multiplied by n!; example: a(4) = 4!*(1/1 + 1/4 + 1/6 + 1/4 + 1/1) = 64. - _Philippe Deléham_, May 12 2005
%C A003149 a(n) is the number of permutations on [n+1] that avoid the pattern 13-2|. The absence of a dash between 1 and 3 means the "1" and "3" must be consecutive in the permutation; the vertical bar means the "2" must occur at the end of the permutation. For example, 24153 fails to avoid this pattern: 243 is an offending subpermutation. - _David Callan_, Nov 02 2005
%C A003149 n!/a(n) is the probability that a random walk on an (n+1)-dimensional hypercube will visit the diagonally opposite vertex before it returns to its starting point. 2^n*a(n)/n! is the expected length of a random walk from one vertex of an (n+1)-dimensional hypercube to the diagonally opposite vertex (a walk which may include one or more passes through the starting point). These "random walk" examples are solutions to IBM's "Ponder This" puzzle for April, 2006. - _Graeme McRae_, Apr 02 2006
%C A003149 a(n) is the number of strong fixed points in all permutations of {1,2,...,n+1} (a permutation p of {1,2,...,n} is said to have j as a strong fixed point (splitter) if p(k)<j for k<j and p(k)>j for k>j). Example: a(2)=5 because the permutations of {1,2,3}, with marked strong fixed points, are: 1'2'3', 1'32, 312, 213', 231 and 321. - _Emeric Deutsch_, Oct 28 2008
%C A003149 Coefficients in the asymptotic expansion of exp(-2*x)*Ei(x)^2 for x -> inf, where Ei(x) is the exponential integral. - _Vladimir Reshetnikov_, Apr 24 2016
%D A003149 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (1.1.11 b, p.342).
%D A003149 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003149 R. P. Stanley, Enumerative Combinatorics, Volume 1 (1986), p. 49. [From _Emeric Deutsch_, Oct 28 2008]
%H A003149 T. D. Noe, <a href="/A003149/b003149.txt">Table of n, a(n) for n = 0..100</a>
%H A003149 Joerg Arndt, <a href="http://jjj.de/pub/arndt-rand-perm-thesis.pdf">Generating Random Permutations</a>, PhD thesis, Australian National University, Canberra, Australia, (2010).
%H A003149 Fred Curtis, <a href="http://f2.org/maths/resnet/">Resistance-network Problems</a>.
%H A003149 Bakir Farhi, <a href="https://arxiv.org/abs/2204.10136">On a curious integer sequence</a>, arXiv:2204.10136 [math.NT], 2022.
%H A003149 Todd Feil, Gary Kennedy and David Callan, <a href="http://www.jstor.org/stable/2324797">Problem E3467</a>, Amer. Math. Monthly, 100 (1993), 800-801. [From _Emeric Deutsch_, Oct 28 2008]
%H A003149 Henry W. Gould, <a href="/A003099/a003099_1.pdf">Letter to N. J. A. Sloane, Nov 1973, and various attachments</a>.
%H A003149 IBM, <a href="https://research.ibm.com/haifa/ponderthis/challenges/April2006.html">"Ponder This" puzzle for April, 2006</a>
%H A003149 T. Mansour and J. West, <a href="https://arxiv.org/abs/math/0207204">Avoiding 2-letter signed patterns</a>, arXiv:math/0207204 [math.CO], 2002.
%H A003149 F. Nedemeyer and Y. Smorodinsky, <a href="https://archive.org/stream/Quantum1_201506/Quantum%201#page/n17/mode/2up">Resistance in the multidimensional cube</a>, Quantum 7:1 (1996) 12-15 and 63.
%H A003149 R. Sprugnoli, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sprugnoli/sprugnoli4.html">Moments of Reciprocals of Binomial Coefficients</a>, Journal of Integer Sequences, 14 (2011), #11.7.8.
%H A003149 V. Strehl, <a href="/A003149/a003149.pdf">The average number of splitters in a random permutation</a> [Unpublished; included here with the author's permission.]
%H A003149 B. Sury, <a href="http://dx.doi.org/10.1006/eujc.1993.1038">Sum of the reciprocals of the binomial coefficients</a>, Europ. J. Comb., 14 (1993), 351-353.
%H A003149 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IncompleteBetaFunction.html">Incomplete Beta Function</a>.
%H A003149 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LerchTranscendent.html">Lerch Transcendent</a>.
%H A003149 <a href="/index/Res#resistances">Index to sequences related to resistances</a>.
%F A003149 a(n) = n! + ((n+1)/2)*a(n-1), n >= 1. - _Leroy Quet_, Sep 06 2002
%F A003149 a(n) = ((3n+1)*a(n-1) - n^2*a(n-2))/2, n >= 2. - _David W. Wilson_, Sep 06 2002; corrected by _N. Sato_, Jan 27 2010
%F A003149 G.f.: (Sum_{k>=0} k!*x^k)^2. - _Vladeta Jovovic_, Aug 30 2002
%F A003149 E.g.f: log(1-x)/(x/2 - 1) if offset 1.
%F A003149 Convolution of A000142 [factorial numbers] with itself. - _Ross La Haye_, Oct 29 2004
%F A003149 a(n) = Sum_{k=0..n+1} k*A145878(n+1,k). - _Emeric Deutsch_, Oct 28 2008
%F A003149 a(n) = A084938(n+2,2). - _Philippe Deléham_, Dec 17 2008
%F A003149 a(n) = 2*Integral_{t=0..oo} Ei(t)*exp(-2*t)*t^(n+1) where Ei is the exponential integral function. - _Groux Roland_, Dec 09 2010
%F A003149 Empirical: a(n-1) = 2^(-n)*(A103213(n) + n!*H(n)) with H(n) harmonic number of order n. - _Groux Roland_, Dec 18 2010; offset fixed by _Vladimir Reshetnikov_, Apr 24 2016
%F A003149 O.g.f.: 1/(1-I(x))^2 where I(x) is o.g.f. for A003319. - _Geoffrey Critzer_, Apr 27 2012
%F A003149 a(n) ~ 2*n!. - _Vaclav Kotesovec_, Oct 04 2012
%F A003149 a(n) = (n+1)!/2^n * Sum_{k=0..n} 2^k/(k+1). - _Vaclav Kotesovec_, Oct 27 2012
%F A003149 E.g.f.: 2/((x-1)*(x-2)) + 2*x/(x-2)^2*G(0) where G(k) = 1 + x*(2*k+1)/(2*(k+1) - 4*x*(k+1)^2/(2*x*(k+1) + (2*k+3)/G(k+1) )); (recursively defined continued fraction). - _Sergei N. Gladkovskii_, Dec 14 2012
%F A003149 a(n) = 2 * n! * (1 + Sum_{k>=1} A005649(k-1)/n^k). - _Vaclav Kotesovec_, Aug 01 2015
%F A003149 From _Vladimir Reshetnikov_, Nov 12 2015: (Start)
%F A003149 a(n) = -(n+1)!*Re(Beta(2; n+2, 0))/2^(n+1), where Beta(z; a, b) is the incomplete Beta function.
%F A003149 a(n) = -2*(n+1)!*Re(LerchPhi(2, 1, n+2)), where LerchPhi(z, s, a) is the Lerch transcendent. (End)
%F A003149 a(n) = (n+1)!*(H(n+1) + (n+1)*hypergeom([1, 1, -n], [2, 2], -1))/2^(n+1), where H(n) is the harmonic number. - _Vladimir Reshetnikov_, Apr 24 2016
%F A003149 Expansion of square of continued fraction 1/(1 - x/(1 - x/(1 - 2*x/(1 - 2*x/(1 - 3*x/(1 - 3*x/(1 - ...))))))). - _Ilya Gutkovskiy_, Apr 19 2017
%F A003149 a(n) = Sum_{k=0..n+1} (-1)^(n-k)*A226158(k)*Stirling1(n+1, k). - _Mélika Tebni_, Feb 22 2022
%F A003149 E.g.f.: x/((1-x)*(2-x))-(2*log(1-x))/(2-x)^2+1/(1-x). - _Vladimir Kruchinin_, Dec 17 2022
%p A003149 seq( add(k!*(n-k)!, k=0..n), n=0..20); # _G. C. Greubel_, Dec 29 2019
%p A003149 # second Maple program:
%p A003149 a:= proc(n) option remember; `if`(n<2, n+1,
%p A003149       ((3*n+1)*a(n-1)-n^2*a(n-2))/2)
%p A003149     end:
%p A003149 seq(a(n), n=0..22);  # _Alois P. Heinz_, Aug 08 2025
%t A003149 Table[Sum[k!(n-k)!,{k,0,n}],{n,0,20}] (* _Harvey P. Dale_, Mar 28 2012 *)
%t A003149 Table[(n+1)!/2^n*Sum[2^k/(k+1),{k,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 27 2012 *)
%t A003149 Round@Table[-2 (n+1)! Re[LerchPhi[2, 1, n+2]], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 12 2015 *)
%t A003149 Table[(n+1)!*Sum[Binomial[n+1, 2*j+1]/(2*j+1), {j, 0, n}]/2^n, {n, 0, 20}] (* _Vaclav Kotesovec_, Dec 04 2015 *)
%t A003149 Series[Exp[-2x] ExpIntegralEi[x]^2, {x, Infinity, 20}][[3]] (* _Vladimir Reshetnikov_, Apr 24 2016 *)
%t A003149 Table[2*(-1)^n * Sum[(2^k - 1) * StirlingS1[n, k] * BernoulliB[k], {k, 0, n}], {n, 1, 25}] (* _Vaclav Kotesovec_, Oct 04 2022 *)
%o A003149 (PARI) a(n)=sum(k=0,n,k!*(n-k)!)
%o A003149 (PARI) a(n)=if(n<0,0,(n+1)!*polcoeff(log(1-x+x^2*O(x^n))/(x/2-1),n+1))
%o A003149 (PARI) a(n) = my(A = 1, B = 1); for(k=1, n, B *= k; A = (n-k+1)*A + B); A \\ _Mikhail Kurkov_, Aug 08 2025
%o A003149 (Magma) F:=Factorial; [ (&+[F(k)*F(n-k): k in [0..n]]): n in [0..20]]; // _G. C. Greubel_, Dec 29 2019
%o A003149 (Sage) f=factorial; [sum(f(k)*f(n-k) for k in (0..n)) for n in (0..20)] # _G. C. Greubel_, Dec 29 2019
%o A003149 (GAP) F:=Factorial;; List([0..20], n-> Sum([0..n], k-> F(k)*F(n-k)) ); # _G. C. Greubel_, Dec 29 2019
%o A003149 (Python)
%o A003149 def a(n: int) -> int:
%o A003149     if n < 2: return n + 1
%o A003149     app, ap = 1, 2
%o A003149     for i in range(2, n + 1):
%o A003149         app, ap = ap, ((3 * i + 1) * ap - (i * i) * app) >> 1
%o A003149     return ap
%o A003149 print([a(n) for n in range(23)])  # _Peter Luschny_, Aug 08 2025
%Y A003149 Cf. A046825, A046878, A046879.
%Y A003149 Cf. A052186, A006932, A145878. - _Emeric Deutsch_, Oct 28 2008
%Y A003149 Cf. A324495, A324496, A324497 (problem similar to the random walks on the hypercube).
%K A003149 nonn,easy,nice
%O A003149 0,2
%A A003149 _N. J. A. Sloane_, _Henry Gould_
%E A003149 More terms from _Michel ten Voorde_, Apr 11 2001