Nathaniel Shar - cp's OEIS frontend

A271648 Number of permutations in S_{2*n+3} containing the pattern 2143...(2n)(2n-1).

6, 119, 2279, 18042, 83921, 284428, 782795, 1859374, 3957717, 7738336, 14140143, 24449570, 40377369, 64143092, 98567251, 147171158, 214284445, 305160264, 426098167, 584574666, 789381473, 1050771420

Offset: 0

Nathaniel Shar, Apr 11 2016

This sequence is eventually polynomial.

N. Shar, Experimental methods in permutation patterns and bijective proof, PhD thesis, Rutgers University (2016)

Cf. A217193.

For n >= 2, a(n) = (32/3)*n^6 + 32*n^5 + (80/3)*n^4 + (16/3)*n^3 + 38/3*n^2 + 59/3*n + 13 (conjectured).
Conjectures from Colin Barker, Apr 11 2016: (Start)
a(n) = 7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)-7*a(n-6)+a(n-7) for n>6.
G.f.: (6+77*x+1572*x^2+4378*x^3+1531*x^4+137*x^5-22*x^6+x^8) / (1-x)^7.
(End)
Remark by Nathaniel Shar, Apr 13 2016: The preceding three conjectures are equivalent (provided appropriate initial conditions are specified for the recurrence relation).

A268755 Variant of A181391: For n >= 1, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = #{a(m), a(m+1), ..., a(n)}; otherwise, a(n+1) = 0. Start with a(1) = 0.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 2, 2, 1, 3, 0, 4, 0, 2, 5, 0, 3, 5, 3, 2, 4, 5, 4, 2, 3, 4, 3, 2, 3, 2, 2, 1, 6, 0, 7, 0, 2, 5, 8, 0, 4, 9, 0, 3, 10, 0, 3, 3, 1, 11, 0, 4, 7, 11, 4, 3, 6, 12, 0, 7, 7, 1, 8, 11, 9, 11, 2, 13, 0, 8, 6, 10, 13, 5, 14, 0, 7, 12, 13, 6, 8, 9, 12

Offset: 1

Nathaniel Shar, Feb 12 2016

From László Kozma, Aug 04 2016: (Start)
Observe that a value k can appear in the sequence only after 0,...,k-1 have already appeared.
Observe that if the sequence were started not from 0 but from some initial sequence, then a cycle could be reached. E.g., ...,1,1,1,1,... or ...,1,2,3,3,1,3,2,3,2,2,1,3,3,...
It can be shown that if we start from 0, we never reach a cycle.
Theorem: this sequence contains every positive integer. (Alternatively: there are infinitely many zeros.)
Proof: suppose otherwise, that the sequence contains only elements up to k. Then there is a last occurrence of 0 in the sequence; let i be its index.
Suppose that after i, all elements of {1,...,k} appear in the sequence. Let x be the element of {1,...,k} with the latest "first appearance" after index i. Since the previous appearance of x is before i, between the two appearances of x we have all elements of {0,1,...,k}, therefore, after x we have "k+1,0", a contradiction.
Thus some element of {1,...,k} does not appear after index i. We argue that k cannot appear more than k times after index i. Otherwise, by the pigeonhole principle, there would be two appearances of k after the same element, say y. Thus: 0,...,y,k,...,y,k. But this is a contradiction, since between the two appearances of y there are at most k-1 distinct values (since 0 and x do not appear). Thus there is a last appearance of k after index i; let us denote its index by i' (i'>i). Thus after i' only elements of {1,...,k-1} appear in the sequence. Repeating the same argument k-2 times, we reach an index i'' after which only element 1 can appear in the sequence. Let j be the smallest index such that from j onwards the sequence contains only 1s. Then the entries at index j-2 and j-1 are "a,a" for some a != 1. But this is a contradiction, since after "a,a,1" not 1 should follow, but some larger value. QED
A275668 gives the first-occurrence-sequence (or, alternatively, the occurrences of zeros, minus 1).
I suggest the name "working set sequence" due to the similarity to concept of "working set" in data structures, e.g. binary search trees. Working set = set of distinct elements queried since last occurrence of current query key in query sequence (i.e., exactly the set whose cardinality we look for here). (End)
Conjecture: every pair of nonnegative integers (x,y) other than (1,1) appear as consecutive entries (a(i) = x, a(i+1) = y, for some i). - László Kozma, Aug 09 2016

			Example: a(10) = 3. This is because a(9) = 1; the previous occurrence of that number, 1, is at index 3; and in between a(3) and a(9) three distinct numbers occur in the sequence.

Nathaniel Shar, Table of n, a(n) for n = 1..100000

Cf. A181391. First-occurrence sequence: A275668.

A248900 Number of permutations of [n] avoiding patterns 2431 and 54321.

Original entry on oeis.org

1, 1, 2, 6, 23, 102, 492, 2492, 13003, 69172, 372963, 2031174, 11148948, 61588814, 342068774, 1908740089, 10694374242, 60137305751, 339276548456, 1919787554118, 10892575241125, 61957028188350, 353224194632459, 2018076850631391, 11552829351121139, 66259093178740462

Offset: 0

Nathaniel Shar, Mar 06 2015

nonn

			a(4) = 23 because all permutations of length 4 except 2431 lie in this set.

Nathaniel Shar, Table of n, a(n) for n = 0..80
Nathaniel Shar, Maple code

Cf. A022558, A047889.

A247472 Number of permutations of length n avoiding the patterns 14253 and 13524.

Original entry on oeis.org

1, 1, 2, 6, 24, 118, 672, 4255, 29146, 212028, 1617344, 12819065, 104870276, 881047470, 7571873230, 66363349857

Offset: 0

Nathaniel Shar, Nov 30 2014

Cf. A164870.

a(10)-a(15) from Lars Blomberg, Apr 26 2018

A248737 a(0) = 0; a(n) = smallest k such that gcd(a(n-k), n) is not 1.

Original entry on oeis.org

0, 1, 2, 3, 2, 5, 2, 7, 2, 6, 1, 11, 3, 13, 5, 1, 7, 17, 6, 19, 2, 3, 2, 23, 2, 11, 2, 6, 1, 29, 3, 31, 5, 3, 7, 1, 3, 37, 11, 3, 8, 41, 2, 43, 2, 6, 1, 47, 3, 15, 1, 2, 1, 53, 3, 6, 1, 2, 1, 59, 3, 61, 5, 3, 7, 3, 1, 67, 11, 4, 1, 71, 3, 73, 5, 1, 7, 1, 6, 79

Offset: 0

Nathaniel Shar, Oct 13 2014

nonn

If p is prime, a(p) = p.

A257173(n) = smallest number m such that a(m) = n. - Reinhard Zumkeller, Apr 17 2015

			a(9) = 6 because a(8) = 2, a(7) = 7, a(6) = 2, a(5) = 5, a(4) = 2 are all relatively prime to 9, but a(3) = 3 is not.

Nathaniel Shar, Table of n, a(n) for n = 0..10000

Cf. A257173.

import Data.List (findIndex); import Data.Maybe (fromMaybe)
a248737 n = a248737_list !! n
a248737_list = 0 : f 1 [0] where
   f x ys = y : f (x + 1) (y : ys) where
     y = (+ 1) $ fromMaybe (x - 1) $ findIndex (\z -> gcd z x /= 1) ys
-- Reinhard Zumkeller, Apr 17 2015

findk(va, n) = {k = 1; while (gcd(va[n-k], n) == 1, k++; if (k==n, break)); k;}
lista(nn) = {va = vector(nn); va[1] = 1; print1(0, ", ", va[1], ", "); for (n=2, nn, va[n] = findk(va, n); print1(va[n], ", "););} \\ Michel Marcus, Oct 17 2014

A248756 a(n) = smallest k such that a(n-k) and n have the same number of 1's in their binary expansions, or a(n) = n if no such k exists.

Original entry on oeis.org

1, 1, 3, 2, 2, 3, 7, 3, 1, 2, 4, 4, 6, 7, 15, 4, 4, 5, 5, 1, 7, 1, 8, 5, 4, 5, 12, 7, 14, 15, 31, 7, 6, 1, 3, 1, 5, 6, 9, 1, 9, 10, 13, 1, 15, 1, 16, 6, 6, 7, 6, 2, 8, 9, 24, 6, 12, 13, 28, 15, 30, 31, 63, 11, 8, 9, 3, 1, 5, 6, 10, 1, 9, 10, 14, 1, 16, 17, 17

Offset: 1

Nathaniel Shar, Oct 13 2014

a(n) = n if and only if n is one less than a power of 2.

A257078(n) = smallest number m such that a(m) = n. - Reinhard Zumkeller, Apr 16 2015

			a(12) = 4. 12 has two 1's in its binary expansion. The previous entry in the sequence that has two 1's in its binary expansion is 3, which is a(8), so a(12) = 12-8 = 4.

Nathaniel Shar, Table of n, a(n) for n = 1..8192

Cf. A000120, A007088.

Cf. A257078.

a248756 n = a248756_list !! (n-1)
a248756_list = f 1 [] where
   f x yvs = fst yw : f (x + 1) (yw:yvs) where
     yw = g 1 yvs
     g _ []          = (x, h)
     g k ((z,w):zws) = if w == h then (k, a000120 k) else g (k + 1) zws
     h = a000120 x
-- Reinhard Zumkeller, Apr 16 2015

findk(va, n) = {hw = hammingweight(n); for (k=1, n-1, if (hammingweight(va[n-k]) == hw, return (k)););return (0);}
lista(nn) = {va = vector(nn); for (n=1, nn, k = findk(va, n); if (k==0, va[n] = n, va[n] = k); print1(va[n], ", "););} \\ Michel Marcus, Oct 15 2014

my (@a, @mem);
$a[0] = 0;
sub listseq {
  my $n = shift;
  for (1..$n) {
    my $s = digitsum($_);
    my $last = $mem[$s]||0;
    $a[$] = $-$last;
    $mem[digitsum($-$last)] = $;
  }
  print "$ $a[$]\n" for 1..$n;
}
sub digitsum {
  my $n = shift;
  my $k = 0;
  do {$k += ($n&1)} while $n >>= 1;
  return $k;
} # Nathaniel Shar, Oct 15 2014

A248426 Number of permutations of length n avoiding the pattern 1342 and with 1 appearing before n.

Original entry on oeis.org

1, 3, 11, 46, 211, 1038, 5400, 29425, 166767, 977637, 5901299, 36538483, 231286924, 1492482109, 9793849702, 65217085321, 439887071563, 3000650380603, 20673092451143, 143687057466690, 1006538694994567, 7100409431126274, 50404258628152846, 359845398688215262

Offset: 2

Nathaniel Shar, Oct 06 2014

nonn

			For n=4 the 11 permutations are: 1234, 1243, 1324, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214.

Cf. A022558.

G.f.: (-1 + sqrt((8*x-1)*sqrt(1-8*x) - 136*x^2 + 20*x + 1)/sqrt((8*x-1)*sqrt(1-8*x) - 8*x^2 + 20*x + 1))*((8*x-1)*sqrt(1-8*x) - 8*x^2 - 12*x + 1)/(64*x).

cp's OEIS Frontend

User: Nathaniel Shar

A271648 Number of permutations in S_{2*n+3} containing the pattern 2143...(2n)(2n-1).

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A268755 Variant of A181391: For n >= 1, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = #{a(m), a(m+1), ..., a(n)}; otherwise, a(n+1) = 0. Start with a(1) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A248900 Number of permutations of [n] avoiding patterns 2431 and 54321.

Views

Author

Keywords

Examples

Links

Crossrefs

A247472 Number of permutations of length n avoiding the patterns 14253 and 13524.

Views

Author

Keywords

Crossrefs

Extensions

A248737 a(0) = 0; a(n) = smallest k such that gcd(a(n-k), n) is not 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

A248756 a(n) = smallest k such that a(n-k) and n have the same number of 1's in their binary expansions, or a(n) = n if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Perl

A248426 Number of permutations of length n avoiding the pattern 1342 and with 1 appearing before n.

Views

Author

Keywords

Examples

Crossrefs

Formula