A002662 -id:A002662 - cp's OEIS frontend

A356116 Triangle read by row. The reduced triangle of the partition_triangle A355776.

0, 0, 0, 0, 1, 0, 0, 5, 5, 0, 0, 16, 46, 16, 0, 0, 42, 252, 252, 42, 0, 0, 99, 1086, 2241, 1086, 99, 0, 0, 219, 4097, 15129, 15129, 4097, 219, 0, 0, 466, 14272, 87058, 154426, 87058, 14272, 466, 0, 0, 968, 47300, 452672, 1305062, 1305062, 452672, 47300, 968, 0

Offset: 1

Peter Luschny, Jul 28 2022

By a partition triangle, we understand an irregular triangle where each row corresponds to a mapping of Partitions(n) -> ZZ. We assume a fixed order of the partitions given. Here we will use the ordering defined in A080577. Examples are A355776, A355777, and A134264. 'Reducing' then means summing the values corresponding to the partitions of n with length k. The 'reduced partition triangle' then is a regular triangle with T(n, k) with 1 <= k <= n.

Conversely, A355776, the statistic of permutations whose Lehmer code is nonmonotonic, can be seen as a refinement of this triangle, which in turn is a refinement of the sequence A056986, the number of permutations on [n] containing any given pattern alpha in the symmetric group S_3.

			Triangle T(n, k) starts:
[1] [0]
[2] [0,   0]
[3] [0,   1,     0]
[4] [0,   5,     5,      0]
[5] [0,  16,    46,     16,       0]
[6] [0,  42,   252,    252,      42,       0]
[7] [0,  99,  1086,   2241,    1086,      99,      0]
[8] [0, 219,  4097,  15129,   15129,    4097,    219,     0]
[9] [0, 466, 14272,  87058,  154426,   87058,  14272,   466,   0]
[10][0, 968, 47300, 452672, 1305062, 1305062, 452672, 47300, 968, 0]
.
Row 6 of the partition triangle A355776 is:
[0, [10, 20, 12], [61,  162, 29], [102, 150], 42, 0]
Adding the bracketed terms reduces this row to row 6 of the above triangle.

FindStat - Combinatorial Statistic Finder, The number of occurrences of the pattern [1,2,3] inside a permutation of length at least 3.
Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

A002662 (column 1), A056986 (row sums), A355776 (refinement).

from functools import cache
@cache
def Pn(n: int, k: int) -> int:
    if k == 0: return 0
    if n == 0 or k == 1: return 1
    return Pn(n, k - 1) + Pn(n - k, k) if k <= n else Pn(n, k - 1)
def reduce_parts(fun, n: int) -> list[int]:
    funn: list[int] = fun(n)
    return [sum(funn[Pn(n, k):Pn(n, k + 1)]) for k in range(n)]
def reduce_partition_triangle(fun, n: int) -> list[list[int]]:
    return [reduce_parts(fun, k) for k in range(1, n)]
reduce_partition_triangle(A355776_row, 6)

A104713 Triangle T(n,k) = binomial(n,k), read by rows, 3 <= k <=n .

Original entry on oeis.org

1, 4, 1, 10, 5, 1, 20, 15, 6, 1, 35, 35, 21, 7, 1, 56, 70, 56, 28, 8, 1, 84, 126, 126, 84, 36, 9, 1, 120, 210, 252, 210, 120, 45, 10, 1, 165, 330, 462, 462, 330, 165, 55, 11, 1, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1, 286, 715, 1287, 1716

Offset: 3

Gary W. Adamson, Mar 19 2005

			First few rows of the triangle are:
1;
4, 1;
10, 5, 1;
20, 15, 6, 1;
35, 35, 21, 7, 1;
56, 70, 56, 28, 8, 1;
...

Cf. A007318, A104712, A002662 (row sums).

A104713 := proc(n,k)
        binomial(n,k) ;
end proc;
seq(seq( A104713(n,k),k=3..n),n=3..16) ; # R. J. Mathar, Oct 29 2011

T(n,k) = A007318(n,k) for n>=3, 3<=k<=n.
From Peter Bala, Jul 16 2013: (Start)
The following remarks assume an offset of 0.
Riordan array (1/(1 - x)^4, x/(1 - x)).
O.g.f.: 1/(1 - t)^3*1/(1 - (1 + x)*t) = 1 + (4 + x)*t + (10 + 5*x + x^2)*t^2 + ....
E.g.f.: (1/x*d/dt)^3 (exp(t)*(exp(x*t) - 1 - x*t - (x*t)^2/2!)) = 1 + (4 + x)*t + (10 + 5*x + x^2)*t^2/2! + ....
The infinitesimal generator for this triangle has the sequence [4,5,6,...] on the main subdiagonal and 0's elsewhere. (End)

A355776 Partition triangle read by rows. A statistic of permutations whose Lehmer code is nonmonotonic, refining triangle A356116.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 3, 2, 5, 0, 0, 6, 10, 22, 24, 16, 0, 0, 10, 20, 12, 61, 162, 29, 102, 150, 42, 0, 0, 15, 35, 49, 135, 432, 246, 273, 391, 1389, 461, 388, 698, 99, 0, 0, 21, 56, 90, 52, 260, 982, 1288, 740, 827, 1150, 4974, 2745, 5778, 482, 2057, 8924, 4148, 1333, 2764, 219, 0

Offset: 0

Peter Luschny, Jul 27 2022

We say a list L is weakly increasing if x <= y, and weakly decreasing, if x >= y, for all x, y in L if index(x) < index(y). We say a list L is nonmonotonic if it is not weakly increasing and not weakly decreasing.

The ordering of the partitions is defined in A334439. See the comments in A356116 for the definition of the terms 'partition triangle' and 'reduced partition triangle'.

			Table T(n, k) starts:
[0]  0;
[1]  0;
[2]  0,  0;
[3]  0,  1,  0;
[4]  0, [3,  2],   5,  0;
[5]  0, [6, 10], [22, 24],   16,  0;
[6]  0, [10, 20, 12], [61,  162, 29], [102, 150],   42,   0;
[7]  0, [15, 35, 49], [135, 432, 246, 273], [391, 1389, 461], [388, 698], 99, 0;
Summing the bracketed terms reduces the triangle to A356116.
.
The permutations whose Lehmer code is nonmonotonic, in the case n = 4, k = 1 are: 1243, 1324, 1423, which map to the partition [3, 1] and 1342, 2143, which map to the partition [2, 2]. Thus A356116(4, 1) = 3 + 2 = 5.
.
The cardinality of the preimage of the partitions, i.e. the number of permutations whose Lehmer code is nonmonotonic, are the terms of the sequence. Here row 6:
[6] => 0
[5, 1] => 10
[4, 2] => 20
[3, 3] => 12
[4, 1, 1] => 61
[3, 2, 1] => 162
[2, 2, 2] => 29
[3, 1, 1, 1] => 102
[2, 2, 1, 1] => 150
[2, 1, 1, 1, 1] => 42
[1, 1, 1, 1, 1, 1] => 0

Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

Cf. A000217 (column 1), A002662 (subdiagonal), A000041 (row lengths), A056986 (row sums), A356116 (reduced triangle), A355777 (Euler-Lehmer).

import collections
def perm_lehmer_nonmono_stats(n):
    res = collections.defaultdict(int)
    for p in Permutations(n):
        l = p.to_lehmer_code()
        if all(x >= y for x, y in zip(l, l[1:])): continue
        c = [l.count(i) for i in range(len(p)) if i in l]
        res[Partition(reversed(sorted(c)))] += 1
    return sorted(res.items(), key=lambda x: len(x[0]))
@cached_function
def A355776_row(n):
    if n < 2: return [0]
    S = perm_lehmer_nonmono_stats(n)
    return [0] + [s[1] for s in S] + [0]
def A355776(n, k): return A355776_row(n)[k] if n > 0 else 0
for n in range(0, 8): print(A355776_row(n))

A368534 a(n) = Sum_{k=1..n} binomial(k+1,2) * n^(n-k).

Original entry on oeis.org

0, 1, 5, 24, 146, 1215, 13431, 186816, 3130436, 61291125, 1371742105, 34522712136, 964626945558, 29621465864627, 991330604373851, 35906022352657920, 1399219698628043016, 58367293868445147657, 2594796705962971336125, 122463905297217627859000

Offset: 0

Seiichi Manyama, Dec 29 2023

Cf. A062805, A368535.
Cf. A002662, A052150, A052161.
Cf. A023037, A062806, A068475.

Table[Sum[Binomial[k+1,2]n^(n-k),{k,n}],{n,0,20}] (* Harvey P. Dale, May 14 2025 *)

a(n) = sum(k=1, n, binomial(k+1, 2)*n^(n-k));

a(n) = [x^n] x/((1-n*x) * (1-x)^3).

a(n) = n * (2*n^(n+1) - n^3 - n^2 + n - 1)/(2 * (n-1)^3) for n > 1.

A159881 Triangle read by rows : T(n,0) = n+1, T(n,k)=0 if k<0 or if k>n, T(n,k) = k*T(n-1,k) - T(n-1,k-1).

Original entry on oeis.org

1, 2, -1, 3, -3, 1, 4, -6, 5, -1, 5, -10, 16, -8, 1, 6, -15, 42, -40, 12, -1, 7, -21, 99, -162, 88, -17, 1, 8, -28, 219, -585, 514, -173, 23, -1, 9, -36, 466, -1974, 2641, -1379, 311, -30, 1, 10, -45, 968, -6388, 12538, -9536, 3245, -521, 38, -1

Offset: 0

Philippe Deléham, Apr 25 2009

			Triangle begins :
1;
2, -1;
3, -3, 1;
4, -6, 5, -1;
5, -10, 16, -8, 1;
6, -15, 42, -40, 12, -1;
7, -21, 99, -162, 88, -17, 1;
8, -28, 219, -585, 514, -173, 23, -1;
9, -36, 466, -1974, 2641, -1379, 311, -30, 1;
10, -45, 968, -6388, 12538, -9536, 3245, -521, 38, -1;
11, -55, 1981, -20132, 56540, -60218, 29006, -6892, 825, -47, 1;

G. C. Greubel, Rows n=0..100 of triangle, flattened

Cf. A000027, A000217, A002662, A152948

A159881 := proc(n,k) option remember; if k = 0 then n+1; elif k < 0 or k > n then 0 ; else k*procname(n-1,k)-procname(n-1,k-1) ; fi; end: for n from 0 to 10 do for k from 0 to n do printf("%d,",A159881(n,k)) ; od: od: # R. J. Mathar, May 29 2009

T[n_,0]:= n+1; T[n_,k_]:= T[n,k] = If[k < 0 || k > n, 0, k*T[n-1, k] - T[n-1, k-1]]; Table[T[n, k], {n, 0, 15}, {k, 0, n}]//Flatten (* G. C. Greubel, Jul 27 2018 *)

{T(n,k) = if(k==0, n+1, if(k<0 || k>n, 0, k*T(n-1,k) - T(n-1,k-1)))};
for(n=0,15, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 27 2018

Conjecture row sums: Sum_{k=0..n} |T(n,k)| = A029761(n). - R. J. Mathar, May 29 2009

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Original entry on oeis.org

0, 0, 0, 4, 56, 1008, 32736, 2097088, 268435328, 68719476480, 35184372088320, 36028797018962944, 73786976294838204416, 302231454903657293672448, 2475880078570760549798240256, 40564819207303340847894502555648, 1329227995784915872903807060280311808

Offset: 0

Gus Wiseman, Jun 23 2019

nonn

Number of simple graphs with vertices {1..n} containing two edges {a,b}, {c,d} that are weakly crossing, meaning a <= c < b <= d or c <= a < d <= b.

			The a(4) = 56 weakly crossing edge-sets:
  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}  {12,13,14,23,24,34}
  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {12,34}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {13,14}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
  {13,23}  {12,14,34}  {12,14,23,24}
  {13,24}  {12,23,24}  {12,14,23,34}
  {13,34}  {12,23,34}  {12,14,24,34}
  {14,24}  {12,24,34}  {12,23,24,34}
  {14,34}  {13,14,23}  {13,14,23,24}
  {23,24}  {13,14,24}  {13,14,23,34}
  {23,34}  {13,14,34}  {13,14,24,34}
  {24,34}  {13,23,24}  {13,23,24,34}
           {13,23,34}  {14,23,24,34}
           {13,24,34}
           {14,23,24}
           {14,23,34}
           {14,24,34}
           {23,24,34}

Cf. A000088, A000108, A002662, A006125, A016098, A054726, A324170.

Cf. A326210, A326244, A326248, A326250, A326257, A326279, A326290.

Table[If[n==0,0,2^Binomial[n,2]-2^(n-1)],{n,0,5}]

A326290 Number of non-crossing n-vertex graphs with loops.

Original entry on oeis.org

1, 2, 8, 64, 768, 11264, 184320, 3227648, 59179008, 1121714176, 21803040768, 432218832896, 8705009516544, 177618573852672, 3663840373899264, 76277945940836352, 1600706475536154624, 33823752545680490496, 719051629204296695808, 15368152475218787434496

Offset: 0

Gus Wiseman, Sep 12 2019

nonn

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.

			The a(0) = 1 through a(2) = 8 non-crossing edge sets with loops:
  {}  {}    {}
      {11}  {11}
            {12}
            {22}
            {11,12}
            {11,22}
            {12,22}
            {11,12,22}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Crossing and nesting simple graphs are (both) A326210, while non-crossing, non-nesting simple graphs are A326244.

Cf. A000108, A002061, A002662, A054726, A324172, A326252.

croXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x

seq(n)=Vec(1+3*x-4*x^2 -x*sqrt(1-24*x+16*x^2 + O(x^n))) \\ Andrew Howroyd, Sep 14 2019

From Andrew Howroyd, Sep 14 2019: (Start)
a(n) = 2^n * A054726(n).
G.f.: 1 + 3*x - 4*x^2 - x*sqrt(1 - 24*x + 16*x^2). (End)

Terms a(6) and beyond from Andrew Howroyd, Sep 14 2019

A342352 Expansion of e.g.f. (exp(x)-1)*(exp(x) - x^2/2 - x - 1).

Original entry on oeis.org

0, 0, 0, 0, 4, 15, 41, 98, 218, 465, 967, 1980, 4016, 8099, 16277, 32646, 65398, 130917, 261971, 524096, 1048364, 2096919, 4194049, 8388330, 16776914, 33554105, 67108511, 134217348, 268435048, 536870475, 1073741357, 2147483150, 4294966766, 8589934029

Offset: 0

Enrique Navarrete, Mar 08 2021

a(n) is the number of binary strings of length n that contain at least three 0's but not all digits are 0.

a(n) is also the number of proper subsets with at least three elements of an n-element set.

			a(6) = 41 since the strings are the 20 permutations of 000111, the 15 permutations of 000011, and the 6 permutations of 000001.

Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Cf. A000079, A000247, A002662.

a(n) = 2^n - Sum_{i={0,1,2,n}} binomial(n,i).

G.f.: x^4*(2*x^2-5*x+4)/((2*x-1)*(x-1)^3). - Alois P. Heinz, Mar 09 2021

A347434 E.g.f.: exp( exp(x) * (exp(x) - 1 - x - x^2 / 2) ).

Original entry on oeis.org

1, 0, 0, 1, 5, 16, 52, 274, 1990, 14354, 99704, 730225, 6061013, 56151330, 551040830, 5597109717, 59324775741, 664973687438, 7891158217876, 98253448977890, 1273082291906394, 17124091446383666, 239333235895599762, 3476600533730954761, 52394273274018321421

Offset: 0

Ilya Gutkovskiy, Sep 02 2021

nonn

Exponential transform of A002662.

Cf. A002662, A006505, A055882, A143405, A347432, A347435.

a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*binomial(n-1, j-1)*(2^j-j*(j+1)/2-1), j=1..n))
    end:
seq(a(n), n=0..24);  # Alois P. Heinz, Sep 02 2021

nmax = 24; CoefficientList[Series[Exp[Exp[x] (Exp[x] - 1 - x - x^2/2)], {x, 0, nmax}], x] Range[0, nmax]!
a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 1, k - 1] (2^k - 1 - k (k + 1)/2) a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 24}]

a(0) = 1; a(n) = Sum_{k=1..n} binomial(n-1,k-1) * A002662(k) * a(n-k).

A355551 Number of ways to select 3 or more collinear points from a 3 X n grid.

Original entry on oeis.org

1, 2, 8, 23, 61, 144, 322, 689, 1439, 2954, 6004, 12123, 24385, 48932, 98054, 196325, 392899, 786078, 1572472, 3145295, 6290981, 12582392, 25165258, 50331033, 100662631, 201325874, 402652412, 805305539, 1610611849, 3221224524, 6442449934

Offset: 1

Thomas Garrison, Jul 06 2022

			a(5)=61: there are 3*(2^5 - 1 - binomial(6,2)) ways to select 3 or more points on a horizontal line, 5 ways on a vertical line, 3 ways on a diagonal line with slope 1, 3 ways on a diagonal line with slope -1, 1 way on a diagonal line with slope 1/2, and 1 way on a diagonal line with slope -1/2; 48 + 5 + 6 + 2 = 61.

Thomas Garrison, Table of n, a(n) for n = 1...1000
Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,5,-2).

Cf. A002662 (1 X n), 2*A002662 (2 X n), A355552 (4 X n), A355553 (n X n).

LinearRecurrence[{4, -4, -2, 5, -2}, {1, 2, 8, 23, 61}, 50] (* Paolo Xausa, Oct 19 2024 *)

Python
```
def a(n): return 3*((1<
				
```

a(n) = 3*(2^n - 1 - n*(n+1)/2) + ceiling(n^2/2).
a(n) = A000982(n) + 3*A002662(n).
a(n) ~ 3*2^n.
From Stefano Spezia, Jul 10 2022: (Start)
G.f.: x*(1 - 2*x + 4*x^2 + x^3)/((1 - x)^3*(1 - x - 2*x^2)).
a(n) = (3*2^(n+2) - 4*n^2 - 6*n - 11 - (-1)^n)/4. (End)

cp's OEIS Frontend

A356116 Triangle read by row. The reduced triangle of the partition_triangle A355776.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A104713 Triangle T(n,k) = binomial(n,k), read by rows, 3 <= k <=n .

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A355776 Partition triangle read by rows. A statistic of permutations whose Lehmer code is nonmonotonic, refining triangle A356116.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A368534 a(n) = Sum_{k=1..n} binomial(k+1,2) * n^(n-k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A159881 Triangle read by rows : T(n,0) = n+1, T(n,k)=0 if k<0 or if k>n, T(n,k) = k*T(n-1,k) - T(n-1,k-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326290 Number of non-crossing n-vertex graphs with loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A342352 Expansion of e.g.f. (exp(x)-1)*(exp(x) - x^2/2 - x - 1).

Views

Author

Keywords

Comments

Examples

Links