A255047 -id:A255047 - cp's OEIS frontend

A083323 a(n) = 3^n - 2^n + 1.

1, 2, 6, 20, 66, 212, 666, 2060, 6306, 19172, 58026, 175100, 527346, 1586132, 4766586, 14316140, 42981186, 129009092, 387158346, 1161737180, 3485735826, 10458256052, 31376865306, 94134790220, 282412759266, 847255055012

Offset: 0

Paul Barry, Apr 27 2003

Binomial transform of A000225 (if this starts 1,1,3,7....).
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x, or 1) x = y. - Ross La Haye, Jan 10 2008
Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if either 0) x is not a subset of y and y is not a subset of x and x and y are disjoint, or 1) x equals y. Then a(n) = |R|. - Ross La Haye, Mar 19 2009

			From _Gus Wiseman_, Dec 10 2019: (Start)
Also the number of achiral set-systems on n vertices, where a set-system is achiral if it is not changed by any permutation of the covered vertices. For example, the a(0) = 1 through a(3) = 20 achiral set-systems are:
  0  0    0           0
     {1}  {1}         {1}
          {2}         {2}
          {12}        {3}
          {1}{2}      {12}
          {1}{2}{12}  {13}
                      {23}
                      {123}
                      {1}{2}
                      {1}{3}
                      {2}{3}
                      {1}{2}{3}
                      {1}{2}{12}
                      {1}{3}{13}
                      {2}{3}{23}
                      {12}{13}{23}
                      {1}{2}{3}{123}
                      {12}{13}{23}{123}
                      {1}{2}{3}{12}{13}{23}
                      {1}{2}{3}{12}{13}{23}{123}
BII-numbers of these set-systems are A330217. Fully chiral set-systems are A330282, with covering case A330229.
(End)

M. H. Albert, M. D. Atkinson, and V. Vatter, Inflations of geometric grid classes: three case studies, arXiv:1209.0425 [math.CO], 2012.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Jay Pantone, The Enumeration of Permutations Avoiding 3124 and 4312, arXiv:1309.0832 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Cf. A134319, A028243, A000079.

Cf. A000612, A003238, A330098, A330234.

List([0..30], n -> 3^n-2^n+1); # G. C. Greubel, Feb 13 2019

[3^n-2^n+1: n in [0..30]]; // G. C. Greubel, Feb 13 2019

LinearRecurrence[{6,-11,6}, {1,2,6}, 30] (* G. C. Greubel, Feb 13 2019 *)

a(n)=3^n-2^n+1 \\ Charles R Greathouse IV, Oct 07 2015

[3^n-2^n+1 for n in range(30)] # G. C. Greubel, Feb 13 2019

G.f.: (1-4*x+5*x^2)/((1-x)*(1-2*x)*(1-3*x)).
E.g.f.: exp(3*x) - exp(2*x) + exp(x).
Row sums of triangle A134319. - Gary W. Adamson, Oct 19 2007
a(n) = 2*StirlingS2(n+1,3) + StirlingS2(n+1,2) + 1. - Ross La Haye, Jan 10 2008
a(n) = Sum_{k=0..n}(binomial(n,k)*A255047(k)). - Yuchun Ji, Feb 23 2019

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 13, 1, 1, 1, 15, 157, 63, 1, 1, 1, 31, 2101, 5419, 321, 1, 1, 1, 63, 32461, 717795, 220561, 1683, 1, 1, 1, 127, 580693, 142090291, 328504401, 9763807, 8989, 1, 1, 1, 255, 11917837, 39991899123, 944362553521, 172924236255, 454635973, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 11 2015

			Square array A(n,k) begins:
  1, 1,    1,       1,            1,                1, ...
  1, 1,    3,       7,           15,               31, ...
  1, 1,   13,     157,         2101,            32461, ...
  1, 1,   63,    5419,       717795,        142090291, ...
  1, 1,  321,  220561,    328504401,     944362553521, ...
  1, 1, 1683, 9763807, 172924236255, 7622403922836151, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Columns k=0+1, 2-10 give: A000012, A001850, A115866, A263162, A263163, A263164, A263165, A263166, A263167, A263168.
Rows n=0-1 give: A000012, A255047.
Main diagonal gives A263160.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A262809.

s:= proc(n) option remember; `if`(n=0, {[]},
      map(x-> [[x[], 0], [x[], 1]][], s(n-1)))
    end:
b:= proc(l) option remember; `if`(l=[] or l[1]=0, 1,
       add((p-> `if`(p[1]<0, 0, `if`(p[1]=0, 1, b(p)))
       )(sort(l-x)), x=s(nops(l)) minus {[0$nops(l)]}))
    end:
A:= (n, k)-> b([n$k]):
seq(seq(A(n,d-n), n=0..d), d=0..10);

g[k_] := Table[Reverse[IntegerDigits[n, 2]][[;;k]], {n, 2^k+1, 2^(k+1)-1}];
b[l_] := b[l] = If[l[[1]] == 0, 1, Sum[b[Sort[l - h]], {h, g[k]}]];
a[n_, k_] := If[n == 0 || k == 0 || k == 1, 1, b[Table[n, {k}]]];
Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Apr 25 2020, after Alois P. Heinz in A115866 *)

A349488 Number of unlabeled disconnected P-series with n elements.

Original entry on oeis.org

0, 1, 2, 6, 16, 45, 115, 296, 733, 1801, 4338, 10380, 24531, 57622, 134317, 311465, 718297, 1649579, 3772448, 8597284, 19527774, 44225665, 99885035, 225032910, 505797776, 1134419571, 2539173978, 5672736196, 12650878942, 28165845957, 62609097765, 138963709623

Offset: 1

Salah Uddin Mohammad, Nov 19 2021

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..3217

Cf. A255047, A349276.

b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(d*
      max(1, 2^(d-1)-1), d=numtheory[divisors](j)), j=1..n)/n)
    end:
a:= n-> b(n)-max(1, 2^(n-1)-1):
seq(a(n), n=1..35);  # Alois P. Heinz, Jan 05 2022

b[n_] := b[n] = If[n == 0, 1, Sum[b[n - j]*Sum[d*
     Max[1, 2^(d-1) - 1], {d, Divisors[j]}], {j, 1, n}]/n];
a[n_] := b[n] - Max[1, 2^(n-1)-1];
Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Mar 11 2022, Alois P. Heinz *)

a(n) = A349276(n) - A255047(n-1).

A291117 Triangle read by rows: T(n,k) = number of ways of partitioning the (n+2)-element multiset {1,1,1,2,3,...,n} into exactly k nonempty parts, n >= 0 and 1 <= k <= n + 2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 8, 4, 1, 1, 15, 30, 20, 7, 1, 1, 31, 104, 102, 46, 11, 1, 1, 63, 342, 496, 300, 96, 16, 1, 1, 127, 1088, 2294, 1891, 786, 183, 22, 1, 1, 255, 3390, 10200, 11417, 6167, 1862, 323, 29, 1, 1, 511, 10424, 44062, 66256, 46417, 17801, 4040, 535, 37, 1, 1, 1023, 31782, 186416, 372190, 336022, 162372, 46425, 8127, 841, 46, 1

Offset: 0

Marko Riedel, Aug 17 2017

			Triangle begins:
  1,   1;
  1,   1,   1;
  1,   3,   2,   1;
  1,   7,   8,   4,   1;
  1,  15,  30,  20,   7,  1;
  1,  31, 104, 102,  46, 11,  1;
  1,  63, 342, 496, 300, 96, 16, 1;

M. Griffiths and I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5.
Marko Riedel, Partitions into bounded blocks, Mathematics Stack Exchange.
Marko Riedel, Maple code for sequences A241500, A291117, A291118, A291119, A291120.

Cf. A241500, A291118, A291119, A291120.

Columns k=1..4: A000012, A255047, A168605, A168606.

Formula including proof is at web link.

A265202 Total number of lambda-parking functions induced by all partitions of n into distinct parts.

Original entry on oeis.org

1, 1, 2, 6, 9, 15, 36, 53, 78, 119, 286, 401, 591, 829, 1232, 2910, 4084, 5789, 8070, 11281, 15823, 37747, 51622, 72919, 98986, 136600, 181648, 254638, 586891, 799841, 1110303, 1495279, 2018749, 2657612, 3552560, 4738775, 10857521, 14560375, 20061359, 26603227

Offset: 0

Alois P. Heinz, Dec 04 2015

nonn

			a(0) = 1: [].
a(1) = 1: [1].
a(2) = 2: [1], [2].
a(3) = 6: [1], [2], [3], [1,1], [1,2], [2,1].
a(4) = 9: [1], [2], [3], [4], [1,1], [1,2], [1,3], [2,1], [3,1].
a(5) = 15: [1], [2], [3], [4], [5], [1,1], [1,2], [1,3], [1,4], [2,1], [2,2], [2,3], [3,1], [3,2], [4,1].
a(6) = 36: [1], [2], [3], [4], [5], [6], [1,1], [1,2], [1,3], [1,4], [1,5], [2,1], [2,2], [2,3], [2,4], [3,1], [3,2], [4,1], [4,2], [5,1], [1,1,1], [1,1,2], [1,1,3], [1,2,1], [1,2,2], [1,2,3], [1,3,1], [1,3,2], [2,1,1], [2,1,2], [2,1,3], [2,2,1], [2,3,1], [3,1,1], [3,1,2], [3,2,1].

Alois P. Heinz, Table of n, a(n) for n = 0..400
Richard P. Stanley, Parking Functions, 2011

Row sums of A265208.

Cf. A000009, A255047, A265016.

b:= proc(p, g, n, i, t) option remember; `if`(g=0, 0, p!/g!)+
      `if`(n `if`(n=0, 1, b(0$2, n, 1$2)):
seq(a(n), n=0..50);

b[p_, g_, n_, i_, t_] := b[p, g, n, i, t] = If[g==0, 0, p!/g!] + If[nJean-François Alcover, Feb 02 2017, translated from Maple *)

A277031 Number T(n,k) of permutations of [n] where the minimal cyclic distance between elements of the same cycle equals k (k=n for the identity permutation in S_n); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 5, 0, 1, 0, 20, 3, 0, 1, 0, 109, 10, 0, 0, 1, 0, 668, 44, 7, 0, 0, 1, 0, 4801, 210, 28, 0, 0, 0, 1, 0, 38894, 1320, 90, 15, 0, 0, 0, 1, 0, 353811, 8439, 554, 75, 0, 0, 0, 0, 1, 0, 3561512, 63404, 3542, 310, 31, 0, 0, 0, 0, 1, 0, 39374609, 517418, 23298, 1276, 198, 0, 0, 0, 0, 0, 1

Offset: 0

Alois P. Heinz, Sep 25 2016

			T(3,1) = 5: (1,2,3), (1,3,2), (1)(2,3), (1,2)(3), (1,3)(2).
T(3,3) = 1: (1)(2)(3).
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       1,     1;
  0,       5,     0,    1;
  0,      20,     3,    0,   1;
  0,     109,    10,    0,   0,  1;
  0,     668,    44,    7,   0,  0, 1;
  0,    4801,   210,   28,   0,  0, 0, 1;
  0,   38894,  1320,   90,  15,  0, 0, 0, 1;
  0,  353811,  8439,  554,  75,  0, 0, 0, 0, 1;
  0, 3561512, 63404, 3542, 310, 31, 0, 0, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..12, flattened
Per Alexandersson et al., d-regular partitions and permutations, MathOverflow, 2014

Columns k=0-1 give: A000007, A277032.
Row sums give A000142.
T(2n,n) = A255047(n) = A000225(n) for n>0.
Cf. A239145, A263757, A276974.

A349276 Number of unlabeled P-series with n elements.

Original entry on oeis.org

1, 2, 5, 13, 31, 76, 178, 423, 988, 2312, 5361, 12427, 28626, 65813, 150700, 344232, 783832, 1780650, 4034591, 9121571, 20576349, 46322816, 104079338, 233421517, 522574991, 1167974002, 2606282841, 5806953923, 12919314397, 28702716868, 63682839588, 141111193270

Offset: 1

Salah Uddin Mohammad, Nov 12 2021

nonn

The class of all P-series is a subclass of the class of series-parallel posets and it contains the class of P-graphs as a subclass.
A poset is called a P-graph if it can be expressed as the ordinal sum of the antichain posets (including the singleton poset).
A poset is called a P-series if it is either a P-graph or it can be expressed as the direct sum of the P-graphs.
For example, all the 3-element posets are P-series, where only the connected posets and the antichains are P-graphs. On the other hand, the 4-element poset <{x,y,z,w},{x<.z, z<.w, y<.w, x||y, y||z}> and its dual are both series-parallel which are not the P-series. Here, by 'x<.z' we mean 'x is covered by z'.

Alois P. Heinz, Table of n, a(n) for n = 1..3217

Cf. A003430 (series-parallel posets), A255047, A349488.

a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*add(d*
      max(1, 2^(d-1)-1), d=numtheory[divisors](j)), j=1..n)/n)
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Jan 05 2022

a[n_] := a[n] = If[n == 0, 1, Sum[a[n - j]*Sum[d*
     Max[1, 2^(d - 1) - 1], {d, Divisors[j]}], {j, 1, n}]/n];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Mar 18 2022, after Alois P. Heinz *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={EulerT(Vec((1 -2*x +2*x^2)/((1-x)*(1-2*x)) + O(x*x^n)))} \\ Andrew Howroyd, Nov 19 2021

a(n) = A255047(n-1) + A349488(n).

G.f: -1 + exp(Sum_{k>=1} B(x^k)/k) where B(x) = x*(1 - 2*x + 2*x^2)/((1 - x)*(1 - 2*x)). - Andrew Howroyd, Jan 06 2022

A265007 Total sum of number of lambda-parking functions, where lambda ranges over all partitions of n.

Original entry on oeis.org

1, 1, 3, 7, 18, 40, 97, 216, 499, 1112, 2502, 5503, 12197, 26582, 58088, 125619, 271713, 583228, 1251115, 2668651, 5685053, 12059993, 25544291, 53926003, 113666195, 238946232, 501546514, 1050430420, 2196869731, 4586021745, 9560876381, 19900839742, 41373446190

Offset: 0

Alois P. Heinz, Nov 29 2015

nonn

			The number of lambda-parking functions induced by the partitions of 4:
1 by [1,1,1,1]: [1,1,1,1],
4 by [1,1,2]: [1,1,1], [1,1,2], [1,2,1], [2,1,1],
4 by [2,2]: [1,1], [1,2], [2,1], [2,2],
5 by [1,3]: [1,1], [1,2], [2,1], [1,3], [3,1],
4 by [4]: [1], [2], [3], [4].
a(4) = 1 + 4 + 4 + 5 + 4 = 18.

Alois P. Heinz, Table of n, a(n) for n = 0..50
R. Stanley, Parking Functions, 2011

Cf. A000041, A255047, A265016.

p:= l-> (n-> n!*LinearAlgebra[Determinant](Matrix(n, (i, j)
         -> (t->`if`(t<0, 0, l[i]^t/t!))(j-i+1))))(nops(l)):
g:= (n, i, l)-> `if`(n=0 or i=1, p([1$n, l[]]), g(n, i-1, l)
               +`if`(i>n, 0, g(n-i, i, [i, l[]]))):
a:= n-> g(n$2, []):
seq(a(n), n=0..20);

p[l_] := With[{n = Length[l]}, n! Det[Table[With[{t = j - i + 1},
     If[t < 0, 0, l[[i]]^t/t!]], {i, n}, {j, n}]]];
g[n_, i_, l_] := If[n == 0 || i == 1, p[Join[
     Table[1, {n}], l]], g[n, i - 1, l] +
     If[i > n, 0, g[n - i, i, Prepend[l, i]]]];
a[n_] := If[n == 0, 1, g[n, n, {}]];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Aug 22 2021, after Alois P. Heinz *)

A134319 Triangle read by rows. T(n, k) = binomial(n, k)*(2^k - 1 + 0^k).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 9, 7, 1, 4, 18, 28, 15, 1, 5, 30, 70, 75, 31, 1, 6, 45, 140, 225, 186, 63, 1, 7, 63, 245, 525, 651, 441, 127, 1, 8, 84, 392, 1050, 1736, 1764, 1016, 255, 1, 9, 108, 588, 1890, 3906, 5292, 4572, 2295, 511, 1, 10, 135, 840, 3150, 7812, 13230, 15240, 11475, 5110, 1023

Offset: 0

Gary W. Adamson, Oct 19 2007

			First few rows of the triangle:
  1;
  1, 1;
  1, 2,  3;
  1, 3,  9,   7;
  1, 4, 18,  28,  15;
  1, 5, 30,  70,  75,  31;
  1, 6, 45, 140, 225, 186,  63;
  1, 7, 63, 245, 525, 651, 441, 127;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Cf. A083313, A083323 (row sums), A255047 (main diagonal).

x:= 'x': T:= (n,k)-> `if` (k=0, 1, abs(coeff(expand((1-1/2^x)^n -(1-2/2^x)^n), 1/(2^x)^k))): seq(seq(T(n,k), k=0..n), n=0..12); # Alois P. Heinz, Dec 10 2008
# Alternative:
T := (n, k) -> binomial(n, k)*(2^k - 1 + 0^k):
for n from 0 to 7 do seq(T(n, k), k=0..n) od;
# Or as a recursion:
p := proc(n, m) option remember; if n = 0 then max(1, m) else
    (m + x)*p(n - 1, m) - (m + 1)*p(n - 1, m + 1) fi end:
Trow := n -> seq((-1)^k * coeff(p(n, 0), x, n - k), k = 0..n):  # Peter Luschny, Jun 23 2023

max = 10; T1 = Table[Binomial[n, k], {n, 0, max}, {k, 0, max}]; T2 = Table[ If[n == k, 2^n-1, 0], {n, 0, max}, {k, 0, max}]; TT = T1.T2 ; T[, 0]=1; T[n, k_] := TT[[n+1, k+1]]; Table[T[n, k], {n, 0, max}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 26 2016 *)

Previous definition: A007318 * a triangle by rows: for n > 0, n zeros followed by 2^n - 1.
Binomial transform of a diagonalized infinite lower triangular matrix with (1, 1, 3, 7, 15, ...) in the main diagonal and the rest zeros.
T(n,k) = |[1/(2^x)^k] 1 + (1-1/2^x)^n - (1-2/2^x)^n|. - Alois P. Heinz, Dec 10 2008
T(n,k) = binomial(n,k)*M(k) where M is Mersenne-like A255047. - Yuchun Ji, Feb 13 2019

More terms from Alois P. Heinz, Dec 10 2008

New name using a formula of Yuchun Ji by Peter Luschny, Jun 23 2023

A350635 Triangle read by rows: T(n,k) is the number of n-element unlabeled P-series with k connected components.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 7, 4, 1, 1, 15, 10, 4, 1, 1, 31, 28, 11, 4, 1, 1, 63, 67, 31, 11, 4, 1, 1, 127, 167, 80, 32, 11, 4, 1, 1, 255, 388, 213, 83, 32, 11, 4, 1, 1, 511, 908, 534, 226, 84, 32, 11, 4, 1, 1, 1023, 2053, 1343, 580, 229, 84, 32, 11, 4, 1, 1

Offset: 1

Salah Uddin Mohammad, Jan 09 2022

			Triangle begins:
    1;
    1,   1;
    3,   1,  1;
    7,   4,  1,  1;
   15,  10,  4,  1,  1;
   31,  28, 11,  4,  1, 1;
   63,  67, 31, 11,  4, 1, 1;
  127, 167, 80, 32, 11, 4, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Row sums give A349276.
Column 1 is A255047(n-1).
Cf.  A263864 (all posets), A349488 (disconnected).

B(x) = x*(1 - 2*x + 2*x^2)/((1 - x)*(1 - 2*x))
T(n)=[Vecrev(p/y) | p<-Vec(-1 + exp(sum(k=1, n, y^k*B(x^k)/k + O(x*x^n))))]
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 13 2022

G.f.: -1 + exp(Sum_{k>=1} y^k*B(x^k)/k) where B(x) = x*(1 - 2*x + 2*x^2)/((1 - x)*(1 - 2*x)). - Andrew Howroyd, Jan 13 2022

cp's OEIS Frontend

A083323 a(n) = 3^n - 2^n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A349488 Number of unlabeled disconnected P-series with n elements.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A291117 Triangle read by rows: T(n,k) = number of ways of partitioning the (n+2)-element multiset {1,1,1,2,3,...,n} into exactly k nonempty parts, n >= 0 and 1 <= k <= n + 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A265202 Total number of lambda-parking functions induced by all partitions of n into distinct parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A277031 Number T(n,k) of permutations of [n] where the minimal cyclic distance between elements of the same cycle equals k (k=n for the identity permutation in S_n); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

A349276 Number of unlabeled P-series with n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A265007 Total sum of number of lambda-parking functions, where lambda ranges over all partitions of n.

Views

Author

Keywords

Examples

Links

Crossrefs