A049039 -id:A049039 - cp's OEIS frontend

A337300 Partial sums of the geometric Connell sequence A049039.

1, 3, 7, 12, 19, 28, 39, 51, 65, 81, 99, 119, 141, 165, 191, 218, 247, 278, 311, 346, 383, 422, 463, 506, 551, 598, 647, 698, 751, 806, 863, 921, 981, 1043, 1107, 1173, 1241, 1311, 1383, 1457, 1533, 1611, 1691, 1773, 1857, 1943, 2031, 2121, 2213, 2307, 2403

Offset: 1

Kevin Ryde, Aug 22 2020

a(n) is Newey's "more complicated" conjectured length of the shortest sequence containing all permutations of 1..n (A062714). It agrees with A062714(n) for n <= 7. [But not for n=8. - Pontus von Brömssen, Aug 18 2025]

Kevin Ryde, Table of n, a(n) for n = 1..5000
Malcolm Newey, Notes On a Problem Involving Permutations As Subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973. Conjectured M(n) formula bottom of page 12.

Cf. A000295, A049039 (first differences), A062714, A122793 (arithmetic Connell sums).

a(n) = my(k=logint(n,2)); n^2 - k*(n+1) + (2<

a(n) = n^2 - k*n + F(k) where k = floor(log_2(n)) and F(0) = 0 then F(k) = k + 2*F(k-1) [Newey], which is F(k) = 2^(k+1) - k - 2 = A000295(k+1), the Eulerian numbers.
a(n) = n^2 - k*(n+1) + 2*(2^k - 1) where k = floor(log_2(n)).
G.f.: 2*x/(1-x)^3 - ( Sum_{j>=0} x^(2^j) )/(1-x)^2.
a(n) = Sum_{i=1..n} A049039(i). - Gerald Hillier, Jun 18 2016

A160464 The Eta triangle.

Original entry on oeis.org

-1, -11, 2, -114, 29, -2, -3963, 1156, -122, 4, -104745, 32863, -4206, 222, -4, -3926745, 1287813, -184279, 12198, -366, 4, -198491580, 67029582, -10317484, 781981, -30132, 562, -4

Offset: 2

Johannes W. Meijer, May 24 2009

The ES1 matrix coefficients are defined by ES1[2*m-1,n] = 2^(2*m-1) * int(y^(2*m-1)/(cosh(y))^(2*n),y=0..infinity)/(2*m-1)! for m = 1, 2, 3, .. and n = 1, 2, 3 .. .
This definition leads to ES1[2*m-1,n=1] = 2*eta(2*m-1) and the recurrence relation ES1[2*m-1,n] = ((2*n-2)/(2*n-1))*(ES1[2*m-1,n-1] - ES1[2*m-3,n-1]/(n-1)^2) which we used to extend our definition of the ES1 matrix coefficients to m = 0, -1, -2, .. . We discovered that ES1[ -1,n] = 0.5 for n = 1, 2, .. . As usual eta(m) = (1-2^(1-m))*zeta(m) with eta(m) the Dirichlet eta function and zeta(m) the Riemann zeta function.
The coefficients in the columns of the ES1 matrix, for m = 1, 2, 3, .. , and n = 2, 3, 4 .. , can be generated with the polynomials GF(z,n) for which we found the following general expression GF(z;n) = ((-1)^(n-1)*r(n)*CFN1(z,n)*GF(z;n=1) + ETA(z,n))/p(n).
The CFN1(z,n) polynomials depend on the central factorial numbers A008955.
The ETA(z,n) are the Eta polynomials which lead to the Eta triangle.
The zero patterns of the Eta polynomials resemble a UFO. These patterns resemble those of the Zeta, Beta and Lambda polynomials, see A160474, A160480 and A160487.
The first Maple algorithm generates the coefficients of the Eta triangle. The second Maple algorithm generates the ES1[2*m-1,n] coefficients for m= 0, -1, -2, -3, .. .
The M(n) sequence, see the second Maple algorithm, leads to Gould's sequence A001316 and a sequence that resembles the denominators of the Taylor series for tan(x), A156769(n).
Some of our results are conjectures based on numerical evidence, see especially A160466.

			The first few rows of the triangle ETA(n,m) with n=2,3,.. and m=1,2,... are
  [ -1]
  [ -11, 2]
  [ -114, 29, -2]
  [ -3963, 1156, -122, 4].
The first few ETA(z,n) polynomials are
  ETA(z,n=2) = -1;
  ETA(z,n=3) = -11+2*z^2;
  ETA(z,n=4) = -114 + 29*z^2 - 2*z^4.
The first few CFN1(z,n) polynomials are
  CFN1(z,n=2) = (z^2-1);
  CFN1(z,n=3) = (z^4 - 5*z^2 + 4);
  CFN1(z,n=4) = (z^6 - 14*z^4 + 49*z^2 - 36).
The first few generating functions GF(z;n) are:
  GF(z;n=2) = ((-1)*2*(z^2 - 1)*GF(z;n=1) + (- 1))/3;
  GF(z;n=3) = (4*(z^4 - 5*z^2+4) *GF(z;n=1) + (-11 + 2*z^2))/30;
  GF(z;n=4) = ((-1)*4*(z^6 - 14*z^4 + 49*z^2 - 36)*GF(z;n=1) + (-114 + 29*z^2 - 2*z^4))/315.

Mohammad K. Azarian, Problem 1218, Pi Mu Epsilon Journal, Vol. 13, No. 2, Spring 2010, p. 116. Solution published in Vol. 13, No. 3, Fall 2010, pp. 183-185.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, Chapter 23, pp. 811-812.
Johannes W. Meijer, The zeros of the Eta, Zeta, Beta and Lambda polynomials, jpg and pdf, Mar 03 2013.
J. W. Meijer and N.H.G. Baken, The Exponential Integral Distribution, Statistics and Probability Letters, Volume 5, No.3, April 1987. pp 209-211.
Eric. W. Weisstein, Dirichlet Eta Function, Wolfram MathWorld.

The r(n) sequence equals A062383 (n>=1).
The p(n) sequence equals A160473(n) (n>=2).
The GCS(n) sequence equals the Geometric Connell sequence A049039(n).
The M(n-1) sequence equals A001316(n-1)/A156769(n) (n>=1).
The q(n) sequence leads to A081729 and the 'gossip sequence' A007456.
The first right hand column equals A053644 (n>=1).
The first left hand column equals A160465.
The row sums equal A160466.
The CFN1(z, n) and the cfn1(n, k) lead to A008955.
Cf. A094665 and A160468.
Cf. the Zeta, Beta and Lambda triangles A160474, A160480 and A160487.
Cf. A162440 (EG1 matrix).

nmax:=8; c(2 ):= -1/3: for n from 3 to nmax do c(n) := (2*n-2)*c(n-1)/(2*n-1)-1/((n-1)*(2*n-1)) end do: for n from 2 to nmax do GCS(n-1) := ln(1/(2^(-(2*(n-1)-1-floor(ln(n-1)/ ln(2))))))/ln(2); p(n) := 2^(-GCS(n-1))*(2*n-1)!; ETA(n, 1) := p(n)*c(n); ETA(n, n) := 0 end do: mmax:=nmax: for m from 2 to mmax do for n from m+1 to nmax do q(n) := (1+(-1)^(n-3)*(floor(ln(n-1)/ln(2)) - floor(ln(n-2)/ln(2)))): ETA(n, m) := q(n)*((-1)*ETA(n-1, m-1)+(n-1)^2*ETA(n-1, m)) end do end do: seq(seq(ETA(n,m), m=1..n-1), n=2..nmax);
# End first program.
nmax1:=20; m:=1; ES1row:=1-2*m; with (combinat): cfn1 := proc(n, k): sum((-1)^j*stirling1(n+1, n+1-k+j) * stirling1(n+1, n+1-k-j), j=-k..k) end proc: mmax1:=nmax1: for m1 from 1 to mmax1 do M(m1-1) := 2^(2*m1-2)/((2*m1-1)!); ES1[-2*m1+1,1] := 2*(1-2^(1-(1-2*m1)))*(-bernoulli(2*m1)/(2*m1)) od: for n from 2 to nmax1 do for m1 from 1 to mmax1-n+1 do ES1[1-2*m1, n] := (-1)^(n-1)*M(n-1)*sum((-1)^(k+1)*cfn1(n-1,k-1)* ES1[2*k-2*n-2*m1+1, 1], k=1..n) od: od: seq(ES1[1-2*m, n], n=1..nmax1-m+1);
# End second program.

We discovered an interesting relation between the Eta triangle coefficients ETA(n,m) = q(n)*((-1)*ETA(n-1,m-1)+(n-1)^2*ETA(n-1,m)), for n = 3, 4, ... and m = 2, 3, ... , with
q(n) = 1 + (-1)^(n-3)*(floor(log(n-1)/log(2)) - floor(log(n-2)/log(2))) for n = 3, 4, ....
See A160465 for ETA(n,m=1) and furthermore ETA(n,n) = 0 for n = 2, 3, ....
The generating functions GF(z;n) of the coefficients in the matrix columns are defined by
GF(z;n) = sum_{m>=1} ES1[2*m-1,n] * z^(2*m-2), with n = 1, 2, 3, .... This leads to
GF(z;n=1) = (2*log(2) - Psi(z) - Psi(-z) + Psi(1/2*z) + Psi(-1/2*z)); Psi(z) is the digamma-function.
GF(z;n) = ((2*n-2)/(2*n-1)-2*z^2/((n-1)*(2*n-1)))*GF(z;n-1)-1/((n-1)*(2*n-1)).
We found for GF(z;n), for n = 2, 3, ..., the following general expression:
GF(z;n) = ((-1)^(n-1)*r(n)*CFN1(z,n)*GF(z;n=1) + ETA(z,n) )/p(n) with
r(n) = 2^floor(log(n-1)/log(2)+1) and
p(n) = 2^(-GCS(n))*(2*n-1)! with
GCS(n) = log(1/(2^(-(2*(n-1)-1-floor(log(n-1)/ log(2))))))/log(2).

A062714 Minimal length of a sequence with terms from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

Original entry on oeis.org

1, 3, 7, 12, 19, 28, 39, 52

Offset: 1

N. J. A. Sloane, Jul 14 2001

For n >= 7, a(n) <= ceiling(n^2 - (7/3)*n + 19/3) as proved by Radomirovic (2012).
From Jon E. Schoenfield, Jul 27 2009: (Start)
For n > 2, a(n) <= (n-1)^2 + 3, and an easy solution at this upper bound can be obtained by cycling n-3 times through the digits 2 through n and appending the digits 2 and 3 once at the end, inserting a 1 at the beginning and after every n-2 digits thereafter until the last digit is reached, and finally prepending the digits 1 through n. For example:
  n=3 (7 digits): 123 1 2 1 3
  n=4 (12 digits): 1234 1 23 1 42 1 3
  n=5 (19 digits): 12345 1 234 1 523 1 452 1 3
  n=6 (28 digits): 123456 1 2345 1 6234 1 5623 1 4562 1 3
  n=7 (39 digits): 1234567 1 23456 1 72345 1 67234 1 56723 1 45672 1 3
Equivalently, for n > 2, the i-th digit can be computed as
  i for i <= n,
  1 for i > n and (i-2) == 0 (mod (n-1)), and
  (floor((i-1)*(n-2)/(n-1)) mod (n-1)) + 2 otherwise.
However, the above approach is not always optimal; e.g., at n = 16, it gives a valid solution in (16-1)^2 + 3 = 228 digits, but the following (using the letters a through g for the numbers 10 through 16) is an example of a 227-digit solution:
  123456789a bcdefg1234 56789abcde f1g2345678 9abcde1f2g
  3456789abc d1e2f3g456 789abc1d2e 3f4g56789a b1c2d3e4f5
  g6789a1b2c 3d4e5f6g78 91a2b3c4d5 e6f7g8192a 3b4c5d6e7f
  18g293a4b5 c6d17ef82g 394a5b16cd 7ef283g491 56abcd7e2f
  3814569abc dg72e13456 89abcdf
(End)
Oliver Tan (2022) proves that for any integer s >= 2, there are infinitely many integers n for which there exists a sequence of length ceiling(n^2 - (5s-3)/(2s-1)*n + (2s^2+9s-7)/(2s-1)) which contains, as a subsequence, all permutations of a set of n symbols. In particular, if s=2, the above yields Radomirovic's expression. With s > 2, it produces shorter sequences than Radomirovic's for larger n. As s approaches infinity, the length approaches ceiling(n^2 - (5/2)*n + C). Formally, for any epsilon > 0, there is a constant C_epsilon such that there are infinitely many integers n for which there exists a sequence of length ceiling(n^2 - (5/2-epsilon)*n + C_epsilon). - Oliver Tan, Jan 22 2022

			1, 2, 3, 1, 2, 3, 1 contains as a subsequence all of 123, ..., 321 and is minimal, so a(3) = 7.
From _John W. Layman_, Aug 29 2008: (Start)
The following is a sequence of length a(5)=19 with terms from 1,2,...,5 that contains as subsequences all of the 120 permutations of 1,2,...,5:
{1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,2,3,5,1}
The proof is shown here:
{1,2,3,4,5,-,-,-,-,-,-,-,-,-,-,-,-,-,-}
{1,2,3,-,5,-,-,-,4,-,-,-,-,-,-,-,-,-,-}
{1,2,-,4,-,-,-,3,-,-,5,-,-,-,-,-,-,-,-}
{1,2,-,4,5,-,-,3,-,-,-,-,-,-,-,-,-,-,-}
{1,2,-,-,5,-,-,3,4,-,-,-,-,-,-,-,-,-,-}
{1,2,-,-,5,-,-,-,4,-,-,-,3,-,-,-,-,-,-}
{1,-,3,-,-,-,2,-,4,-,5,-,-,-,-,-,-,-,-}
{1,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,-}
{1,-,3,4,-,-,2,-,-,-,5,-,-,-,-,-,-,-,-}
{1,-,3,4,5,-,2,-,-,-,-,-,-,-,-,-,-,-,-}
{1,-,3,-,5,-,2,-,4,-,-,-,-,-,-,-,-,-,-}
{1,-,3,-,5,-,-,-,4,-,-,2,-,-,-,-,-,-,-}
{1,-,-,4,-,-,2,3,-,-,5,-,-,-,-,-,-,-,-}
{1,-,-,4,-,-,2,-,-,-,5,-,3,-,-,-,-,-,-}
{1,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,-}
{1,-,-,4,-,-,-,3,-,-,5,2,-,-,-,-,-,-,-}
{1,-,-,4,5,-,2,3,-,-,-,-,-,-,-,-,-,-,-}
{1,-,-,4,5,-,-,3,-,-,-,2,-,-,-,-,-,-,-}
{1,-,-,-,5,-,2,3,4,-,-,-,-,-,-,-,-,-,-}
{1,-,-,-,5,-,2,-,4,-,-,-,3,-,-,-,-,-,-}
{1,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,-}
{1,-,-,-,5,-,-,3,4,-,-,2,-,-,-,-,-,-,-}
{1,-,-,-,5,-,-,-,4,-,-,2,3,-,-,-,-,-,-}
{1,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,-}
{-,2,-,-,-,1,-,3,4,-,5,-,-,-,-,-,-,-,-}
{-,2,-,-,-,1,-,3,-,-,5,-,-,-,4,-,-,-,-}
{-,2,-,-,-,1,-,-,4,-,-,-,3,-,-,-,-,5,-}
{-,2,-,-,-,1,-,-,4,-,5,-,3,-,-,-,-,-,-}
{-,2,-,-,-,1,-,-,-,-,5,-,3,-,4,-,-,-,-}
{-,2,-,-,-,1,-,-,-,-,5,-,-,-,4,-,3,-,-}
{-,2,3,-,-,1,-,-,4,-,5,-,-,-,-,-,-,-,-}
{-,2,3,-,-,1,-,-,-,-,5,-,-,-,4,-,-,-,-}
{-,2,3,4,-,1,-,-,-,-,5,-,-,-,-,-,-,-,-}
{-,2,3,4,5,1,-,-,-,-,-,-,-,-,-,-,-,-,-}
{-,2,3,-,5,1,-,-,4,-,-,-,-,-,-,-,-,-,-}
{-,2,3,-,5,-,-,-,4,1,-,-,-,-,-,-,-,-,-}
{-,2,-,4,-,1,-,3,-,-,5,-,-,-,-,-,-,-,-}
{-,2,-,4,-,1,-,-,-,-,5,-,3,-,-,-,-,-,-}
{-,2,-,4,-,-,-,3,-,1,5,-,-,-,-,-,-,-,-}
{-,2,-,4,-,-,-,3,-,-,5,-,-,1,-,-,-,-,-}
{-,2,-,4,5,1,-,3,-,-,-,-,-,-,-,-,-,-,-}
{-,2,-,4,5,-,-,3,-,1,-,-,-,-,-,-,-,-,-}
{-,2,-,-,5,1,-,3,4,-,-,-,-,-,-,-,-,-,-}
{-,2,-,-,5,1,-,-,4,-,-,-,3,-,-,-,-,-,-}
{-,2,-,-,5,-,-,3,-,1,-,-,-,-,4,-,-,-,-}
{-,2,-,-,5,-,-,3,4,1,-,-,-,-,-,-,-,-,-}
{-,2,-,-,5,-,-,-,4,1,-,-,3,-,-,-,-,-,-}
{-,2,-,-,5,-,-,-,4,-,-,-,3,1,-,-,-,-,-}
{-,-,3,-,-,1,2,-,4,-,5,-,-,-,-,-,-,-,-}
{-,-,3,-,-,1,2,-,-,-,5,-,-,-,4,-,-,-,-}
{-,-,3,-,-,1,-,-,4,-,-,2,-,-,-,-,-,5,-}
{-,-,3,-,-,1,-,-,4,-,5,2,-,-,-,-,-,-,-}
{-,-,3,-,-,1,-,-,-,-,5,2,-,-,4,-,-,-,-}
{-,-,3,-,-,1,-,-,-,-,5,-,-,-,4,2,-,-,-}
{-,-,3,-,-,-,2,-,-,1,-,-,-,-,4,-,-,5,-}
{-,-,3,-,-,-,2,-,-,1,5,-,-,-,4,-,-,-,-}
{-,-,3,-,-,-,2,-,4,1,5,-,-,-,-,-,-,-,-}
{-,-,3,-,-,-,2,-,4,-,5,-,-,1,-,-,-,-,-}
{-,-,3,-,-,-,2,-,-,-,5,-,-,1,4,-,-,-,-}
{-,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,1}
{-,-,3,4,-,1,2,-,-,-,5,-,-,-,-,-,-,-,-}
{-,-,3,4,-,1,-,-,-,-,5,2,-,-,-,-,-,-,-}
{-,-,3,4,-,-,2,-,-,1,5,-,-,-,-,-,-,-,-}
{-,-,3,4,-,-,2,-,-,-,5,-,-,1,-,-,-,-,-}
{-,-,3,4,5,1,2,-,-,-,-,-,-,-,-,-,-,-,-}
{-,-,3,4,5,-,2,-,-,1,-,-,-,-,-,-,-,-,-}
{-,-,3,-,5,1,2,-,4,-,-,-,-,-,-,-,-,-,-}
{-,-,3,-,5,1,-,-,4,-,-,2,-,-,-,-,-,-,-}
{-,-,3,-,5,-,2,-,-,1,-,-,-,-,4,-,-,-,-}
{-,-,3,-,5,-,2,-,4,1,-,-,-,-,-,-,-,-,-}
{-,-,3,-,5,-,-,-,4,1,-,2,-,-,-,-,-,-,-}
{-,-,3,-,5,-,-,-,4,-,-,2,-,1,-,-,-,-,-}
{-,-,-,4,-,1,2,3,-,-,5,-,-,-,-,-,-,-,-}
{-,-,-,4,-,1,2,-,-,-,5,-,3,-,-,-,-,-,-}
{-,-,-,4,-,1,-,3,-,-,-,2,-,-,-,-,-,5,-}
{-,-,-,4,-,1,-,3,-,-,5,2,-,-,-,-,-,-,-}
{-,-,-,4,-,1,-,-,-,-,5,2,3,-,-,-,-,-,-}
{-,-,-,4,-,1,-,-,-,-,5,-,3,-,-,2,-,-,-}
{-,-,-,4,-,-,2,-,-,1,-,-,3,-,-,-,-,5,-}
{-,-,-,4,-,-,2,-,-,1,5,-,3,-,-,-,-,-,-}
{-,-,-,4,-,-,2,3,-,1,5,-,-,-,-,-,-,-,-}
{-,-,-,4,-,-,2,3,-,-,5,-,-,1,-,-,-,-,-}
{-,-,-,4,-,-,2,-,-,-,5,-,-,1,-,-,3,-,-}
{-,-,-,4,-,-,2,-,-,-,5,-,3,1,-,-,-,-,-}
{-,-,-,4,-,-,-,3,-,1,-,2,-,-,-,-,-,5,-}
{-,-,-,4,-,-,-,3,-,1,5,2,-,-,-,-,-,-,-}
{-,-,-,4,-,-,-,3,-,-,-,2,-,1,-,-,-,5,-}
{-,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,1}
{-,-,-,4,-,-,-,3,-,-,5,-,-,1,-,2,-,-,-}
{-,-,-,4,-,-,-,3,-,-,5,2,-,1,-,-,-,-,-}
{-,-,-,4,5,1,2,3,-,-,-,-,-,-,-,-,-,-,-}
{-,-,-,4,5,1,-,3,-,-,-,2,-,-,-,-,-,-,-}
{-,-,-,4,5,-,2,-,-,1,-,-,3,-,-,-,-,-,-}
{-,-,-,4,5,-,2,3,-,1,-,-,-,-,-,-,-,-,-}
{-,-,-,4,5,-,-,3,-,1,-,2,-,-,-,-,-,-,-}
{-,-,-,4,5,-,-,3,-,-,-,2,-,1,-,-,-,-,-}
{-,-,-,-,5,1,2,3,4,-,-,-,-,-,-,-,-,-,-}
{-,-,-,-,5,1,2,-,4,-,-,-,3,-,-,-,-,-,-}
{-,-,-,-,5,1,-,3,-,-,-,2,-,-,4,-,-,-,-}
{-,-,-,-,5,1,-,3,4,-,-,2,-,-,-,-,-,-,-}
{-,-,-,-,5,1,-,-,4,-,-,2,3,-,-,-,-,-,-}
{-,-,-,-,5,1,-,-,4,-,-,-,3,-,-,2,-,-,-}
{-,-,-,-,5,-,2,-,-,1,-,-,3,-,4,-,-,-,-}
{-,-,-,-,5,-,2,-,-,1,-,-,-,-,4,-,3,-,-}
{-,-,-,-,5,-,2,3,-,1,-,-,-,-,4,-,-,-,-}
{-,-,-,-,5,-,2,3,4,1,-,-,-,-,-,-,-,-,-}
{-,-,-,-,5,-,2,-,4,1,-,-,3,-,-,-,-,-,-}
{-,-,-,-,5,-,2,-,4,-,-,-,3,1,-,-,-,-,-}
{-,-,-,-,5,-,-,3,-,1,-,2,-,-,4,-,-,-,-}
{-,-,-,-,5,-,-,3,-,1,-,-,-,-,4,2,-,-,-}
{-,-,-,-,5,-,-,3,-,-,-,2,-,1,4,-,-,-,-}
{-,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,1}
{-,-,-,-,5,-,-,3,4,1,-,2,-,-,-,-,-,-,-}
{-,-,-,-,5,-,-,3,4,-,-,2,-,1,-,-,-,-,-}
{-,-,-,-,5,-,-,-,4,1,-,2,3,-,-,-,-,-,-}
{-,-,-,-,5,-,-,-,4,1,-,-,3,-,-,2,-,-,-}
{-,-,-,-,5,-,-,-,4,-,-,2,-,1,-,-,3,-,-}
{-,-,-,-,5,-,-,-,4,-,-,2,3,1,-,-,-,-,-}
{-,-,-,-,5,-,-,-,4,-,-,-,3,1,-,2,-,-,-}
{-,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,1}
(End)

Václav Chvátal, David A. Klarner, and Donald E. Knuth, Selected Combinatorial Research Problems, Stanford University Computer Science Department report STAN-CS-72-292, June 1972, page 26, problem 36 due to R. M. Karp.
Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 4-24, section 4; arXiv preprint, arXiv:1810.08252 [math.CO], 2018-2020.
David Galvin, The n-Part Trilogy Problem
D. J. Kleitman and D. J. Kwiatkowski, A Lower Bound On the Length of a Sequence Containing All Permutations as Subsequences, Journal of Combinatorial Theory, series A, volume 21, number 2, September 1976, pages 129-136.
P. J. Koutas and T. C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.
Maarten Löffler and Benjamin Raichel, Preprocessing Disks for Convex Hulls, Revisited, arXiv:2502.03633 [cs.CG], 2025. See p. 28.
Malcolm Newey, Notes on a problem involving permutations as subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973.
Sasa Radomirovic, A Construction of Short Sequences Containing All Permutations of a Set as Subsequences, Electronic Journal of Combinatorics 19(4), 2012, P31.
Oliver Tan, Skip Letters for Short Supersequence of All Permutations, arXiv preprint arXiv:2201.06306 [math.CO], 2022.
Przemysław Uznański, All Permutations Supersequence is coNP-complete, arXiv preprint arXiv:1506.05079 [cs.CC], 2015.

Cf. A136094 (smallest sequences), A351468 (Newey's sequences).
Cf. A049039, A337300 (conjectured values).
Cf. A373728 (circular), A180632 (superpermutations), A348574 (subset substrings).

NextTuple[x_, n_, l_] := Module[{i, x0 = x},
   If[x0 == ConstantArray[n, l], Return[{}]];
   For[i = l, i >= 1, i--,
    If[x0[[i]] < n, x0[[i]]++; Return[x0], x0[[i]] = 1]]];
Join[{1}, Table[p = Permutations[Range[n], {n}];
  For[tl = n + 1, tl <= 50, tl++,
   tup = ConstantArray[1, tl];
   While[tup = NextTuple[tup, n, tl]; tup != {},
    If[Product[Count[tup, i], {i, 1, n}] == 0, Continue[]];
    For[j = 1, j <= Length[p], j++,
     perm = p[[j]]; lst = tup; fnd = True;
     For[k = 1, k <= Length[perm], k++,
      If[lst == {}, fnd = False; Break[]];
      p1 = Position[lst, perm[[k]], 1, 1];
      If[Length[p1] == 0, fnd = False; Break[]];
      p1 = First@First@p1;
      If[! IntegerQ[p1], fnd = False; Break[]];
      lst = Drop[lst, p1];
      ]; If[! fnd, Break[]]]; If[fnd, Break[]]]; If[fnd, Break[]]];
tl, {n, 2, 5}]](* Robert Price, Oct 13 2019 *)

Conjecture: a(n) = Sum_{k=1..n} A049039(k) = A337300(n). - Gerald Hillier, Jun 18 2016 [The conjecture is false for n=8, provided that a(8)=52 is correct. - Pontus von Brömssen, Aug 18 2025]

a(5) = 19 from John W. Layman, Aug 29 2008
a(5)-a(7) are computed by Newey 1973, added by Max Alekseyev, Apr 16 2013
a(8) (using A136094) from Pontus von Brömssen, Aug 18 2025

A093848 (a(n)) is the earliest monotonic sequence starting with a(1)=1 and satisfying a(n)=length of n-th run of consecutive integers with same parity.

Original entry on oeis.org

1, 2, 4, 5, 7, 9, 11, 12, 14, 16, 18, 20, 21, 23, 25, 27, 29, 31, 33, 34, 36, 38, 40, 42, 44, 46, 48, 50, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 122, 124

Offset: 1

Benoit Cloitre, May 21 2004

nonn

There are a(1) odd terms, a(2) even terms, a(3) odd terms, a(4) even terms ... - Benoit Cloitre, May 26 2004

A variation on Golomb's sequence A001462.

			Sequence begins: (1),(2,4),(5,7,9,11),(12,14,16,18,20),(21,.... since the number of elements in each run of odd or even integers is 1, 2, 4, 5, ... the sequence itself.

T. D. Noe, Table of n, a(n) for n=1..1000

Cf. A001462, A049039, A169863.

A093848 := proc(nmax) local n,par,a,alast,j ; n := 3 ; par := 1 ; a := [1,2,4] ; while nops(a) < nmax do alast := op(-1,a); if type(alast,'even') = type(par,'even') then ; else alast := alast -1 ; end if; for j from 1 to op(n,a) do a := [op(a), alast+2*j] ; end do: par := 1-par ; n := n+1 ; end do: a ; end proc: A093848(120) ; # R. J. Mathar, Jun 22 2010

t={1,2,4}; Do[t=Join[t,Table[t[[-1]]+2*i-1, {i,t[[n]]}]], {n,3,40}]

it seems that a(n) = 2n - a*n^b + o(n^b) where a and b are 2 suitable constants. b=0.4.... Does b=2-phi where phi is the golden ratio?

Terms starting at a(52) corrected by R. J. Mathar, Jun 22 2010

A160473 The p(n) sequence that is associated with the Eta triangle A160464.

Original entry on oeis.org

3, 30, 315, 11340, 311850, 12162150, 638512875, 86837751000, 7424627710500, 779585909602500, 98617617564716250, 14792642634707437500, 2596108782391155281250, 527010082825404522093750, 122529844256906551386796875, 64695757767646659132228750000

Offset: 2

Johannes W. Meijer, May 24 2009

A160464 is the Eta triangle.
Equals 3*(n-2)!*A000457(n-2)/A054243(n-1)
Equals 2^(-A049039(n-1))*(2*n-1)!
Cf. The pg(n) sequence A162440. - Johannes W. Meijer, Jul 06 2009

[2^(-(2*(n-1)-1-Floor(Log(n-1)/Log(2))))*Factorial(2*n-1)  : n in [2..30]]; // Vincenzo Librandi, Jul 06 2015

vector(20, n, n++; 2^(-(2*(n-1)-1-floor(log(n-1)/log(2))))*(2*n-1)!) \\ Michel Marcus, Jul 06 2015

a(n) = 2^(-(2*(n-1)-1-floor(log(n-1)/log(2))))*(2*n-1)! for n = 2, 3, 4, ... .

A050487 Geometric Connell sequence: start with 1; then next two numbers == 2 mod 3; next four == 3 mod 3; next eight == 1 mod 3; etc.

Original entry on oeis.org

1, 2, 5, 6, 9, 12, 15, 16, 19, 22, 25, 28, 31, 34, 37, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162

Offset: 1

James Sellers, Dec 26 1999

R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Cf. A049039, A050488.

a(n) = 3*n - 2*(1 + floor(log_2(n))).

More terms from Ralf Stephan, Oct 11 2003

A160465 First left hand column of the Eta triangle A160464.

Original entry on oeis.org

-1, -11, -114, -3963, -104745, -3926745, -198491580, -26045435115, -2153099119815, -219022225836750, -26891482281048000, -3921682257253270125, -670160622793156369875, -132649536458654226136125

Offset: 2

Johannes W. Meijer, May 24 2009

A160464 is the Eta triangle.
The GCS(n) sequence equals the geometric Connell sequence A049039(n).
The p(n) sequence is given by A160473.

nmax:=15; c(2) := -1/3: for n from 3 to nmax do c(n) := (2*n-2)*c(n-1)/(2*n-1)-1/ ((n-1)*(2*n-1)) end do: for n from 2 to nmax do GCS(n-1) := ln(1/(2^(-(2*(n-1)-1-floor(ln(n-1)/ ln(2))))))/ln(2); p(n) := 2^(-GCS(n-1))*(2*n-1)!; ETA(n, 1) := p(n)*c(n) end do: seq(ETA(n, 1), n=2..nmax);

A135260 Fibonacci Connell sequence: 1 odd, 1 even, 2 odd, 3 even, 5 odd, 8 even, ....

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 10, 11, 13, 15, 17, 19, 20, 22, 24, 26, 28, 30, 32, 34, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125

Offset: 1

Jonathan Vos Post, Dec 01 2007

This is to A049039 as Fibonacci numbers A000045 is to A000079 Powers of 2.

Cf. A000045, A005408, A005843, A049039.

F(1) of the odd numbers: a(n) = 2n+1 (A005408), followed by the next F(2) of the even numbers a(n) = 2n (A005843), followed by the next F(3) of the odd numbers, followed by the next F(4) of the even numbers and so forth, where F(n) = A000045(n).

Corrected by Avinoam Kalma, Jun 20 2010

cp's OEIS Frontend

A337300 Partial sums of the geometric Connell sequence A049039.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A160464 The Eta triangle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A062714 Minimal length of a sequence with terms from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A093848 (a(n)) is the earliest monotonic sequence starting with a(1)=1 and satisfying a(n)=length of n-th run of consecutive integers with same parity.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A160473 The p(n) sequence that is associated with the Eta triangle A160464.

Views

Author

Keywords

Crossrefs

Programs

Magma

PARI

Formula

A050487 Geometric Connell sequence: start with 1; then next two numbers == 2 mod 3; next four == 3 mod 3; next eight == 1 mod 3; etc.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A160465 First left hand column of the Eta triangle A160464.

Views

Author

Keywords

Crossrefs

Programs

Maple

A135260 Fibonacci Connell sequence: 1 odd, 1 even, 2 odd, 3 even, 5 odd, 8 even, ....

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions