A244174 -id:A244174 - cp's OEIS frontend

A245732 Number T(n,k) of endofunctions on [n] such that at least one preimage with cardinality >=k exists and a nonempty preimage of j implies that all i<=j have preimages with cardinality >=k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 4, 3, 1, 27, 13, 1, 1, 256, 75, 7, 1, 1, 3125, 541, 21, 1, 1, 1, 46656, 4683, 141, 21, 1, 1, 1, 823543, 47293, 743, 71, 1, 1, 1, 1, 16777216, 545835, 5699, 183, 71, 1, 1, 1, 1, 387420489, 7087261, 42241, 2101, 253, 1, 1, 1, 1, 1

Offset: 0

Alois P. Heinz, Jul 30 2014

T(0,0) = 1 by convention.

In general, column k > 1 is asymptotic to n! / ((1+r^(k-1)/(k-1)!) * r^(n+1)), where r is the root of the equation 2 - exp(r) + Sum_{j=1..k-1} r^j/j! = 0. - Vaclav Kotesovec, Aug 02 2014

			Triangle T(n,k) begins:
0 :         1;
1 :         1,      1;
2 :         4,      3,    1;
3 :        27,     13,    1,   1;
4 :       256,     75,    7,   1,  1;
5 :      3125,    541,   21,   1,  1, 1;
6 :     46656,   4683,  141,  21,  1, 1, 1;
7 :    823543,  47293,  743,  71,  1, 1, 1, 1;
8 :  16777216, 545835, 5699, 183, 71, 1, 1, 1, 1;

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

Column k=0 gives A000312.
Columns k=1-10 give (for n>0): A000670, A032032, A102233, A232475, A245790, A245791, A245792, A245793, A245794, A245795.
T(2n,n) gives A244174(n) or 1+A007318(2n,n) = 1+A000984(n) for n>0.
Cf. A245733.

b:= proc(n, k) option remember; `if`(n=0, 1,
      add(b(n-j, k)*binomial(n, j), j=k..n))
    end:
T:= (n, k)-> `if`(k=0, n^n, `if`(n=0, 0, b(n, k))):
seq(seq(T(n, k), k=0..n), n=0..12);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n-j, k]*Binomial[n, j], {j, k, n}]]; T[n_, k_] := If[k == 0, n^n, If[n == 0, 0, b[n, k]]]; T[0, 0] = 1; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 05 2015, after Alois P. Heinz *)

E.g.f. (for column k > 0): 1/(2 -exp(x) +Sum_{j=1..k-1} x^j/j!) -1. - Vaclav Kotesovec, Aug 02 2014

A242451 Number T(n,k) of compositions of n in which the minimal multiplicity of parts equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 6, 1, 0, 1, 0, 15, 0, 0, 0, 1, 0, 23, 7, 1, 0, 0, 1, 0, 53, 10, 0, 0, 0, 0, 1, 0, 94, 32, 0, 1, 0, 0, 0, 1, 0, 203, 31, 21, 0, 0, 0, 0, 0, 1, 0, 404, 71, 35, 0, 1, 0, 0, 0, 0, 1, 0, 855, 77, 91, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1648, 222, 105, 71, 0, 1, 0, 0, 0, 0, 0, 1

Offset: 0

Alois P. Heinz, May 15 2014

T(0,0) = 1 by convention. T(n,k) counts the compositions of n in which at least one part has multiplicity k and no part has a multiplicity smaller than k.
T(n,n) = T(2n,n) = 1.
T(3n,n) = A244174(n).

			T(5,1) = 15: [1,1,1,2], [1,1,2,1], [1,2,1,1], [2,1,1,1], [1,2,2], [2,1,2], [2,2,1], [1,1,3], [1,3,1], [3,1,1], [2,3], [3,2], [1,4], [4,1], [5].
T(6,2) = 7: [1,1,2,2], [1,2,1,2], [1,2,2,1], [2,1,1,2], [2,1,2,1], [2,2,1,1], [3,3].
T(6,3) = 1: [2,2,2].
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,  1;
  0,   3,  0,  1;
  0,   6,  1,  0, 1;
  0,  15,  0,  0, 0, 1;
  0,  23,  7,  1, 0, 0, 1;
  0,  53, 10,  0, 0, 0, 0, 1;
  0,  94, 32,  0, 1, 0, 0, 0, 1;
  0, 203, 31, 21, 0, 0, 0, 0, 0, 1;
  0, 404, 71, 35, 0, 1, 0, 0, 0, 0, 1;

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

Columns k=0-10 give: A000007, A244164, A244165, A244166, A244167, A244168, A244169, A244170, A244171, A244172, A244173.
Row sums give A011782.
Cf. A242447 (the same for maximal multiplicity), A243978 (the same for partitions).

b:= proc(n, i, p, k) option remember; `if`(n=0, p!, `if`(i<1, 0,
       b(n, i-1, p, k) +add(b(n-i*j, i-1, p+j, k)/j!,
       j=max(1, k)..floor(n/i))))
    end:
T:= (n, k)-> b(n$2, 0, k) -`if`(n=0 and k=0, 0, b(n$2, 0, k+1)):
seq(seq(T(n, k), k=0..n), n=0..14);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[n == 0, p!, If[i < 1, 0, b[n, i - 1, p, k] + Sum[b[n - i*j, i - 1, p + j, k]/j!, {j, Max[1, k], Floor[n/i]}]]]; T[n_, k_] := b[n, n, 0, k] - If[n == 0 && k == 0, 0, b[n, n, 0, k + 1]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)

A323230 a(n) = binomial(2*(n - 1), n - 1) + 1.

Original entry on oeis.org

1, 2, 3, 7, 21, 71, 253, 925, 3433, 12871, 48621, 184757, 705433, 2704157, 10400601, 40116601, 155117521, 601080391, 2333606221, 9075135301, 35345263801, 137846528821, 538257874441, 2104098963721, 8233430727601, 32247603683101, 126410606437753, 495918532948105

Offset: 0

Peter Luschny, Feb 12 2019

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

Compare to A244174 which is "missing" the second term 2.

Cf. A000108.

[1] cat [1 + n*Catalan(n-1): n in [1..30]]; // G. C. Greubel, Dec 09 2021

aList := proc(len) local gf, ser; assume(Im(x)<0);
gf := -1/(x-1) - I*x/sqrt(4*x-1); ser := series(gf, x, len+2):
seq(coeff(ser, x, n), n=0..len) end: aList(27);
# Alternative:
a := proc(n) option remember;
if n < 2 then [1, 2][n+1] else ((4*n - 6)*a(n - 1) - 3*n + 5)/(n - 1) fi end:
seq(a(n), n=0..27); # Peter Luschny, Aug 02 2019

Table[Binomial[2(n - 1), n - 1] + 1, {n, 0, 27}]

a(n)=binomial(2*n-2, n-1)+1 \\ Charles R Greathouse IV, Oct 23 2023

[1 + binomial(2*n-2, n-1) for n in (0..30)] # G. C. Greubel, Dec 09 2021

Let G(x) = -1/(x - 1) - I*x/sqrt(4*x - 1) with Im(x) < 0, then a(n) = [x^n] G(x).
The generating function G(x) satisfies the differential equation 6*x^2 - 4*x + 1 = (4*x^4 - 9*x^3 + 6*x^2 - x)*diff(G(x), x) - (2*x^3 - 5*x^2 + 4*x - 1)*G(x).
a(n) = ((4*n - 6)*a(n - 1) - 3*n + 5)/(n - 1) for n >= 2. - Peter Luschny, Aug 02 2019
From G. C. Greubel, Dec 09 2021: (Start)
a(n) = 1 + n*A000108(n-1).
E.g.f.: exp(x) + x*exp(2*x)*(BesselI[0, 2*x] - BesselI[1, 2*x]). (End)

A065567 T(n,m) is the sum over all m-subsets of {1,...,n} of the gcd of the subset.

Original entry on oeis.org

1, 3, 1, 6, 3, 1, 10, 7, 4, 1, 15, 11, 10, 5, 1, 21, 20, 21, 15, 6, 1, 28, 26, 36, 35, 21, 7, 1, 36, 38, 60, 71, 56, 28, 8, 1, 45, 50, 90, 127, 126, 84, 36, 9, 1, 55, 67, 132, 215, 253, 210, 120, 45, 10, 1, 66, 77, 177, 335, 463, 462, 330, 165, 55, 11, 1, 78, 105, 250, 512, 798, 925, 792, 495, 220, 66, 12, 1

Offset: 1

Wouter Meeussen, Nov 30 2001

First differences of row sums equals A034738.

			Triangle begins:
   1;
   3,  1;
   6,  3,  1;
  10,  7,  4, 1;
  15, 11, 10, 5, 1;
  ...
T(4,2) = 7 = gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4).

Alois P. Heinz, Rows n = 1..200 (first 31 rows from Sean A. Irvine)

Row sums give A065568.
T(2n,n) gives A244174 for n>=1.
T(2n,n+1) gives A001791 for n>=1.
T(2n+1,n+1) gives A001700 for n>=0.
Cf. A002088, A034738.

with(combstruct):
a065567_row := proc(n) local k,L,l,R,comb;
R := NULL;
for k from 1 to n do
   L := 0;
   comb := iterstructs(Combination(n),size=k):
   while not finished(comb) do
      l := nextstruct(comb);
      L := L + igcd(op(l));
   od;
   R := R,L;
od;
R end: # Peter Luschny, Dec 07 2010
# second Maple program:
b:= proc(n, g, t) option remember; `if`(n=0, g*x^t,
      b(n-1, igcd(g, n), t+1)+b(n-1, g, t))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0$2)):
seq(T(n), n=1..12);  # Alois P. Heinz, Sep 05 2023

Table[Plus@@(GCD@@@KSubsets[Range[n], m]), {n, 16}, {m, n}]

Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A002088(n). - Alois P. Heinz, Sep 05 2023

A260883 Number of m-shape ordered set partitions, square array read by ascending antidiagonals, A(m, n) for m, n >= 0.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 3, 9, 1, 1, 7, 13, 35, 1, 1, 21, 121, 75, 161, 1, 1, 71, 1849, 3907, 541, 913, 1, 1, 253, 35641, 426405, 202741, 4683, 6103, 1, 1, 925, 762763, 65782211, 203374081, 15430207, 47293, 47319, 1, 1, 3433, 17190265, 11872636325, 323213457781, 173959321557

Offset: 1

Peter Luschny, Aug 02 2015

A set partition of m-shape is a partition of a set with cardinality m*n for some n >= 0 such that the sizes of the blocks are m times the parts of the integer partitions of n. It is ordered if the positions of the blocks are taken into account.
If m = 0, all possible sizes are zero. Thus the number of ordered set partitions of 0-shape is the number of ordered partitions of n (partition numbers A101880).
If m = 1, the set is {1, 2, ..., n} and the set of all possible sizes are the integer partitions of n. Thus the number of ordered set partitions of 1-shape is a Fubini number (sequence A000670).
If m = 2, the set is {1, 2, ..., 2n} and the number of ordered set partitions of 2-shape is also the number of 2-packed words of degree n (sequence A094088).

			[ n ] [0  1   2      3         4            5                  6]
[ m ] -----------------------------------------------------------
[ 0 ] [1, 1,  3,     9,       35,          161,              913]  A101880
[ 1 ] [1, 1,  3,    13,       75,          541,             4683]  A000670
[ 2 ] [1, 1,  7,   121,     3907,       202741,         15430207]  A094088
[ 3 ] [1, 1, 21,  1849,   426405,    203374081,     173959321557]  A243664
[ 4 ] [1, 1, 71, 35641, 65782211, 323213457781, 3482943541940351]  A243665
        A244174
For example the number of ordered set partitions of {1,2,...,9} with sizes in [9], [6,3] and [3,3,3] is 1, 168 and 1680 respectively. Thus A(3,3) = 1849.
Formatted as a triangle:
[1]
[1, 1]
[1, 1, 3]
[1, 1, 3, 9]
[1, 1, 7, 13, 35]
[1, 1, 21, 121, 75, 161]
[1, 1, 71, 1849, 3907, 541, 913]
[1, 1, 253, 35641, 426405, 202741, 4683, 6103]

Without order: A260876.

Cf. A000670, A094088, A101880, A243664, A243665, A243666, A244174.

def A260883(m, n):
    shapes = ([x*m for x in p] for p in Partitions(n))
    return sum(factorial(len(s))*SetPartitions(sum(s), s).cardinality() for s in shapes)
for m in (0..4): print([A260883(m, n) for n in (0..6)])

From Petros Hadjicostas, Aug 02 2019: (Start)

Conjecture: For n >= 0, let P be the set of all possible lists (a_1, ..., a_n) of nonnegative integers such that a_1*1 + a_2*2 + ... + a_n*n = n. Consider terms of the form multinomial(n*m, m*[1,..., 1, 2,..., 2,..., n,..., n]) * multinomial(a_1 + ... + a_n, [a_1,..., a_n]), where in the list [1,..., 1, 2,..., 2,..., n,..., n] the number 1 occurs a_1 times, 2 occurs a_2 times, ..., and n occurs a_n times. (Here a_n = 0 or 1.) Summing these terms over P we get A(m, n) provided m >= 1. (End)

A323663 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is Sum_{j=1..n} binomial(j*k, k).

Original entry on oeis.org

1, 1, 3, 1, 7, 6, 1, 21, 22, 10, 1, 71, 105, 50, 15, 1, 253, 566, 325, 95, 21, 1, 925, 3256, 2386, 780, 161, 28, 1, 3433, 19489, 18760, 7231, 1596, 252, 36, 1, 12871, 119713, 154085, 71890, 17857, 2926, 372, 45, 1, 48621, 748342, 1303753, 747860, 214396, 38332, 4950, 525, 55

Offset: 1

Seiichi Manyama, Jan 23 2019

			Square array begins:
    1,   1,    1,     1,       1,        1, ...
    3,   7,   21,    71,     253,      925, ...
    6,  22,  105,   566,    3256,    19489, ...
   10,  50,  325,  2386,   18760,   154085, ...
   15,  95,  780,  7231,   71890,   747860, ...
   21, 161, 1596, 17857,  214396,  2695652, ...
   28, 252, 2926, 38332,  539028,  7941438, ...
   36, 372, 4950, 74292, 1197036, 20212950, ...

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Columns 1-3 give A000217, A002412, A116689.
Rows 1-3 give A000012, A244174, A029848.
Main diagonal is A096131.
Cf. A060539.

A067437 Number of distinct prime factors in binomial(2*n,n)+1.

Original entry on oeis.org

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

Offset: 1

Benoit Cloitre, Feb 23 2002

Amiram Eldar, Table of n, a(n) for n = 1..212

Cf. A001221, A000984, A067434, A244174.

a[n_] := PrimeNu[Binomial[2*n,n] + 1]; Array[a,90] (* Amiram Eldar, Apr 23 2022 *)

a(n) = A001221(A244174(n)). - Amiram Eldar, Apr 23 2022

A374891 Obverse convolution (1)**A000984; see Comments.

Original entry on oeis.org

2, 6, 42, 882, 62622, 15843366, 14655113550, 50311004817150, 647552943001537650, 31484671641677762080650, 5817013478501458288734652050, 4103513269179719224996951799587650, 11096544131445222000310082187517540861050

Offset: 0

Clark Kimberling, Jul 31 2024

nonn

See A374848 for the definition of obverse convolution and a guide to related sequences. This is a divisibility sequence (see Formula).

Cf. A000012, A000984, A007685, A374848.

s[n_] := 1; t[n_] := Binomial[2 n, n];
u[n_] := Product[s[k] + t[n - k], {k, 0, n}]
Table[u[n], {n, 0, 20}]

a(n+1) = a(n)*A244174(n+1) for n>=0 (conjectured) = a(n)*A323230(n+2) for n>=0 (conjectured).

a(n) ~ c * A007685(n), where c = Product_{k=0..oo} (1 + 1/binomial(2*k,k)) = 3.74782908533723753117687910314018231428739915473496578523053032212205053... - Vaclav Kotesovec, Jul 31 2024

cp's OEIS Frontend

A245732 Number T(n,k) of endofunctions on [n] such that at least one preimage with cardinality >=k exists and a nonempty preimage of j implies that all i<=j have preimages with cardinality >=k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A242451 Number T(n,k) of compositions of n in which the minimal multiplicity of parts equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A323230 a(n) = binomial(2*(n - 1), n - 1) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A065567 T(n,m) is the sum over all m-subsets of {1,...,n} of the gcd of the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260883 Number of m-shape ordered set partitions, square array read by ascending antidiagonals, A(m, n) for m, n >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Sage

Formula

A323663 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is Sum_{j=1..n} binomial(j*k, k).

Views

Author

Keywords

Examples

Links

Crossrefs

A067437 Number of distinct prime factors in binomial(2*n,n)+1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A374891 Obverse convolution (1)**A000984; see Comments.

Views

Author

Keywords

Comments