A000337 -id:A000337 - cp's OEIS frontend

A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

0, 1, 3, 5, 9, 11, 14, 17, 25, 27, 30, 33, 38, 41, 45, 49, 65, 67, 70, 73, 78, 81, 85, 89, 98, 101, 105, 109, 115, 119, 124, 129, 161, 163, 166, 169, 174, 177, 181, 185, 194, 197, 201, 205, 211, 215, 220, 225, 242, 245, 249, 253, 259, 263, 268, 273, 283, 287, 292, 297, 304

Offset: 1

N. J. A. Sloane

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

a(A092246(n)) = A230720(n); a(A230709(n)) = A230721(n+1). - Reinhard Zumkeller, Oct 28 2013

D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Zak Seidov, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Terrillon Jean-Christophe, Hiroyuki Iida, Reaper Tournament System, 2018.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Mohd Nor Akmal Khalid, Hiroyuki Iida, Simulating competitiveness and precision in a tournament structure: a reaper tournament system, Int'l J. of Information Technology (2020) Vol. 12, 1-18.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Index entries for sequences related to sorting

Cf. A001855, A133457.

a003071 n = 1 - 2 ^ last es +
   sum (zipWith (*) (zipWith (+) es [0..]) (map (2 ^) es))
   where es = reverse $ a133457_row n
-- Reinhard Zumkeller, Oct 28 2013

a[1] = 0; a[n_] := a[n] = a[n-1] + 2^IntegerExponent[n-1, 2] + DigitCount[n-1, 2, 1] - 1; Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Feb 10 2012, after Henry Bottomley *)

Let n = 2^e_1 + 2^e_2 + ... + 2^e_t, e_1 > e_2 > ... > e_t >= 0, t >= 1. Then a(n) = 1 - 2^e_t + Sum_{k=1..t} (e_k + k - 1)*2^e_k [Knuth, Problem 14, Section 5.2.4].
a(n) = a(n-1) + A061338(n) = a(n-1) + A006519(n) + A000120(n) - 1 = n + A000337(A000523(n)) + a(n - 2^A000523(n)). a(2^k) = k*2^k + 1 = A002064(k). - Henry Bottomley, Apr 27 2001
G.f.: x/(1-x)^3 + 1/(1-x)^2*Sum(k>=1, (-1+(1-x)*2^(k-1))*x^2^k/(1-x^2^k)). - Ralf Stephan, Apr 17 2003

More terms from David W. Wilson

A036799 a(n) = 2 + 2^(n+1)*(n-1).

Original entry on oeis.org

0, 2, 10, 34, 98, 258, 642, 1538, 3586, 8194, 18434, 40962, 90114, 196610, 425986, 917506, 1966082, 4194306, 8912898, 18874370, 39845890, 83886082, 176160770, 369098754, 771751938, 1610612738, 3355443202, 6979321858, 14495514626, 30064771074, 62277025794

Offset: 0

N. J. A. Sloane

This sequence is a part of a class of sequences of the type: a(n) = Sum_{i=0..n} (C^i)*(i^k). This sequence has C=2, k=1. Sequence A036800 has C=2, k=2. Suppose C >= 2, k >= 1 are integers. What is the general closed form for a(n)? - Ctibor O. Zizka, Feb 07 2008
Partial sums of A036289. - Vladimir Joseph Stephan Orlovsky, Jul 09 2011
a(n) is the number of swaps needed in the worst case, when successively inserting 2^(n+1) - 1 keys into an initially empty binary heap (thus creating a tree with n+1 full levels). - Rudy van Vliet, Nov 09 2015
a(n) is also the total path length of the complete binary tree of height n, with nodes at depths 0,...,n. Total path length is defined to be the sum of depths over all nodes. - F. Skerman, Jul 02 2017
For n >= 1, every number greater than or equal to a(n-1) can be written as a sum of (not necessarily distinct) numbers of the form 2^n - 2^k with 0 <= k < n. However, a(n-1) - 1 cannot be written in this way. See problem N1 from the 2014 International Mathematics Olympiad Shortlist. - Dylan Nelson, Jun 02 2023

M. Petkovsek et al., A=B, Peters, 1996, p. 97.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 3, 4, 9.
Problem Selection Committee for the 2014 IMO, Shortlisted Problems with Solutions for the 55th International Mathematical Olympiad. See pp. 9, 68-70.
Stanislav Sykora, Finite and Infinite Sums of the Power Series (k^p)(x^k), DOI 10.3247/SL1Math06.002, Section V.
Index entries for linear recurrences with constant coefficients, signature (5,-8,4).

Cf. A000337, A036289, A036800, A232599, A232600, A232601, A232602.

a036799 n = (n-1)*2^(n+1) + 2  -- Reinhard Zumkeller, May 24 2012

[2+2^(n+1)*(n-1) : n in [0..40]]; // Wesley Ivan Hurt, Nov 12 2015

A036799:=n->2+2^(n+1)*(n-1): seq(A036799(n), n=0..40); # Wesley Ivan Hurt, Nov 12 2015

Accumulate[Table[n*2^n, {n, 0, 40}]] (* Vladimir Joseph Stephan Orlovsky, Jul 09 2011 *)

a(n)=2+(n-1)<<(n+1) \\ Charles R Greathouse IV, Sep 28 2015

concat(0, Vec(2*x/((1-x)*(1-2*x)^2) + O(x^40))) \\ Altug Alkan, Nov 09 2015

[2^(n+1)*(n-1) +2 for n in (0..40)] # G. C. Greubel, Mar 29 2021

a(n) = (n-1) * 2^(n+1) + 2.
a(n) = 2 * A000337(n).
a(n) = Sum_{k=1..n} k*2^k. - Benoit Cloitre, Oct 25 2002
G.f.: 2*x/((1-x)*(1-2*x)^2). - Colin Barker, Apr 30 2012
a(n) = 5*a(n-1) - 8*a(n-2) + 4*a(n-3) for n > 2. - Wesley Ivan Hurt, Nov 12 2015
a(n) = Sum_{k=0..n} Sum_{i=0..n} k * binomial(k,i). - Wesley Ivan Hurt, Sep 21 2017
E.g.f.: 2*exp(x) - 2*(1-2*x)*exp(2*x). - G. C. Greubel, Mar 29 2021

A173787 Triangle read by rows: T(n,k) = 2^n - 2^k, 0 <= k <= n.

Original entry on oeis.org

0, 1, 0, 3, 2, 0, 7, 6, 4, 0, 15, 14, 12, 8, 0, 31, 30, 28, 24, 16, 0, 63, 62, 60, 56, 48, 32, 0, 127, 126, 124, 120, 112, 96, 64, 0, 255, 254, 252, 248, 240, 224, 192, 128, 0, 511, 510, 508, 504, 496, 480, 448, 384, 256, 0, 1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512, 0

Offset: 0

Reinhard Zumkeller, Feb 28 2010

			Triangle begins as:
   0;
   1,  0;
   3,  2,  0;
   7,  6,  4,  0;
  15, 14, 12,  8,  0;
  31, 30, 28, 24, 16, 0;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

[2^n -2^k: k in [0..n], n in [0..15]]; // G. C. Greubel, Jul 13 2021

Table[2^n -2^k, {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 13 2021 *)

flatten([[2^n -2^k for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Jul 13 2021

A000120(T(n,k)) = A025581(n,k).
Row sums give A000337.
Central terms give A020522.
T(2*n+1, n) = A006516(n+1).
T(2*n+3, n+2) = A059153(n).
T(n, k) = A140513(n,k) - A173786(n,k), 0 <= k <= n.
T(n, k) = A173786(n,k) - A059268(n+1,k+1), 0 < k <= n.
T(2*n, 2*k) = T(n,k) * A173786(n,k), 0 <= k <= n.
T(n, 0) = A000225(n).
T(n, 1) = A000918(n) for n>0.
T(n, 2) = A028399(n) for n>1.
T(n, 3) = A159741(n-3) for n>3.
T(n, 4) = A175164(n-4) for n>4.
T(n, 5) = A175165(n-5) for n>5.
T(n, 6) = A175166(n-6) for n>6.
T(n, n-4) = A110286(n-4) for n>3.
T(n, n-3) = A005009(n-3) for n>2.
T(n, n-2) = A007283(n-2) for n>1.
T(n, n-1) = A000079(n-1) for n>0.
T(n, n) = A000004(n).

A119259 Central terms of the triangle in A119258.

Original entry on oeis.org

1, 3, 17, 111, 769, 5503, 40193, 297727, 2228225, 16807935, 127574017, 973168639, 7454392321, 57298911231, 441739706369, 3414246490111, 26447737520129, 205272288591871, 1595964714385409, 12427568655368191, 96905907580960769, 756583504975757311, 5913649000782757889

Offset: 0

Reinhard Zumkeller, May 11 2006

The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 06 2022

R. P. Stanley, Enumerative Combinatorics Volume 2, Cambridge Univ. Press, 1999, Theorem 6.33, p. 197.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. Abate and W. Whitt, Brownian Motion and the Generalized Catalan Numbers, J. Int. Seq. 14 (2011) # 11.2.6, eq (42).

Cf. A005408, A056220, A000225, A000337, A055580, A027608, A119258, A064062, A178792, A014300, A098665.

a119259 n = a119258 (2 * n) n  -- Reinhard Zumkeller, Aug 06 2014

Table[Binomial[2k - 1, k] Hypergeometric2F1[-2k, -k, 1 - 2k, -1], {k, 0, 10}] (* Vladimir Reshetnikov, Feb 16 2011 *)

from itertools import count, islice
def A119259_gen(): # generator of terms
    yield from (1,3)
    a, c = 2, 1
    for n in count(1):
        yield (a<>1
A119259_list = list(islice(A119259_gen(),20)) # Chai Wah Wu, Apr 26 2023

a(n) = A119258(2*n,n).
a(n) = Sum_{k=0..n} C(2*n,k)*C(2*n-k-1,n-k). - Paul Barry, Sep 28 2007
a(n) = Sum_{k=0..n} C(n+k-1,k)*2^k. - Paul Barry, Sep 28 2007
2*a(n) = A064062(n)+A178792(n). - Joseph Abate, Jul 21 2010
G.f.: (4*x^2+3*sqrt(1-8*x)*x-5*x)/(sqrt(1-8*x)*(2*x^2+x-1)-8*x^2-7*x+1). - Vladimir Kruchinin, Aug 19 2013
a(n) = (-1)^n - 2^(n+1)*binomial(2*n,n-1)*hyper2F1([1,2*n+1],[n+2],2). - Peter Luschny, Jul 25 2014
a(n) = (-1)^n + 2^(n+1)*A014300(n). - Peter Luschny, Jul 25 2014
a(n) = [x^n] ( (1 + x)^2/(1 - x) )^n. Exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + 3*x + 13*x^2 + 67*x^3 + ... is essentially the o.g.f. for A064062. - Peter Bala, Oct 01 2015
The o.g.f. is the diagonal of the bivariate rational function 1/(1 - t*(1 + x)^2/(1 - x)) and hence is algebraic by Stanley 1999, Theorem 6.33, p.197. - Peter Bala, Aug 21 2016
n*(3*n-4)*a(n) +(-21*n^2+40*n-12)*a(n-1) -4*(3*n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Aug 09 2017
From Peter Bala, Mar 23 2020: (Start)
a(p) == 3 ( mod p^3 ) for prime p >= 5. Cf. A002003, A103885 and A156894.
More generally, we conjecture that a(n*p^k) == a(n*p^(k-1)) ( mod p^(3*k) ) for prime p >= 5 and positive integers n and k. (End)
G.f.: (8*x)/(sqrt(1-8*x)*(1+4*x)-1+8*x). - Fabian Pereyra, Jul 20 2024
a(n) = 2^(n+1)*binomial(2*n,n) - A178792(n). - Akiva Weinberger, Dec 06 2024
a(n) = Sum_{k=0..n} 2^k * (-1)^(n-k) * binomial(2*n,k). - Seiichi Manyama, Jul 31 2025

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 6, 3, 8, 16, 24, 24, 24, 16, 8, 20, 60, 100, 120, 120, 120, 100, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210

Offset: 0

Alois P. Heinz, Feb 12 2019

T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).

T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
T(4,4) = 3: 1234, 1243, 1324.
T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   1;
   1,   1;
   2,   2,   2;
   3,   6,   6,   6,   3;
   8,  16,  24,  24,  24,  16,   8;
  20,  60, 100, 120, 120, 120, 100,  60,  20;
  80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Marko Riedel, math.stackexchange.com, Average number of inversions in a random binary heap on 2^n-1 elements.
Marko Riedel, Average number of inversions in a random binary heap on 2^n-1 elements (PDF).
Eric Weisstein's World of Mathematics, Heap,
Wikipedia, Binary heap.
Wikipedia, Permutation.

Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
Row sums give A000142.
Central terms (also maxima) of rows give A324075.
Cf. A000523, A008302, A061168, A120385, A306343, A324074, A372640.
Average number of inversions of a full binary heap on 2^n-1 elements is A000337.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
     If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
     Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
     Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 15 2021, after Alois P. Heinz *)

T(n,k) = T(n,A061168(n)-k) for n > 0.

Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).

A055580 Björner-Welker sequence: 2^n*(n^2 + n + 2) - 1.

Original entry on oeis.org

1, 7, 31, 111, 351, 1023, 2815, 7423, 18943, 47103, 114687, 274431, 647167, 1507327, 3473407, 7929855, 17956863, 40370175, 90177535, 200278015, 442499071, 973078527, 2130706431, 4647288831, 10099884031, 21877489663

Offset: 0

Wolfdieter Lang, May 26 2000; revised Feb 12 2001

a(n) is the d=1 Betti number of the complement of '3-equal' arrangements in n-dimensional real space, see Björner-Welker reference, Table I, pp. 308-309, column '1' with k=3 and Th. 5.2, pp. 297-298.
Binomial transform of [1/2, 2/3, 3/4, 4/5, ...] = 1/2, 7/6, 31/12, 111/20, 351/30, 1023/42, ..., where 2, 6, 12, 20, ... = A002378 (deleting the zero). - Gary W. Adamson, Apr 28 2005
Number of three-dimensional block structures associated with n joint systems in the construction of stable underground structures. - Richard M. Green, Jul 26 2011
Number of monotone mappings from the chain with three points to the complete binary tree of height n (n+1 levels). For example, the seven monotone mappings from the chain with three points (denoted 1,2,3, in order) to the complete binary tree with two levels (with a the root of the tree, and b, c the atoms) are: f(1)=f(2)=f(3)=a; f(1)=f(2)=a, f(3)=b; f(1)=f(2)=a, f(3)=c; f(1)=a, f(2)=f(3)=b; f(1)=a, f(2)=f(3)=c; f(1)=f(2)=f(3)=b; f(1)=f(2)=f(3)=c. - Pietro Codara, Mar 26 2015

H. Barcelo and S. Smith, The discrete fundamental group of the order complex of B_n, Abstract 1020-05-141, 1020th Meeting Amer. Math. Soc., Cincinatti, Ohio, Oct 21-22, 2006.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Henry Adams, Samir Shukla, and Anurag Singh, Čech complexes of hypercube graphs, arXiv:2212.05871 [math.CO], 2022.
H. Barcelo and R. Laubenbacher, Perspectives on A-homotopy theory and its applications, Discr. Math., 298 (2005), 39-61.
H. Barcelo and S. Smith, The discrete fundamental group of the order complex of B_n, arXiv:0711.0915 [math.CO], 2007.
A. Björner and V. Welker, The homology of "k-equal" manifolds and related partition lattices, Adv. Math., 110 (1995), 277-313.
Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
Robert Davis and Greg Simay, Further Combinatorics and Applications of Two-Toned Tilings, arXiv:2001.11089 [math.CO], 2020.
G.G. Kocharyan and A.M. Kulyukin, Construction of a three-dimensional block structure on the basis of jointed rock parameters estimating the stability of underground workings, Soil Mech. Found. Eng., 31 (1994), 62-66.
A. F. Y. Zhao, Pattern Popularity in Multiply Restricted Permutations, Journal of Integer Sequences, 17 (2014), #14.10.3.
Index entries for linear recurrences with constant coefficients, signature (7,-18,20,-8).

Fourth column of triangle A055252.

Cf. A055252, A055249, A045618, A000337, A001788, A066185.

[2^n*(n^2+n+2)-1: n in [0..35]]; // Vincenzo Librandi, Jul 28 2011

Table[ n*(n+1)*2^(n-2), {n, 0, 26}] // Accumulate // Rest (* Jean-François Alcover, Jul 09 2013, after Paul Barry *)
LinearRecurrence[{7,-18,20,-8},{1,7,31,111},30] (* Harvey P. Dale, Nov 27 2014 *)

a(n)=(n^2+n+2)<Charles R Greathouse IV, Jul 28 2011

a(n) = A055252(n+3, 3).
a(n) = Sum_{j=0..n-1} a(j) + A045618(n), n >= 1.
G.f.: 1/((1-2*x)^3*(1-x)).
Partial sums of A001788 (without leading zero). - Paul Barry, Jun 26 2003
a(n) = A001788(n) - A000337(n). - Jon Perry, Dec 12 2003
a(n) = A119258(n+4,n). - Reinhard Zumkeller, May 11 2006
E.g.f.: 2*(1 + 2*x + 2*x^2)*exp(2*x) - exp(x). - G. C. Greubel, Oct 28 2016
a(n) = Sum_{k=0..n+1} Sum_{i=0..n+1} i^2 * C(k,i). - Wesley Ivan Hurt, Sep 21 2017

Edited (for consistency with change of offset) by M. F. Hasler, Nov 03 2012

A063090 a(n)/(n*n!) is the average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order.

Original entry on oeis.org

1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000

Offset: 1

Rob Arthan, Aug 06 2001

a(n) is the sum over all permutations, p, of {1, ..., n} of the number of comparisons required to find all the entries in the tree formed when the order of insertion is p(1), p(2), ... p(n). To derive the formula given, first group the trees according to the value of k = p(1). For a given k, p determines a permutation of {1, ..., k-1} that gives the structure of the left subtree. By symmetry, the contribution of the right subtrees will be the same as the left subtrees. Now count and simplify.

a(n) mod n is n-2 or 0 depending on whether n is prime or not. - Gary Detlefs, May 28 2012

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 427, C(n).

T. D. Noe, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Quicksort.

Cf. A000108, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971.

[Factorial(n)*((2*n+2)*HarmonicNumber(n) - 3*n): n in [1..30]]; // G. C. Greubel, Sep 01 2018

A[1]:= 1:
for n from 2 to 30 do A[n]:= (2*n-1)*(n-1)!+(n+1)*A[n-1] od:
seq(A[n],n=1..30); # Robert Israel, Sep 21 2014

a[n_] := n!*((2*n+2)*HarmonicNumber[n] - 3*n); Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 20 2012, after Gary Detlefs *)

{h(n) = sum(k=1,n, 1/k)};
for(n=1,30, print1(n!*(2*(n+1)*h(n) - 3*n), ", ")) \\ G. C. Greubel, Sep 01 2018

a(1) = 1, a(n) = n*n! + 2 * Sum_{k=1}^{n-1} (n-1)!/k! * a(k).
a(n) = (2*n - 1)*(n - 1)! + (n + 1)*a(n-1).
E.g.f.: -(x+2*log(1-x))/(1-x)^2. - Vladeta Jovovic, Sep 15 2003
a(n) = Sum_{k=0..n} |Stirling1(n, k)|*A000337(k). - Vladeta Jovovic, Jul 06 2004
a(n) = 2*(n+1)*abs(Stirling1(n+1, 2))-3*n*n!. - Vladeta Jovovic, Jul 06 2004
a(n) = n!*((2*n+2)*h(n) - 3*n), where h(n) is the n-th harmonic number. - Gary Detlefs, May 28 2012
a(n) = A288964(n) + n!*n (because this sequence and A288964 have the same definition related to quicksort but under slightly different assumptions). - Petros Hadjicostas, May 03 2020

More terms from Vladeta Jovovic, Aug 08 2001

Missing brackets in the formula in the name inserted by Rob Arthan, Sep 21 2014

A034015 Small 3-Schroeder numbers: a(n) = A027307(n+1)/2.

Original entry on oeis.org

1, 5, 33, 249, 2033, 17485, 156033, 1431281, 13412193, 127840085, 1235575201, 12080678505, 119276490193, 1187542872989, 11909326179841, 120191310803937, 1219780566014657, 12440630635406245, 127446349676475425, 1310820823328281561, 13530833791486094769

Offset: 0

N. J. A. Sloane

Series reversion of x*(Sum_{k>=0} a(k)(-x^2)^k) is Sum_{k odd} C(k)x^k where C() is Catalan numbers A000108.
Series reversion of x*(Sum_{k>=0} a(k)(-x)^k) is A000337(x). (Michael Somos)
This sequence should really have started with a(0)=1, a(1)=1, a(2)=5, a(3)=33, ..., but the present offset is too well-established. - N. J. A. Sloane, Mar 28 2021
This is the number of hypoplactic classes of 2-parking functions of size n+1. - Jun Yan, Apr 13 2024

Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.

Alois P. Heinz, Table of n, a(n) for n = 0..500
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014-2020.
Jun Yan, Results on pattern avoidance in parking functions, arXiv preprint arXiv:2404.07958 [math.CO], 2024. See Theorem 4.4.

Part of a family indexed by m: m=2 (A001003), m=3 is this sequence, m=4 is A243675, ....
The sequences listed in Yang-Jiang's Table 1 appear to be A006318, A001003, A027307, A034015, A144097, A243675, A260332, A243676. - N. J. A. Sloane, Mar 28 2021
Apart from the first term, this is A027307/2. - N. J. A. Sloane, Mar 28 2021

a:= proc(n) option remember; `if`(n<2, 4*n+1,
      ((110*n^3+66*n^2-17*n-9) *a(n-1)
       +(n-1)*(2*n-1)*(5*n+3) *a(n-2)) /
      ((2*n+3)*(5*n-2)*(n+1)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 22 2014

a[n_] := If[n<0, 0, Sum[2^i*Binomial[2*n+2, i]*Binomial[n+1, i+1]/(n+1), {i, 0, n}]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 13 2014, after PARI *)
a[n_] := Hypergeometric2F1[-n, -2 (n + 1), 2, 2];
Table[a[n], {n, 0, 20}]  (* Peter Luschny, Nov 08 2021 *)

a(n)=if(n<0,0,sum(i=0,n,2^i*binomial(2*n+2,i)*binomial(n+1,i+1))/(n+1))

a(n) = Sum_{i=0..n} Sum_{j=0..i} (-2)^(n-i)*binomial(i,j)*binomial(2i+j, n)*binomial(n+1,i)/(n+1) (conjectured). - Michael D. Weiner, May 25 2017
Yang & Jiang (2021) give an explicit formula for a(n) in Theorems 2.4 and 2.9. - N. J. A. Sloane, Mar 28 2021 [This formula is: a(n) = (1/(n + 1)) * Sum_{k=1..n+1} binomial(2*n + 2, k - 1) * binomial(n + 1, k)*2^(k - 1). - Jun Yan, Apr 13 2024]
a(n) = hypergeom([-n, -2*(n + 1)], [2], 2). - Peter Luschny, Nov 08 2021
a(n) ~ phi^(5*n + 6) / (4 * 5^(1/4) * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Nov 08 2021
D-finite with recurrence +2*(2*n+3)*(n+1)*a(n) +(-46*n^2-43*n-9)*a(n-1) +3*(6*n^2-14*n+7)*a(n-2) +(2*n-3)*(n-2)*a(n-3)=0. - R. J. Mathar, Aug 01 2022
Let D(n) be the set of 2-Dyck paths that have n up-steps of size 2 and 2n down-steps of size 1 and never go below the x-axis. For every d in D(n), let peak(d) be the number of peaks in d. Then a(n) = Sum_{d in D(n+1)}2^(peak(d) - 1). - Jun Yan, Apr 13 2024
a(n) = (-1)^(n) * Jacobi_P(n, 1, n+2, -3)/(n+1). - Peter Bala, Sep 08 2024

A055249 Triangle of partial row sums (prs) of triangle A055248 (prs of Pascal's triangle A007318).

Original entry on oeis.org

1, 3, 1, 8, 4, 1, 20, 12, 5, 1, 48, 32, 17, 6, 1, 112, 80, 49, 23, 7, 1, 256, 192, 129, 72, 30, 8, 1, 576, 448, 321, 201, 102, 38, 9, 1, 1280, 1024, 769, 522, 303, 140, 47, 10, 1, 2816, 2304, 1793, 1291, 825, 443, 187, 57, 11, 1, 6144, 5120, 4097, 3084, 2116, 1268, 630

Offset: 0

Wolfdieter Lang, May 26 2000

In the language of the Shapiro et al. reference (given in A053121) such a lower triangular (ordinary) convolution array, considered as matrix, belongs to the Riordan-group. The G.f. for the row polynomials p(n,x) (increasing powers of x) is ((1-z)/(1-2*z)^2)/(1-x*z/(1-z)).
This is the second member of the family of Riordan-type matrices obtained from A007318(n,m) (Pascal's triangle read as lower triangular matrix) by repeated application of the prs-procedure.
The column sequences appear in A001792, A001787, A000337, A045618, A045889, A034009, A055250, A055251 for m=0..7.

			1;
3,1;
8,4,1;
20,12,5,1;
...
Fourth row polynomial (n=3): p(3,x)= 20+12*x+5*x^2+x^3

G. C. Greubel, Table of n, a(n) for n = 0..1274

Cf. A007318, A055248, A008949. Row sums: A049611(n+1) = A055252(n, 0).

a[n_, m_] := Binomial[n, m]*Hypergeometric2F1[2, m-n, m+1, -1]; Table[a[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Jean-François Alcover, Mar 11 2014 *)

a(n, m) = Sum_{k=m,..,n} ( A055248(n, k) ), n >= m >= 0, a(n, m) := 0 if n

Column m recursion: a(n, m) = Sum_{j=m,..,(n-1)} ( a(j, m) ) + A055248(n, m), n >= m >= 0, a(n, m) := 0 if n

G.f. for column m: ((1-x)/(1-2*x)^2)*(x/(1-x))^m, m >= 0.

a(n, m) = binomial(n, m) * 2F1(2, m-n; m+1; -1) where 2F1 is the hypergeometric function. Jean-François Alcover, Mar 11 2014

A187059 The exponent of highest power of 2 dividing the product of the elements of the n-th row of Pascal's triangle (A001142).

Original entry on oeis.org

0, 0, 1, 0, 5, 2, 4, 0, 17, 10, 12, 4, 18, 8, 11, 0, 49, 34, 36, 20, 42, 24, 27, 8, 58, 36, 39, 16, 47, 22, 26, 0, 129, 98, 100, 68, 106, 72, 75, 40, 122, 84, 87, 48, 95, 54, 58, 16, 162, 116, 119, 72, 127, 78, 82, 32, 147, 94, 98, 44, 108, 52, 57, 0, 321, 258, 260, 196, 266, 200, 203, 136, 282, 212, 215, 144, 223, 150, 154, 80, 322, 244, 247, 168, 255, 174, 178, 96, 275, 190, 194, 108, 204, 116, 121, 32, 418, 324, 327, 232, 335

Offset: 0

Bruce Reznick, Mar 05 2011

The exponent of the highest power of 2 which divides Product_{k=0..n} binomial(n, k). This can be computed using de Polignac's formula.

This is the function ord_2(Ḡ_n) extensively studied in Lagarias-Mehta (2014), and plotted in Fig. 1.1. - Antti Karttunen, Oct 22 2014

			For example, if n = 4, the power of 2 that divides 1*4*6*4*1 is 5.

I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, Wiley, 1991, pages 182, 183, 187 (Ex. 34).

Antti Karttunen and Paul Tek, Table of n, a(n) for n = 0..8191 (First 4096 terms from Karttunen)
J. Lagarias, Products of binomial coefficients and Farey fractions, Lecture in DIMACS Conference on Challenges of Identifying Integer Sequences, October 9, 2014; Part 1, Part 2.
Jeffrey C. Lagarias and Harsh Mehta, Products of binomial coefficients and unreduced Farey fractions, arXiv:1409.4145 [math.NT], 2014.

Row sums of triangular table A065040.
Row 1 of array A249421.
Cf. A000295 (a(2^k-2)), A000337 (a(2^k)), A005803 (a(2^k-3)), A036799 (a(2^k+1)), A109363 (a(2^k-4)).
Cf. A000178, A000788, A001142, A002109, A007318, A007814, A174605, A249152, A249150, A249151, A249154, A249343, A249345, A249346, A249347.

a187059 = a007814 . a001142  -- Reinhard Zumkeller, Mar 16 2015

a[n_] := Sum[IntegerExponent[Binomial[n, k], 2], {k, 0, n}]; Array[a, 100, 0]
A187059[n_] := Sum[#*((#+1)*2^k - n - 1) & [Floor[n/2^k]], {k, Floor[Log2[n]]}];
Array[A187059, 100, 0] (* Paolo Xausa, Feb 11 2025 *)
2*Accumulate[#] - Range[Length[#]]*# & [DigitCount[Range[0, 99], 2, 1]] (* Paolo Xausa, Feb 11 2025 *)

a(n)=sum(k=0,n,valuation(binomial(n,k),2))

\\ Much faster version, based on code for A065040 by Charles R Greathouse IV which if reduced even further gives the formula a(n) = 2*A000788(n) - A249154(n):
A065040(m,k) = (hammingweight(k)+hammingweight(m-k)-hammingweight(m));
A187059(n) = sum(k=0, n, A065040(n, k));
for(n=0, 4095, write("b187059.txt", n, " ", A187059(n)));
\\ Antti Karttunen, Oct 25 2014

def A187059(n): return (n+1)*n.bit_count()+sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1)) # Chai Wah Wu, Nov 11 2024

a(2^k-1) = 0 (19th century); a(2^k) = (k-1)*2^k+1 for k >= 1. (Use de Polignac.)
a(n) = Sum_{i=0..n} A065040(n,i) [where the entries of triangular table A065040(m,k) give the exponent of the maximal power of 2 dividing binomial coefficient A007318(m,k)].
a(n) = A007814(A001142(n)). - Jason Kimberley, Nov 02 2011
a(n) = A249152(n) - A174605(n). [Exponent of 2 in the n-th hyperfactorial minus exponent of 2 in the n-th superfactorial. Cf. for example Lagarias & Mehta paper or Peter Luschny's formula for A001142.] - Antti Karttunen, Oct 25 2014
a(n) = 2*A000788(n) - A249154(n). - Antti Karttunen, Nov 02 2014
a(n) = Sum_{i=1..n} (2*i-n-1)*v_2(i), where v_2(i) = A007814(i) is the exponent of the highest power of 2 dividing i. - Ridouane Oudra, Jun 02 2022
a(n) = Sum_{k=1..floor(log_2(n))} t*((t+1)*2^k - n - 1), where t = floor(n/(2^k)). - Paolo Xausa, Feb 11 2025, derived from Ridouane Oudra's formula above.

Name clarified by Antti Karttunen, Oct 22 2014

Previous Showing 11-20 of 70 results. Next

cp's OEIS Frontend

A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A036799 a(n) = 2 + 2^(n+1)*(n-1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A173787 Triangle read by rows: T(n,k) = 2^n - 2^k, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Programs

Magma

Mathematica

Sage

Formula

A119259 Central terms of the triangle in A119258.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A055580 Björner-Welker sequence: 2^n*(n^2 + n + 2) - 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula