A369596 -id:A369596 - cp's OEIS frontend

A331518 a(n) = Sum_{k=0..n} q(n,k) * !k, where q(n,k) = number of partitions of n into k distinct parts and !k = subfactorial of k.

1, 0, 0, 1, 1, 2, 4, 5, 7, 10, 21, 24, 37, 49, 71, 129, 160, 227, 313, 433, 572, 1012, 1213, 1750, 2315, 3223, 4159, 5740, 8945, 11206, 15402, 20506, 27545, 36068, 48122, 61960, 94694, 116240, 158580, 205397, 276458, 352526, 470101, 596433, 781224, 1111228

Offset: 0

Ilya Gutkovskiy, Jan 19 2020

nonn

a(n) is the number of permutations of [n] whose fixed points sum to n*(n-1)/2. a(6) = 4: 143256, 231456, 312456, 523416. - Alois P. Heinz, Mar 02 2024

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000

Cf. A000166, A008289, A032020, A331517.

Cf. A161680, A369596.

g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m+1)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..45);  # Alois P. Heinz, Mar 02 2024

Table[Sum[Length[Select[IntegerPartitions[n, {k}], UnsameQ @@ # &]] Subfactorial[k], {k, 0, n}], {n, 0, 45}]
nmax = 45; CoefficientList[Series[Sum[Subfactorial[k] x^(k (k + 1)/2)/Product[(1 - x^j), {j, 1, k}], {k, 0, nmax}], {x, 0, nmax}], x]
nmax = 50; CoefficientList[Series[Sum[Subfactorial[k] * x^(k*(k+1)/2) / Product[(1 - x^j), {j, 1, k}], {k, 0, Sqrt[2*nmax]}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 28 2020 *)

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

a(n) = A369596(n,A161680(n)). - Alois P. Heinz, Mar 02 2024

A370945 Number T(n,k) of partitions of [n] whose singletons sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1, 11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1, 41, 11, 11, 15, 15, 19, 20, 13, 10, 11, 8, 8, 5, 4, 4, 3, 2, 1, 1, 0, 0, 1, 162, 41, 41, 52, 52, 63, 67, 78, 41, 45, 39, 39, 33, 30, 20, 17, 14, 10, 10, 6, 5, 4, 3, 2, 1, 1, 0, 0, 1

Offset: 0

Alois P. Heinz, Mar 06 2024

			T(4,0) = 4: 1234, 12|34, 13|24, 14|23.
T(4,1) = 1: 1|234.
T(4,2) = 1: 134|2.
T(4,3) = 2: 124|3, 1|2|34.
T(4,4) = 2: 123|4, 1|24|3.
T(4,5) = 2: 1|23|4, 14|2|3.
T(4,6) = 1: 13|2|4.
T(4,7) = 1: 12|3|4.
T(4,10) = 1: 1|2|3|4.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0, 1;
   1, 1, 1, 1, 0, 0, 1;
   4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1;
  11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..50, flattened
Wikipedia, Partition of a set

Column k=0 gives A000296.
Row sums give A000110.
Row lengths give A000124.
Reversed rows converge to A370946.
T(n,n) gives A370947.
Cf. A000217, A053632, A105479, A369596.

h:= proc(n) option remember; `if`(n=0, 1,
      add(h(n-j)*binomial(n-1, j-1), j=2..n))
    end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);

h[n_] := h[n] = If[n == 0, 1,
    Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
    If[n == 0, h[m], b[n, i - 1, m] + b[n - i, Min[n - i, i - 1], m - 1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], { k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 12 2024, after Alois P. Heinz *)

Sum_{k=0..A000217(n)} k * T(n,k) = A105479(n+1).
T(n,A161680(n)) = A370946(n).
T(n,A000217(n)) = 1.

A369796 Number of permutations of [n] whose fixed points sum to n.

Original entry on oeis.org

1, 1, 0, 1, 3, 13, 64, 406, 2737, 23044, 200509, 2078460, 22323513, 275402437, 3501602483, 50310672046, 739235942264, 12084285146335, 202054808987101, 3703410393626031, 69269248667062892, 1409725495837854024, 29169764518508360709, 651568557906956269430

Offset: 0

Alois P. Heinz, Mar 02 2024

nonn

			a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(3) = 1: 213.
a(4) = 3: 1432, 2314, 3124.
a(5) = 13: 13542, 15243, 21435, 23415, 24135, 31425, 34125, 34215, 41235, 42351, 43125, 43215, 52314.
a(6) = 64: 123564, 123645, 132654, 134652, 136254, ..., 542136, 542316, 621435, 625413, 625431.

Alois P. Heinz, Table of n, a(n) for n = 0..450
Wikipedia, Permutation

Main diagonal of A369596.

Cf. A000142, A000166, A008289, A331518.

g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..23);

a(n) = Sum_{k>=0} A000166(n-k)*A008289(n,k).

a(n) = A369596(n,n).

cp's OEIS Frontend

A331518 a(n) = Sum_{k=0..n} q(n,k) * !k, where q(n,k) = number of partitions of n into k distinct parts and !k = subfactorial of k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A370945 Number T(n,k) of partitions of [n] whose singletons sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A369796 Number of permutations of [n] whose fixed points sum to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula