A112531 -id:A112531 - cp's OEIS frontend

A047970 Antidiagonal sums of nexus numbers (A047969).

1, 2, 5, 14, 43, 144, 523, 2048, 8597, 38486, 182905, 919146, 4866871, 27068420, 157693007, 959873708, 6091057009, 40213034874, 275699950381, 1959625294310, 14418124498211, 109655727901592, 860946822538675, 6969830450679864, 58114638923638573

Offset: 0

Alford Arnold, Dec 11 1999

nonn

From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.
Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.
A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.
For example, if q=5{bar 1}32{bar 4}, then q1=532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a. (End)
Number of ordered factorizations over the Gaussian polynomials.
Apparently, also the number of permutations in S_n avoiding {bar 3}{bar 1}542 (i.e., every occurrence of 542 is contained in an occurrence of a 31542). - Lara Pudwell, Apr 25 2008
With offset 1, apparently the number of sequences {b(m)} of length n of positive integers with b(1) = 1 and, for all m > 1, b(m) <= max{b(m-1) + 1, max{b(i) | 1 <= i <= m - 1}}. This sequence begins 1, 2, 5, 14, 43, 144, 523, 2048, 8597, 38486. The term 144 counts the length 6 sequence 1, 2, 3, 1, 1, 3, for instance. Contrast with the families of sequences discussed in Franklin T. Adams-Watters's comment in A005425. - Rick L. Shepherd, Jan 01 2015
a(n-1) for n >= 1 is the number of length-n restricted growth strings (RGS) [s(0), s(1), ..., s(n-1)] with s(0)=0 and s(k) <= the number of fixed points in the prefix, see example. - Joerg Arndt, Mar 08 2015
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) = e(k). [Martinez and Savage, 2.15] - Eric M. Schmidt, Jul 17 2017
a(n) counts all positive-integer m-tuples whose maximum is n-m+2. - Mathew Englander, Feb 28 2021
a(n) counts the cyclic permutations of [n+2] that avoid the vincular pattern 12-3-4, i.e., the pattern 1234 where the 1 and 2 are required to be adjacent. - Rupert Li, Jul 27 2021

			a(3) = 1 + 5 + 7 + 1 = 14.
From _Paul D. Hanna_, Jul 22 2014:  (Start)
G.f. A(x) = 1 + 2*x + 5*x^2 + 14*x^3 + 43*x^4 + 144*x^5 + 523*x^6 + 2048*x^7 + ...
where we have the series identity:
A(x) = (1-x)*( 1/(1-2*x) + x/(1-3*x) + x^2/(1-4*x) + x^3/(1-5*x) + x^4/(1-6*x) + x^5/(1-7*x) + x^6/(1-8*x) + ...)
is equal to
A(x) = 1/(1-x) + x/((1-x)*(1-2*x)) + x^2/((1-2*x)*(1-3*x)) + x^3/((1-3*x)*(1-4*x)) + x^4/((1-4*x)*(1-5*x)) + x^5/((1-5*x)*(1-6*x)) + x^6/((1-6*x)*(1-7*x)) + ...
and also equals
A(x) = 1/((1-x)*(1+x)) + 2!*x/((1-x)^2*(1+x)*(1+2*x)) + 3!*x^2/((1-x)^3*(1+x)*(1+2*x)*(1+3*x)) + 4!*x^3/((1-x)^4*(1+x)*(1+2*x)*(1+3*x)*(1+4*x)) + ...
(End)
From _Joerg Arndt_, Mar 08 2015: (Start)
There are a(4-1)=14 length-4 RGS as in the comment (dots denote zeros):
01:  [ . . . . ]
02:  [ . . . 1 ]
03:  [ . . 1 . ]
04:  [ . . 1 1 ]
05:  [ . 1 . . ]
06:  [ . 1 . 1 ]
07:  [ . 1 . 2 ]
08:  [ . 1 1 . ]
09:  [ . 1 1 1 ]
10:  [ . 1 1 2 ]
11:  [ . 1 2 . ]
12:  [ . 1 2 1 ]
13:  [ . 1 2 2 ]
14:  [ . 1 2 3 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..300
G. E. Andrews, The Theory of Partitions, 1976, page 242 table of Gaussian polynomials.
David Callan, The number of bar(31)542-avoiding permutations, arXiv:1111.3088 [math.CO], 2011.
Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021.
Zhicong Lin and Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
Lara Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.
Eric Weisstein's World of Mathematics, Nexus Number
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

Antidiagonal sums of A085388 (beginning with the second antidiagonal) and A047969.
Partial sums are in A026898, A003101. First differences A112532.
Cf. A112531, A089246, A242431, A101494.

T := proc(n, k) option remember; local j;
    if k=n then 1
  elif k>n then 0
  else (k+1)*T(n-1, k) + add(T(n-1, j), j=k..n)
    fi end:
A047970 := n -> T(n,0);
seq(A047970(n), n=0..24); # Peter Luschny, May 14 2014

a[ n_] := SeriesCoefficient[ ((1 - x) Sum[ x^k / (1 - (k + 2) x), {k, 0, n}]), {x, 0, n}]; (* Michael Somos, Jul 09 2014 *)

/* From o.g.f. (Paul D. Hanna, Jul 20 2014) */
{a(n)=polcoeff( sum(m=0, n, (m+1)!*x^m/(1-x)^(m+1)/prod(k=1, m+1, 1+k*x +x*O(x^n))), n)}
for(n=0, 25, print1(a(n), ", "))

/* From o.g.f. (Paul D. Hanna, Jul 22 2014) */
{a(n)=polcoeff( sum(m=0, n, x^m/((1-m*x)*(1-(m+1)*x +x*O(x^n)))), n)}
for(n=0, 25, print1(a(n), ", "))

def A074664():
    T = []; n = 0
    while True:
        T.append(1)
        yield T[0]
        for k in (0..n):
            T[k] = (k+1)*T[k] + add(T[j] for j in (k..n))
        n += 1
a = A074664()
[next(a) for n in range(25)] # Peter Luschny, May 13 2014

Formal o.g.f.: (1 - x)*( Sum_{n >= 0} x^n/(1 - (n + 2)*x) ). - Peter Bala, Jul 09 2014
O.g.f.: Sum_{n>=0} (n+1)! * x^n/(1-x)^(n+1) / Product_{k=1..n+1} (1 + k*x). - Paul D. Hanna, Jul 20 2014
O.g.f.: Sum_{n>=0} x^n / ( (1 - n*x) * (1 - (n+1)*x) ). - Paul D. Hanna, Jul 22 2014
From Mathew Englander, Feb 28 2021: (Start)
a(n) = A089246(n+2,0) = A242431(n,0).
a(n) = Sum_{m = 1..n+1} Sum_{i = 0..m-1} binomial(m,i) * (n-m+1)^i.
a(n) = 1 + Sum_{i = 0..n} i * (i+1)^(n-i). (End)
a(n) ~ sqrt(2*Pi*n / (w*(1+w))) * (1 + n/w)^(1 + n - n/w), where w = LambertW(exp(1)*n). - Vaclav Kotesovec, Jun 10 2025

A242628 Irregular table enumerating partitions; n-th row has partitions in previous row with each part incremented, followed by partitions in previous row with an additional part of size 1.

Original entry on oeis.org

1, 2, 1, 1, 3, 2, 2, 2, 1, 1, 1, 1, 4, 3, 3, 3, 2, 2, 2, 2, 3, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 5, 4, 4, 4, 3, 3, 3, 3, 4, 2, 3, 3, 2, 3, 2, 2, 2, 2, 2, 2, 4, 1, 3, 3, 1, 3, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 6, 5, 5, 5, 4, 4, 4, 4, 5, 3, 4, 4, 3, 4, 3, 3, 3, 3, 3, 3, 5, 2

Offset: 1

Franklin T. Adams-Watters, May 19 2014

This can be calculated using the binary expansion of n; see the PARI program.
The n-th row consists of all partitions with hook size (maximum + number of parts - 1) equal to n.
The partitions in row n of this sequence are the conjugates of the partitions in row n of A125106 taken in reverse order.
Row n is also the reversed partial sums plus one of the n-th composition in standard order (A066099) minus one. - Gus Wiseman, Nov 07 2022

			The table starts:
  1;
  2; 1,1;
  3; 2,2; 2,1; 1,1,1;
  4; 3,3; 3,2; 2,2,2; 3,1 2,2,1 2,1,1 1,1,1,1;
  ...

Alois P. Heinz, Rows n = 1..12, flattened
Gus Wiseman, Statistics, classes, and transformations of standard compositions

Cf. A241596 (another version of this list of partitions), A125106, A240837, A112531, A241597 (compositions).
For other schemes to list integer partitions, please see for example A227739, A112798, A241918, A114994.
First element in each row is A008687.
Last element in each row is A065120.
Heinz numbers of rows are A253565.
Another version is A358134.
Cf. A000120, A029837, A029931, A030303, A066099, A070939, A253566, A355536, A358135, A358136.

b:= proc(n) option remember; `if`(n=1, [[1]],
      [map(x-> map(y-> y+1, x), b(n-1))[],
       map(x-> [x[], 1], b(n-1))[]])
    end:
T:= n-> map(x-> x[], b(n))[]:
seq(T(n), n=1..7);  # Alois P. Heinz, Sep 25 2015

T[1] = {{1}};
T[n_] := T[n] = Join[T[n-1]+1, Append[#, 1]& /@ T[n-1]];
Array[T, 7] // Flatten (* Jean-François Alcover, Jan 25 2021 *)

apart(n) = local(r=[1]); while(n>1,if(n%2==0,for(k=1,#r,r[k]++),r=concat(r,[1]));n\=2);r \\ Generates n-th partition.

A112532 First differences of [0, A047970].

Original entry on oeis.org

1, 1, 3, 9, 29, 101, 379, 1525, 6549, 29889, 144419, 736241, 3947725, 22201549, 130624587, 802180701, 5131183301, 34121977865, 235486915507, 1683925343929, 12458499203901, 95237603403381, 751291094637083, 6108883628141189, 51144808472958709, 440444879385258001

Offset: 0

Alford Arnold, Sep 10 2005

nonn

Number of sequences of length n in [n] (endofunctions) whose first run has length equal to the maximum of the sequence.

			The 9 sequences for n=4 (sorted by maximum)
1121,1122,2211,2212, 1113,2223,3331,3332, 4444
The 29 sequences for n=5 (sorted by maximum)
11211,11212,11221,11222, 22111,22112,22121,22122, 11123,11131,11132,11133, 22213,22231,22232,22233, 33311,33312,33313,33321,33322,33323, 11114, 22224, 33334, 44441,44442,44443, 55555

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

Cf. A047970, A112531, A229046.

First differences of column 0 of triangle A089246 (beginning at row 1). With offset 1, first differences of column 0 of triangle A242431. Second differences of column 0 of triangle A101494.

a[n_]:= If[n==0, 1, n + Sum[(i-1)^2*i^(n-i), {i,0,n}]];
Table[a[n], {n, 0, 30}] (* G. C. Greubel, Jan 12 2022 *)

a(n) = n + sum(i = 0, n, (n-i-1)^2 * (n-i)^i); \\ Michel Marcus, Mar 01 2021

[n +sum((j-1)^2*j^(n-j) for j in (0..n)) for n in (0..30)] # G. C. Greubel, Jan 12 2022

G.f.: (1-x)^2*( Sum_{n >= 0} x^n/(1 - (n+2)*x) ). - Peter Bala, Jul 09 2014
From Mathew Englander, Feb 28 2021: (Start)
a(n) = A089246(n+2,0) - A089246(n+1,0).
a(n) = n + Sum_{i = 0..n} (n-i-1)^2 * (n-i)^i. (End)

Corrected by D. S. McNeil, Aug 20 2010

Combinatorial interpretation and examples by Olivier Gérard, Jan 29 2023

A241596 Partitions listed by alternately incrementing each part and appending a 1.

Original entry on oeis.org

1, 2, 11, 3, 22, 21, 111, 4, 33, 32, 222, 31, 221, 211, 1111, 5, 44, 43, 333, 42, 332, 322, 2222, 41, 331, 321, 2221, 311, 2211, 2111, 11111, 6, 55, 54, 444, 53, 443, 433, 3333, 52, 442, 432, 3332, 422, 3322, 3222, 22222, 51, 441, 431, 3331, 421, 3321, 3221, 22221, 411, 3311, 3211, 22211, 3111, 22111, 21111, 111111

Offset: 1

N. J. A. Sloane, May 19 2014

Start with S_0 = {1}.
Thereafter, S_{n+1} consists of the partitions in S_n with all parts incremented by 1, together with all partitions in S_n with an additional part of 1.
From Franklin T. Adams-Watters, May 19 2014:
a(n) can be defined in terms of the binary expansion of n. Start with the partition [1]. Now process the bits of n from right to left, excluding the leading 1. For a zero bit, increase each number in the partition by 1; for a one bit, add a part of size 1. For example, for n=11, binary 1011, we get 1 -> 11 -> 111 -> 222 = a(11).
Row n consists of all partitions with hook size (maximum part + number of parts - 1) equal to n.
This sequence will eventually fail because digits greater than 9 are needed.

			The partitions appear in the following order:
S_0 = 1,
S_1 = 2, 11,
S_2 = 3, 22, 21, 111,
S_3 = 4, 33, 32, 222, 31, 221, 211, 1111,
S_4 = 5, 44, 43, 333, 42, 332, 322, 2222, 41, 331, 321, 2221, 311, 2211, 2111, 11111,
...

Arie Groeneveld, Posting to Sequence Fans List, May 19 2014

Alois P. Heinz, Rows n = 1..9, flattened

See A242628 for another version of this list of partitions.

Cf. A125106, A240837, A112531, A241597 (compositions).

b:= proc(n) option remember; `if`(n=1, [[1]],
      [map(x-> map(y-> y+1, x), b(n-1))[],
       map(x-> [x[], 1], b(n-1))[]])
    end:
T:= n-> map(x-> parse(cat(x[])), b(n))[]:
seq(T(n), n=1..6);

Typos corrected by Alois P. Heinz, Sep 25 2015

cp's OEIS Frontend

A047970 Antidiagonal sums of nexus numbers (A047969).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A242628 Irregular table enumerating partitions; n-th row has partitions in previous row with each part incremented, followed by partitions in previous row with an additional part of size 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A112532 First differences of [0, A047970].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A241596 Partitions listed by alternately incrementing each part and appending a 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Extensions