Brian Drake - cp's OEIS frontend

A185982 Triangle read by rows: number of set partitions of n elements with k connectors, 0<=k

1, 1, 1, 1, 3, 1, 1, 7, 6, 1, 1, 16, 24, 10, 1, 1, 39, 86, 61, 15, 1, 1, 105, 307, 313, 129, 21, 1, 1, 314, 1143, 1520, 891, 242, 28, 1, 1, 1035, 4513, 7373, 5611, 2161, 416, 36, 1, 1, 3723, 18956, 36627, 34213, 17081, 4658, 670, 45, 1, 1, 14494, 84546, 188396, 208230, 127540, 45095, 9187, 1025, 55, 1

Offset: 1

Brian Drake, Feb 08 2011

			A connector is a pair (a, a+1) in a set partition if a is in block i and a+1 is in block i+1, for some i.  For example a(4,1) = 7, counting 1/234, 13/2/4, 14/23, 134/2, 12/34, 124/3, 123/4.
Triangle begins:
  1;
  1,   1;
  1,   3,   1;
  1,   7,   6,   1;
  1,  16,  24,  10,   1;
  1,  39,  86,  61,  15,  1;
  1, 105, 307, 313, 129, 21, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
T. Mansour and A. O. Munagi, Block-connected set partitions, European J. Combin., 31 (2010), 887-902.

Columns k=0-10 give: A000012, A271788, A271789, A271790, A271791, A271792, A271793, A271794, A271795, A271796, A271797.
Row sums give A000110.
T(n+1,n-1) gives A000217.
T(2n,n) gives A271841.
Cf. A185983, A270953, A271206, A271270, A271271, A272064.

b:= proc(n, i, m) option remember; `if`(n=0, 1, add(expand(
       b(n-1, j, max(m, j))*`if`(j=i+1, x, 1)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(b(n, 1, 0)):
seq(T(n), n=1..12);  # Alois P. Heinz, Mar 25 2016

b[n_, i_, m_] := b[n, i, m] = If[n == 0, 1, Sum[b[n-1, j, Max[m, j]]*If[j == i+1, x, 1], {j, 1, m+1}]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n-1}]][b[n, 1, 0]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Apr 13 2016, after Alois P. Heinz *)

More terms from Alois P. Heinz, Oct 11 2011

A185983 Triangle read by rows: number of set partitions of n elements with k circular connectors.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 8, 4, 2, 1, 1, 20, 15, 14, 1, 1, 6, 53, 61, 68, 11, 3, 1, 25, 159, 267, 295, 97, 32, 1, 1, 93, 556, 1184, 1339, 694, 242, 28, 3, 1, 346, 2195, 5366, 6620, 4436, 1762, 371, 48, 2, 1, 1356, 9413, 25400, 34991, 27497, 12977, 3650, 634, 53, 3

Offset: 0

Brian Drake, Feb 08 2011

A pair (a,a+1) in a set partition with m blocks is a circular connector if a is in block i and a+1 is in block (i mod m)+1 for some i. In addition, (n,1) is considered a circular connector if n is in block m.

			For a(4,2) = 8, the set partitions are 1/234, 134/2, 124/3, 123/4, 12/34, 14/23, 1/24/3, and 13/2/4.
For a(5,1) = 1, the set partition is 13/25/4.
For a(6,6) = 3, the set partitions are 135/246, 14/25/36, 1/2/3/4/5/6.
Triangle begins:
  1;
  1, 0;
  1, 0,  1;
  1, 0,  3,  1;
  1, 0,  8,  4,  2;
  1, 1, 20, 15, 14,  1;
  1, 6, 53, 61, 68, 11, 3;
  ...

Alois P. Heinz, Rows n = 0..60, flattened
T. Mansour and A. O. Munagi, Block-connected set partitions, European J. Combin., 31 (2010), 887-902.

Cf. A185982.  Row sums are A000110.
T(n,n) = A032741(n) if n>0. - Alois P. Heinz, Oct 14 2011
T(2n,n) gives A362944.
Cf. A271272, A271273.

b:= proc(n, i, m, t) option remember; `if`(n=0, x^(t+
     `if`(i=m and m<>1, 1, 0)), add(expand(b(n-1, j,
      max(m, j), `if`(j=m+1, 0, t+`if`(j=1 and i=m
      and j<>m, 1, 0)))*`if`(j=i+1, x, 1)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Mar 30 2016

b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, x^(t + If[i == m && m != 1, 1, 0]), Sum[Expand[b[n - 1, j, Max[m, j], If[j == m + 1, 0, t + If[j == 1 && i == m && j != m, 1, 0]]]*If[j == i + 1, x, 1]], {j, 1, m + 1}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 1, 0, 0] ];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 19 2016, after Alois P. Heinz *)

More terms from Alois P. Heinz, Oct 14 2011

A173403 Inverse binomial transform of A002416.

Original entry on oeis.org

1, 1, 13, 469, 63577, 33231721, 68519123173, 562469619451069, 18442242396353040817, 2417685638793025070212561, 1267626422541873052658376446653, 2658442047546208031914776455678477989, 22300713297142388711251601783864453690641417

Offset: 0

Brian Drake, Feb 17 2010

nonn

a(n) is the number of n X n matrices of 0's and 1's with the property that there is no index k such that both the k-th column and the k-th row consist of all zeros.

a(n) is the number of binary relations on n labeled vertices with no vertex of indegree and outdegree = 0. - Geoffrey Critzer, Oct 02 2012

E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications, Dover, 2005, exercise 4.1.6.

Brian Drake, Table of n, a(n) for n = 0..50

Cf. A002416, A135748, A287065, A048291.

N:=8: seq( sum(binomial(n,i)*2^((n-i)^2)*(-1)^(i), i=0..n), n=0..N);

Table[Sum[(-1)^k Binomial[n,k] 2^(n-k)^2,{k,0,n}],{n,0,20}]  (* Geoffrey Critzer, Oct 02 2012 *)

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

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 30 2017

A140983 E.g.f. is reversion of (2(1+x)log(1+x)+x^2+2x)/( (2+x)^2(1+x) ).

Original entry on oeis.org

1, 3, 17, 145, 1663, 24031, 419521, 8592417, 202069759, 5367258479, 158934860321, 5191969220945, 185490468312767, 7194912503747775, 301130097048242561, 13526711564792340289, 649121580063333263359, 33142745983169890692559

Offset: 1

Brian Drake, Jul 28 2008

a(n) is the number of labeled incomplete ternary trees on n vertices in which each left or middle child has a larger label than its parent and each right child has a smaller label than its parent. For example, a(2)=3 because we have 2L1, 2M1 and 1R2. Here aLb means a is a left child of b, etc.

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

Cf. A007889.

N:= 8: exp(RootOf(2*_Z*exp(_Z)-x*exp(_Z)-2*x*exp(_Z)^2-x*exp(_Z)^3 -1 +exp(_Z)^2))-1: series(%, x, N+1): convert(%, polynom): seq( i!*coeff(%, x, i), i=1..N);

A140945 Triangle read by rows: counts series-parallel networks by the number of series connections.

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 25, 25, 1, 1, 90, 290, 90, 1, 1, 301, 2450, 2450, 301, 1, 1, 966, 17451, 41580, 17451, 966, 1, 1, 3025, 112035, 544971, 544971, 112035, 3025, 1, 1, 9330, 671980, 6076350, 12122502, 6076350, 671980, 9330, 1, 1, 28501, 3846700, 60738700, 217523922, 217523922, 60738700, 3846700, 28501, 1

Offset: 1

Brian Drake, Jul 24 2008

T(n,k) is the number of series-parallel matroids on [n+1] of rank k. - Andrew Howroyd, Mar 08 2023

			Triangle begins:
  1;
  1,   1;
  1,   6,     1;
  1,  25,    25,     1;
  1,  90,   290,    90,     1;
  1, 301,  2450,  2450,   301,   1;
  1, 966, 17451, 41580, 17451, 966, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50; first 17 rows from Brian Drake, Jul 24 2008)
Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.5.1), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
Luis Ferroni and Matt Larson, Kazhdan-Lusztig polynomials of braid matroids, arXiv:2303.02253 [math.CO], 2023.
Nicholas Proudfoot, Yuan Xu, and Ben Young, On the enumeration of series-parallel matroids, arXiv:2406.04502 [math.CO], 2024.

Row sums are A006351.
Second column is A000392.
Cf. A359985.

N:=6: 1/a*log(1+a*y)+1*log(1+b*y)/b-y=x: solve(%, y):series(%, x, N): simplify(%, symbolic): convert(%, polynom): subs(b=1, %): R:= [seq(i!*coeff(%, x, i), i=1..N-1)]: seq( seq(coeff(R[i], a, j), j=0..i-1), i=1..N-1);

T(n) = {[Vecrev(p) | p<-Vec(serlaplace(intformal(serreverse(log(1 + x*y + O(x*x^n))/y + log(1 + x + O(x*x^n)) - x))))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) }  \\ Andrew Howroyd, Mar 08 2023

E.g.f. is reversion of log(1+ax)/a+log(1+bx)/b-x.

Let f(x,t) = (1+x)*(1+x*t)/(1-x^2*t) and let D be the operator f(x,t)*d/dx. Then the n-th row polynomial equals (D^n)(f(x,t)) evaluated at x = 0. - Peter Bala, Sep 29 2011

A131942 Number of partitions of n in which each odd part has odd multiplicity.

Original entry on oeis.org

1, 1, 1, 3, 3, 6, 6, 11, 13, 21, 24, 35, 44, 59, 74, 99, 126, 158, 202, 250, 320, 392, 495, 598, 758, 908, 1134, 1358, 1685, 2003, 2466, 2925, 3576, 4234, 5129, 6064, 7308, 8612, 10305, 12135, 14443, 16963, 20085, 23548, 27754, 32482, 38105, 44503, 52042

Offset: 0

Brian Drake, Jul 30 2007

			a(5)=6 because 5, 4+1, 3+2, 2+2+1, 2+1+1+1 and 1+1+1+1+1 have all odd parts with odd multiplicity. The partition 3+1+1 is the partition of 5 which is not counted.

Brian Drake and Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 101 terms from Brian Drake)
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.

Cf. A000041, A015128, A006950, A046682.

A:= series(product( 1/(1-q^(2*n)) *(1+q^(2*n-1)-q^(4*n-2))/(1-q^(4*n-2)), n=1..15),q,25): seq(coeff(A,q,i), i=0..24);

nmax = 50; CoefficientList[Series[Product[(1 + x^(2*k-1) - x^(4*k-2))/ ((1-x^(2*k)) * (1-x^(4*k-2))), {k, 1, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 03 2016 *)

G.f.: Product_{n>=1} (1+q^(2n-1)-q^(4n-2))/((1-q^(2n))(1-q^(4n-2))).

a(n) ~ sqrt(Pi^2 + 8*log(phi)^2) * exp(sqrt((Pi^2 + 8*log(phi)^2)*n/2)) / (8*Pi*n), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Jan 03 2016

A133656 Number of below-diagonal paths from (0,0) to (n,n) using steps (1,0), (0,1) and (2k-1,1), k a positive integer.

Original entry on oeis.org

1, 2, 6, 23, 99, 456, 2199, 10962, 56033, 292094, 1546885, 8299058, 45010492, 246377362, 1359339710, 7551689783, 42206697209, 237156951618, 1338917298708, 7591380528489, 43207023511013, 246773061257046, 1413889039642479, 8124356140582768, 46807462792903984

Offset: 0

Brian Drake, Sep 20 2007

			a(4) = 99 since there are 90 Schroeder paths (A006318) from (0,0) to (4,4) plus DNNEN, DNENN, DENNN, DdNN, DNdN, DNNd, EDNNN, ENDNN and dDNN, where E=(1,0), N=(0,1), D=(3,1) and d=(1,1).

Alois P. Heinz, Table of n, a(n) for n = 0..1276 (first 51 terms from Brian Drake)
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.

Cf. A006318, A064641, A052709, A063020, A348474.

Row sums of A201080.

A:=series(RootOf(1+_Z*(x-1)+_Z^2*(x-x^2)+_Z^3*x^2-_Z^4*x^3), x, 21): seq(coeff(A,x,i), i=0..20);

a[n_] := Sum[Binomial[n+k, n] * Sum[Binomial[j, -n - 3k + 2j - 2]* (-1)^(n+k-j+1) * Binomial[n+k+1, j], {j, 0, k+n+1}], {k, 0, n}]/(n+1);
a /@ Range[0, 24] (* Jean-François Alcover, Oct 06 2019, after Vladimir Kruchinin *)

a(n):=sum(binomial(n+k,n)*sum(binomial(j,-n-3*k+2*j-2)*(-1)^(n+k-j+1) *binomial(n+k+1,j),j,0,k+n+1),k,0,n)/(n+1); /* Vladimir Kruchinin, Oct 11 2011 */

G.f. g(x) satisfies: g(x) = 1 + x*g(x)^2+x*g(x)/(1-x^2*g(x)^2).
a(n) = sum(k=0..n, binomial(n+k,n)*sum(j=0..k+n+1, binomial(j,-n-3*k+2*j-2) *(-1)^(n+k-j+1)*binomial(n+k+1,j)))/(n+1). - Vladimir Kruchinin, Oct 11 2011
From Peter Bala, Feb 22 2022: (Start)
G.f. g(x) = (1/x)*series reversion of x*(1 + x)*(1 - x)^2/(1 + x - x^2).
It appears that 1 + x*g'(x)/g(x) = 1 + 2*x + 8*x^2 + 41*x^3 + 220*x^4 + ... is the g.f. of A348474. (End)

A131945 Number of partitions of n where odd parts are distinct or repeated once.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 8, 10, 15, 18, 26, 32, 45, 55, 74, 90, 119, 145, 188, 228, 291, 351, 442, 532, 664, 796, 982, 1172, 1435, 1708, 2076, 2462, 2972, 3512, 4214, 4966, 5929, 6965, 8272, 9688, 11457, 13383, 15762, 18362, 21543, 25031, 29264, 33922, 39533, 45717

Offset: 0

Brian Drake, Jul 30 2007

Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).

Also number of partitions of n such that every part is not congruent to 3 mod 6. More generally, g.f. for number of partitions of n such that every odd part occurs at most m times is product_{n=1..oo} (1-q^((m+1)*(2*n-1)))/(1-q^n). Similarly, g.f. for number of partitions of n such that every even part occurs at most m times is product_{n=1..oo} (1-q^((2*m+2)*n))/(1-q^n). - Vladeta Jovovic, Aug 01 2007

			a(6) = 8 because we have 6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 2+2+2 and 2+2+1+1. The three excluded partitions of 6 are 3+1+1+1, 2+1+1+1+1 and 1+1+1+1+1+1.
G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 5*x^5 + 8*x^6 + 10*x^7 + 15*x^8 + ...
G.f. = 1/q + q^5 + 2*q^11 + 2*q^17 + 4*q^23 + 5*q^29 + 8*q^35 + 10*q^41 + ...

Brian Drake and Seiichi Manyama, Table of n, a(n) for n = 0..1000 (first 101 terms from Brian Drake)
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
Mircea Merca, Overpartitions in terms of 2-adic valuation, Aequat. Math. (2024). See p. 11.
James A. Sellers, Elementary Proofs of Two Congruences for Partitions with Odd Parts Repeated at Most Twice, arXiv:2409.12321 [math.NT], 2024. See p. 2.
Michael Somos, Introduction to Ramanujan theta functions.
Eric Weisstein's World of Mathematics, Ramanujan Theta Functions.

Cf. A000122, A000700, A006950, A010054, A121373, A131942, A279320.

A:= series(product( (1-q^(6*n-3))/(1-q^n), n=1..20),q,21): seq(coeff(A,q,i), i=0..20);

a[ n_] := SeriesCoefficient[ QPochhammer[ x^3] / (QPochhammer[ x] QPochhammer[ x^6]), {x, 0, n}]; (* Michael Somos, Jan 29 2015 *)
a[ n_] := SeriesCoefficient[ QPochhammer[ x^3, x^6] / QPochhammer[ x], {x, 0, n}]; (* Michael Somos, Nov 11 2015 *)
nmax = 50; CoefficientList[Series[Product[1 / ((1-x^k) * (1+x^(3*k))), {k, 1, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Dec 11 2016 *)

{a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^3 + A) / (eta(x + A) * eta(x^6 + A)), n))}; /* Michael Somos, Aug 05 2007 */

G.f.: product_{n=1..oo} (1-q^(6n-3))/(1-q^n).
Expansion of chi(-x^3) / f(-x) in powers of x where chi(), f() are Ramanujan theta functions. - Michael Somos, Aug 05 2007
Expansion of q^(1/6) * eta(q^3) / (eta(q) * eta(q^6)) in powers of q. - Michael Somos, Aug 05 2007
Euler transform of period 6 sequence [ 1, 1, 0, 1, 1, 1, ...]. - Michael Somos, Aug 05 2007
a(n) ~ sqrt(5) * exp(sqrt(5*n)*Pi/3) / (12*n). - Vaclav Kotesovec, Dec 11 2016

A128520 q-inverse of x-x^2-x^3. Coefficients of a solution to the functional equation x = f(x) - f(x) f(q x) - f(x) f(q x) f(q^2 x).

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 2, 3, 1, 6, 8, 8, 7, 3, 5, 1, 8, 18, 21, 28, 17, 23, 14, 11, 5, 8, 1, 10, 32, 50, 73, 73, 77, 79, 58, 57, 44, 39, 22, 18, 8, 13, 1, 12, 50, 103, 166, 221, 238, 289, 256, 269, 226, 231, 176, 166, 113, 119, 74, 62, 36, 29, 13, 21, 1, 14, 72, 188, 347, 545, 680, 861

Offset: 1

Brian Drake, Mar 06 2007

The n-th row has binomial(n-1,2)+1 entries for n>=1. Each 1 starts a new row.
The last entry in the n-th row is the Fibonacci number F(n) = A000045(n). The second to last entry is F(n-1). The third from the end is the Lucas number L(n-1) = A000032(n-1).
The first entry in the n-th row is 1: A000012. The second entry is 2(n-2) = A005843(n-2). The third entry is 2(n-3)^2 = A001105(n-3).
The n-th row sum is A001002(n-1).

			1; 1; 1, 2; 1, 4, 2, 3; 1, 6, 8, 8, 7, 3, 5; 1, 8, 18, 21, 28, 17, 23, 14, 11, 5, 8; ...
a(4,1)=1, a(4,2)=4, a(4,3)=2, a(4,4)=3. f_4(q) = q^3 + 4 q^4 + 2 q^5 + 3 q^6. g_4(q) = 1 + 4 q + 2 q^2 + 3 q^3.

Cf. A001002, A000045, A000032, A005843, A000012, A001105.

a:= proc(n)local i, j; option remember; if n=1 then 1 else add(q^i*a(i)*a(n-i), i=1..n-1) + add(a(i) *add(q^(2*n-2*i-j)*a(j)*a(n-i-j), j=1..n-i-1), i=1..n-2); fi; expand(%); sort(%); end;

g[1]=1; g[n_]:=g[n]=Expand[Sum[q^(i-1)g[i]g[n-i],{i,1,n-1}]+Sum[q^(2i+j-2)g[i]g[j]g[n-i-j],{i,1,n-2},{j,1,n-i-1}]]; a[n_,i_]:=Coefficient[g[n],q,i-1]

Let a(n,i) be the i-th entry in the n-th row, for n >= 1 and 1 <= i <= binomial(n-1,2)+1. Let f_n(q) = Sum_{i=1..binomial(n-1,2)+1} a(n,i) q^(n+i-2) and f(x) = Sum_{n>=1} f_n(q) x^n. Then f satisfies x = f(x) - f(x) f(q x) - f(x) f(q x) f(q^2 x).
The functions f_n satisfy the recurrence f_1 = 1, f_n = Sum_{i=1..n-1}(q^i f_i f_{n-i}) + Sum_{i=1..n-2}( f_i Sum_{j=1..n-i-1}(q^(2i+j) f_j f_{n-i-j})).
Equivalently, let g_n(q) = f_n(q)/q^(n-1) = Sum_{i=0..binomial(n-1,2)} a(n,i) q^(i-2) and g(x) = q f(x/q) = Sum_{n>=1} g_n(q) x^n. Then g satisfies q^2 x = q^2 g(x) - q g(x) g(q x) - g(x) g(q x) g(q^2 x). The functions g_n satisfy g_1 = 1, g_n = Sum_{i=1..n-1} (q^(i-1) g_i g_{n-i}) + Sum_{i=1..n-2} Sum_{j=1..n-i-1} (q^(2i+j-2) g_i g_j g_{n-i-j}).

Edited by Dean Hickerson, Mar 09 2007

cp's OEIS Frontend

User: Brian Drake

A185982 Triangle read by rows: number of set partitions of n elements with k connectors, 0<=k

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A185983 Triangle read by rows: number of set partitions of n elements with k circular connectors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A173403 Inverse binomial transform of A002416.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A140983 E.g.f. is reversion of (2(1+x)log(1+x)+x^2+2x)/( (2+x)^2(1+x) ).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A140945 Triangle read by rows: counts series-parallel networks by the number of series connections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A131942 Number of partitions of n in which each odd part has odd multiplicity.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A133656 Number of below-diagonal paths from (0,0) to (n,n) using steps (1,0), (0,1) and (2k-1,1), k a positive integer.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima