A189391 The minimum possible value for the apex of a triangle of numbers whose base consists of a permutation of the numbers 0 to n, and each number in a higher row is the sum of the two numbers directly below it.
0, 1, 3, 8, 19, 44, 98, 216, 467, 1004, 2134, 4520, 9502, 19928, 41572, 86576, 179587, 372044, 768398, 1585416, 3263210, 6711176, 13775068, 28255568, 57863214, 118430584, 242061468, 494523536, 1009105372, 2058327344, 4194213448
Offset: 0
Examples
For n = 4 consider the triangle: ....19 ...8 11 ..5 3 8 .4 1 2 6 3 1 0 2 4 This triangle has 19 at its apex and no other such triangle with the numbers 0 - 4 on its base has a smaller apex value, so a(4) = 19.
Links
- Nathaniel Johnston, Table of n, a(n) for n = 0..1000
- F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60. - From _N. J. A. Sloane_, May 04 2012
- Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.
- Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. - _N. J. A. Sloane_, Sep 20 2018
Crossrefs
Programs
-
Magma
m:=30; R
:=PowerSeriesRing(Rationals(), m); [0] cat Coefficients(R!((2*x+Sqrt(1-4*x^2)-1)/(2*(2*x-1)^2))); // G. C. Greubel, Aug 24 2018 -
Maple
a:=proc(n)return add((2*n-4*k-1)*binomial(n,k),k=0..floor((n-1)/2)): end: seq(a(n),n=0..50);
-
Mathematica
CoefficientList[Series[(2*x+Sqrt[1-4*x^2]-1) / (2*(2*x-1)^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 16 2014 *) -
PARI
A189391(n)=sum(i=0,(n-1)\2,(2*n-4*i-1)*binomial(n,i)) \\ M. F. Hasler, Jan 24 2012
Formula
If n even, a(n) = (n+1/2)*binomial(n,n/2) - 2^(n-1); if n odd, a(n) = ((n+1)/2)*binomial(n+1,(n+1)/2) - 2^(n-1). - N. J. A. Sloane, Nov 01 2018
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-4*k-1)*binomial(n,k).
G.f.: (2*x+sqrt(1-4*x^2)-1) / (2*(2*x-1)^2). - Alois P. Heinz, Feb 09 2012
a(n) ~ 2^n * (sqrt(2n/Pi)- 1/2). - Vaclav Kotesovec, Mar 16 2014 (formula simplified by Lewis Chen, May 25 2017)
D-finite with recurrence n*a(n) + (n-5)*a(n-1) + 2*(-5*n+6)*a(n-2) + 4*(-n+8)*a(n-3) + 24*(n-3)*a(n-4) = 0. - R. J. Mathar, Jan 04 2017
From Wolfdieter Lang, Feb 18 2017:(Start)
G.f.: c(x^2)*Tri(x*c(x^2)), with c and Tri the g.f. of A000108 and A000217, respectively. See the explicit form of the g.f. given above by Alois P. Heinz.
(End)
2*a(n) = A152548(n)-2^n. - R. J. Mathar, Jun 17 2021
Comments