A112532 -id:A112532 - 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

A229046 G.f.: Sum_{n>=0} n! * x^n * (1+x)^n / Product_{k=1..n} (1 + k*x).

Original entry on oeis.org

1, 1, 2, 4, 10, 28, 88, 304, 1144, 4648, 20248, 94024, 463144, 2409928, 13198888, 75848584, 456066664, 2862257608, 18708144808, 127096142344, 895846801384, 6540722530888, 49392459602728, 385251753351304, 3099780861286504, 25698921466247368, 219294936264513448

Offset: 0

Paul D. Hanna, Oct 27 2013

nonn

a(n-1) is the number of set partitions of [n] such that the absolute difference between least elements of consecutive blocks is always > 1. a(4) = 10: 12345, 1234|5, 1235|4, 123|45, 1245|3, 124|35, 124|3|5, 125|34, 12|345, 12|34|5. - Alois P. Heinz, May 22 2017

Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) = e(k). [Martinez and Savage, 2.13] - Eric M. Schmidt, Jul 17 2017

			G.f.: A(x) = 1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 28*x^5 + 88*x^6 + 304*x^7 +...
where
A(x) = 1 + x*(1+x)/(1+x) + 2!*x^2*(1+x)^2/((1+x)*(1+2*x)) + 3!*x^3*(1+x)^3/((1+x)*(1+2*x)*(1+3*x)) + 4!*x^4*(1+x)^4/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)) + 5!*x^5*(1+x)^5/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)*(1+5*x)) +...
Also, we have the identity (cf. A204064):
A(x) = 1 + x + 2*x^2*(1+x)/(1+x+x^2) + 2*x^3*(1+2*x)*(2+2*x)/((1+x+2*x^2)*(1+2*x+2*x^2)) + 2*x^4*(1+3*x)*(2+3*x)*(3+3*x)/((1+x+3*x^2)*(1+2*x+3*x^2)*(1+3*x+3*x^2)) + 2*x^5*(1+4*x)*(2+4*x)*(3+4*x)*(4+4*x)/((1+x+4*x^2)*(1+2*x+4*x^2)*(1+3*x+4*x^2)*(1+4*x+4*x^2)) +...
Also, by Peter Bala's o.g.f.:
A(x) = 1/((1+x)*(1-x)) + x/((1+x)^2*(1-2*x)) + x^2/((1+x)^3*(1-3*x))+ x^3/((1+x)^4*(1-4*x))+ x^4/((1+x)^5*(1-5*x)) + x^5/((1+x)^6*(1-6*x)) +...

Paul D. Hanna, Table of n, a(n) for n = 0..500
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Cf. A204064, A105795, A112532, A245373, A298668.

a:= n-> add(k!*Stirling2(n-k+1,k+1), k=0..floor(n/2)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 24 2018

a[n_] := Sum[k!*StirlingS2[n-k+1, k+1], {k, 0, n/2}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 25 2018, after Alois P. Heinz *)

a(n)=polcoeff( sum(m=0, n, m!*x^m*(1+x)^m/prod(k=1, m, 1+k*x +x*O(x^n))), n)
for(n=0,30,print1(a(n),", "))

a(n)=polcoeff( 1-x + 2*x*sum(m=0, n, x^m*prod(k=1, m, (k+m*x)/(1+k*x+m*x^2 +x*O(x^n))) ), n)
for(n=0,30,print1(a(n), ", "))

/* After Peter Bala: Sum_{n>=0} x^n/((1+x)^(n+1)*(1 - (n+1)*x)) */
{a(n)=polcoeff( sum(m=0, n, x^m/((1+x)^(m+1)*(1 - (m+1)*x) +x*O(x^n))), n)} \\ Paul D. Hanna, Jul 13 2014
for(n=0,30,print1(a(n), ", "))

a(n)=sum(k=0, floor(n/2), sum(i=0, k, (-1)^i*binomial(k,i)*(k-i+1)^(n-k)))
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jul 13 2014

G.f.: 1+x + Sum_{n>=1} 2*x^(n+1) * Product_{k=1..n} (k + n*x)/(1 + k*x + n*x^2).
From Peter Bala, Jul 09 2014: (Start)
An alternative form of the o.g.f. appears to be the formal series A(x) = 1/(1 + x) * Sum_{n >= 0} 1/(1 - (n+1)*x)*(x/(1 + x))^n (checked up to a(26)). Cf. A105795.
Setting y = x/(1 + x) produces A(y) = (1 - y)^2*( Sum_{n >= 0} y^n/(1 - (n + 2)*y) ) = 1 + y + 3*y^2 + 9*y^3 + ..., the generating function for A112532. (End)
a(n) = 2*A204064(n-1) for n>1.
a(n) = Sum_{k=0..floor(n/2)} Sum_{i=0..k} (-1)^i * binomial(k,i) * (k-i+1)^(n-k). (See Paul Barry's formula in A105795). - Paul D. Hanna, Jul 13 2014
From Alois P. Heinz, Jan 24 2018: (Start)
a(n) = Sum_{k=0..floor(n/2)} k! * Stirling2(n-k+1,k+1).
a(n) = Sum_{k=1..ceiling((n+1)/2)} A298668(n+1,k). (End)

A112531 Triangle read by rows which lists compositions having at least one part equal to 1.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 6, 4, 3, 6, 4, 1, 2, 3, 6, 4, 6, 12, 12, 5, 3, 6, 12, 10, 4, 10, 5, 1, 2, 3, 6, 4, 6, 12, 12, 5, 6, 12, 24, 20, 12, 30, 20, 6, 3, 6, 12, 10, 12, 30, 30, 15, 4, 10, 20, 20, 5, 15, 6, 1

Offset: 1

Alford Arnold, Sep 10 2005

Consider partitions listed in the order given by A241596 and A242628. Omit any partition not containing 1 as a part. Write down the number of compositions (= ordered partitions) corresponding to this partition.
Row sums give A112532; which are the first differences of A047970.
Row lengths give A011782.

			The partitions (see A241596) begin 1 2 11 3 22 21 111 4 33 32 222 31 221 211 1111 ...
After omitting partitions with no part equal to 1, we have
1 11 21 111 31 221 211 1111 ...
which give rise to 1 1 2 1 2 3 3 1 ... compositions.
The resulting triangle of compositions begins:
1;
1;
2, 1;
2, 3, 3, 1;
2, 3, 6, 4, 3, 6, 4, 1;
2, 3, 6, 4, 6, 12, 12, 5, 3, 6, 12, 10, 4, 10, 5, 1;
2, 3, 6, 4, 6, 12, 12, 5, 6, 12, 24, 20, 12, 30, 20, 6, 3, 6, 12, 10, 12, 30, 30, 15, 4, 10, 20, 20, 5, 15, 6, 1;
...

Cf. A000079, A011782, A047970, A089246, A112532, A241596, A242628.

Edited by N. J. A. Sloane, May 19 2014 based on postings to the Sequence Fans Mailing List by Peter Luschny, Jonas Wallgren, Arie Groeneveld, and Franklin T. Adams-Watters.

A242431 Triangle read by rows: T(n, k) = (k + 1)*T(n-1, k) + Sum_{j=k..n-1} T(n-1, j) for k < n, T(n, n) = 1. T(n, k) for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 14, 10, 4, 1, 43, 35, 17, 5, 1, 144, 128, 74, 26, 6, 1, 523, 491, 329, 137, 37, 7, 1, 2048, 1984, 1498, 730, 230, 50, 8, 1, 8597, 8469, 7011, 3939, 1439, 359, 65, 9, 1, 38486, 38230, 33856, 21568, 9068, 2588, 530, 82, 10, 1

Offset: 0

Peter Luschny, May 14 2014

			0|    1;
1|    2,    1;
2|    5,    3,    1;
3|   14,   10,    4,   1;
4|   43,   35,   17,   5,   1;
5|  144,  128,   74,  26,   6,  1;
6|  523,  491,  329, 137,  37,  7, 1;
7| 2048, 1984, 1498, 730, 230, 50, 8, 1;

Peter Luschny, Rows n = 0..50, flattened.
Mathew Englander, Comments on A101494 and A089246, and related sequences

Cf. A003101, A026898, A047969, A047970, A101494, A089246.

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:
seq(print(seq(T(n,k), k=0..n)), n=0..7);

def A242431_rows():
    T = []; n = 0
    while True:
        T.append(1)
        yield T
        for k in (0..n):
            T[k] = (k+1)*T[k] + add(T[j] for j in (k..n))
        n += 1
a = A242431_rows()
for n in range(8): next(a)

T(n, 0) = A047970(n).
Sum_{k=0..n} T(n, k) = A112532(n+1).
From Mathew Englander, Feb 25 2021: (Start)
T(n,k) = 1 + Sum_{i = k+1..n} i*(i+1)^(n-i).
T(n,k) = T(n,k+1) + (k+1)*(k+2)^(n-k-1) for 0 <= k < n.
T(n,k) = T(n,k+1) + (k+2)*(T(n-1,k) - T(n-1,k+1)) for 0 <= k <= n-2.
T(n,k) = Sum_{i = 0..n-k} (k+2)^i*A089246(n-k,i).
Sum_{i = k..n} T(i,k) = Sum_{i = 0..n-k} (n+2-i)^i = Sum_{i = 0..n-k} A101494(n-k,i)*(k+2)^i. (End)

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

A229046 G.f.: Sum_{n>=0} n! * x^n * (1+x)^n / Product_{k=1..n} (1 + k*x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

A112531 Triangle read by rows which lists compositions having at least one part equal to 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A242431 Triangle read by rows: T(n, k) = (k + 1)*T(n-1, k) + Sum_{j=k..n-1} T(n-1, j) for k < n, T(n, n) = 1. T(n, k) for n >= 0 and 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Sage

Formula