A129952 Binomial transform of A124625.

1, 1, 2, 6, 16, 40, 96, 224, 512, 1152, 2560, 5632, 12288, 26624, 57344, 122880, 262144, 557056, 1179648, 2490368, 5242880, 11010048, 23068672, 48234496, 100663296, 209715200, 436207616, 905969664, 1879048192, 3892314112

Offset: 0

Author

Paul Curtz, Jun 10 2007

Keywords

• nonn
• easy

Comments

Essentially the same as A057711: a(n) = A057711(n) for n >= 1.

Number of permutations of length n>=0 avoiding the partially ordered pattern (POP) {1>2, 1>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and third elements. - Sergey Kitaev, Dec 08 2020

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
• Index entries for linear recurrences with constant coefficients, signature (4,-4).

Crossrefs

Cf. A124625, A045623, A057711, A129953 (first differences), A129954 (second differences), A129955 (third differences).

Programs

Magma

m:=15; S:=&cat[ [ 1, 2*i ]: i in [0..m] ]; [ &+[ Binomial(j-1, k-1)*S[k]: k in [1..j] ]: j in [1..2*m] ]; // Klaus Brockhaus, Jun 17 2007

Mathematica

LinearRecurrence[{4, -4}, {1, 1, 2, 6}, 30] (* G. C. Greubel, Jun 08 2016; corrected by Georg Fischer, Apr 02 2019 *)

PARI

{m=29; print1(1, ",", 1, ","); for(n=2, m, print1(n*2^(n-2), ","))} \\ Klaus Brockhaus, Jun 17 2007

Python

def A129952(n): return n<1 else 1 # Chai Wah Wu, Oct 03 2024

Formula

a(0) = 1, a(1) = 1; for n > 1, a(n) = n*2^(n-2).

G.f.: (1-3*x+2*x^2+2*x^3)/(1-2*x)^2.

E.g.f.: (1/2)*(x*exp(2*x) + x + 2). - G. C. Greubel, Jun 08 2016

Extensions

Edited and extended by Klaus Brockhaus, Jun 17 2007