A098825 -id:A098825 - cp's OEIS frontend

A351983 Number of integer compositions of n with exactly one part above the diagonal.

0, 0, 1, 2, 5, 9, 18, 35, 67, 131, 257, 505, 996, 1973, 3915, 7781, 15486, 30855, 61527, 122764, 245069, 489412, 977673, 1953515, 3904108, 7803545, 15599618, 31187269, 62355347, 124679883, 249310255, 498540890, 996953659, 1993701032, 3987069747, 7973603891

Offset: 0

Gus Wiseman, Apr 02 2022

nonn

			The a(2) = 1 through a(6) = 18 compositions:
  (2)  (3)   (4)    (5)     (6)
       (21)  (13)   (14)    (15)
             (22)   (32)    (42)
             (31)   (41)    (51)
             (211)  (131)   (114)
                    (212)   (132)
                    (221)   (141)
                    (311)   (213)
                    (2111)  (222)
                            (312)
                            (321)
                            (411)
                            (1311)
                            (2112)
                            (2121)
                            (2211)
                            (3111)
                            (21111)

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

The version for permutations is A000295, weak A057427.
The version for partitions is A002620, weak A001477.
The weak version is A177510.
The version for fixed points is A240736, nonfixed A352520.
This is column k = 1 of A352524; column k = 0 is A008930.
A238349 counts compositions by fixed points, first column A238351.
A352521 counts compositions by strong nonexcedances, first column A219282.
A352522 counts compositions by weak nonexcedances, first column A238874.
A352523 counts compositions by nonfixed points, first column A010054.
A352524 counts compositions by strong excedances, first column A008930.
A352525 counts compositions by weak excedances, first column A177510.
Cf. A088218, A098825, A115994, A238352, A330644, A352516.

pless[y_]:=Length[Select[Range[Length[y]],#

S(v,u,c=0)={vector(#v, k, c + sum(i=1, k-1, v[k-i]*u[i]))}
seq(n)={my(v=vector(1+n), s=0); v[1]=1; for(i=1, n, v=S(v, vector(n, j, if(j>i,'x,1)), O(x^2)); s+=apply(p->polcoef(p,1), v)); s} \\ Andrew Howroyd, Jan 02 2023

Terms a(21) and beyond from Andrew Howroyd, Jan 02 2023

A372102 Number of permutations of [n] whose non-fixed points are not neighbors.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 19, 45, 107, 278, 728, 2033, 5749, 17105, 51669, 162674, 520524, 1724329, 5807143, 20146861, 71048431, 257139686, 945626800, 3558489633, 13599579817, 53060155137, 210124405097, 847904374466, 3470756061140, 14453943647561, 61023690771451

Offset: 0

Alois P. Heinz, Apr 18 2024

nonn

			a(3) = 2: 123, 321.
a(4) = 4: 1234, 1432, 3214, 4231.
a(5) = 9: 12345, 12543, 14325, 15342, 32145, 32541, 42315, 52143, 52341.
a(6) = 19: 123456, 123654, 125436, 126453, 143256, 143652, 153426, 163254, 163452, 321456, 325416, 326451, 423156, 423651, 521436, 523416, 621453, 623154, 623451.

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

Cf. A000142, A000166, A001629, A011973, A098825, A131735, A162969, A165961, A371995.

a:= proc(n) option remember; `if`(n<4, [2$3, 4][n+1],
      3*a(n-1)+(n-2)*a(n-2)+(n-1)*(a(n-4)-a(n-3)))/2
    end:
seq(a(n), n=0..30);

a[n_] := Sum[Binomial[n + 1 - k, k] * Subfactorial[k], {k, 0, (n + 1)/2}];
Table[a[n], {n, 0, 30}] (* Peter Luschny, Apr 24 2024 *)

a(n) = Sum_{j=0..floor((n+1)/2)} A000166(j)*A011973(n+1,j).
a(n) mod 2 = A131735(n+3).
Row sums of A371995(n+1), which are the antidiagonals of A098825. - Peter Luschny, Apr 24 2024
a(n) ~ sqrt(Pi) * exp(sqrt(n/2) - n/2 - 7/8) * n^(n/2 + 1) / 2^((n+3)/2). - Vaclav Kotesovec, Apr 25 2024

A281262 Number of permutations of [2n] with exactly n fixed points.

Original entry on oeis.org

1, 0, 6, 40, 630, 11088, 244860, 6362928, 190900710, 6490575520, 246642054516, 10358965584240, 476512419579196, 23825620968559200, 1286583532342313400, 74621844875699059680, 4626554382293942780550, 305352589231397889910080, 21374681246197861368840900

Offset: 0

Alois P. Heinz, Apr 12 2017

nonn

			a(2) = 6: 1243, 1324, 1432, 2134, 3214, 4231.

Alois P. Heinz, Table of n, a(n) for n = 0..366

Cf. A000166, A007318, A008290, A098825.

a:= proc(n) option remember; `if`(n<2, 1-n,
      (4*n-2)*((n-1)*a(n-1)+(4*n-6)*a(n-2))/n)
    end:
seq(a(n), n=0..20);

a[n_] := Binomial[2n, n] Subfactorial[n];
a /@ Range[0, 20] (* Jean-François Alcover, Sep 01 2021 *)

a(n) = (4*n-2)*((n-1)*a(n-1)+(4*n-6)*a(n-2))/n for n>1, a(n) = 1-n for n<2.
a(n) = binomial(2n,n) * A000166(n).
a(n) = A008290(2n,n) = A098825(2n,n).

A352875 Number of integer compositions y of n with a fixed point y(i) = i.

Original entry on oeis.org

0, 1, 1, 2, 5, 10, 21, 42, 86, 174, 351, 708, 1424, 2861, 5743, 11520, 23092, 46269, 92673, 185562, 371469, 743491, 1487870, 2977164, 5956616, 11916910, 23839736, 47688994, 95393322, 190811346, 381662507, 763389209, 1526881959, 3053930971, 6108131542, 12216698288

Offset: 0

Gus Wiseman, May 15 2022

nonn

			The a(0) = 0 through a(5) = 10 compositions (empty column indicated by dot):
  .  (1)  (11)  (12)   (13)    (14)
                (111)  (22)    (32)
                       (112)   (113)
                       (121)   (122)
                       (1111)  (131)
                               (221)
                               (1112)
                               (1121)
                               (1211)
                               (11111)

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

The version for partitions is A001522, ranked by A352827 (unproved).
The version for permutations is A002467, complement A000166.
The complement for partitions is A064428, ranked by A352826 (unproved).
This is the sum of latter columns of A238349, nonfixed A352523.
The complement is counted by A238351.
The complement for reversed partitions is A238394, ranked by A352830.
The version for reversed partitions is A238395, ranked by A352872.
The case of just one fixed point is A240736.
A008290 counts permutations by fixed points, nonfixed A098825.
A011782 counts compositions.
A115720 and A115994 count partitions by Durfee square.
A238352 counts reversed partitions by fixed points, rank statistic A352822.
A352512 counts fixed points in standard compositions, nonfixed A352513.
A352521 = comps by subdiags, first col A219282, rank stat A352514.
A352522 = comps by weak subdiags, first col A238874, rank stat A352515.
A352524 = comps by superdiags, first col A008930, rank stat A352516.
A352525 = comps by weak superdiags, col k=1 A177510, rank stat A352517.
A352833 counts partitions by fixed points.
Cf. A006918, A008292, A088218, A114088, A123125, A188674, A257990.

pq[y_]:=Length[Select[Range[Length[y]],#==y[[#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],pq[#]>0&]],{n,0,15}]

S(v,u,c)={vector(#v, k, c + sum(i=1, k-1, v[k-i]*u[i]))}
seq(n)={my(v=vector(1+n), s=vector(#v, i, 2^(i-2))); v[1]=1; s[1]=0; for(i=1, n, v=S(v, vector(n, j, if(j==i,'x,1)), O(x)); s-=apply(p->polcoef(p,0), v)); s} \\ Andrew Howroyd, Jan 02 2023

a(n) = 2^(n-1) - A238351(n) for n >= 1. - Andrew Howroyd, Jan 02 2023

Terms a(21) and beyond from Andrew Howroyd, Jan 02 2023

A373417 Triangle T(n,k) for the number of permutations in symmetric group S_n with (n-k) fixed points and an even number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k<=n that contain an even number of parts.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 0, 15, 20, 1, 0, 0, 0, 45, 120, 130, 1, 0, 0, 0, 105, 420, 910, 924, 1, 0, 0, 0, 210, 1120, 3640, 7392, 7413, 1, 0, 0, 0, 378, 2520, 10920, 33264, 66717, 66744, 1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476

Offset: 0

Julian Hatfield Iacoponi, Jun 04 2024

A343418(n) + a(n) = A098825(n) = partial derangement "rencontres" triangle.
A343418(n) - a(n) = (k-1) * binomial(n,k) = A127717(n-1,k-1).
Difference of 1st and 2nd leading diagonals (n > 0).
T(n,n) - T(n,n-1) = -1,0,0,3,5,10,14,21,27,36,44,...
                  = (-1) + (1+0) + (3+2) + (5+4) + (7+6) + (9+8) + ...
Cf. A176222(n) with 2 terms -1,0 prepended (moving its offset from 3 to 1).

			Triangle array T(n,k):
  n:  {k<=n}
  0:  {1}
  1:  {1, 0}
  2:  {1, 0, 0}
  3:  {1, 0, 0, 0}
  4:  {1, 0, 0, 0,   3}
  5:  {1, 0, 0, 0,  15,   20}
  6:  {1, 0, 0, 0,  45,  120,   130}
  7:  {1, 0, 0, 0, 105,  420,   910,    924}
  8:  {1, 0, 0, 0, 210, 1120,  3640,   7392,   7413}
  9:  {1, 0, 0, 0, 378, 2520, 10920,  33264,  66717,  66744}
  10: {1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476}
T(n,0) = 1 due to sole permutation in S_n with n fixed points, namely the identity permutation, with 0 non-fixed point cycles, an even number. (T(0,0)=1 relies on S_0 containing an empty permutation.)
T(n,1) = 0 due to no permutations in S_n with (n-1) fixed points.
T(n,2) = T(n,3) = 0 due to only non-unity partitions of 2 and 3 being of odd length, namely the trivial partitions (2),(3).
Example:
T(4,4) = 3 since S_4 contains 3 permutations with 0 fixed points and an even number of non-fixed point cycles, namely the derangements: (12)(34),(13)(24),(14)(23).
Worked Example:
T(7,6) = 910 permutations in S_7 with 1 fixed point and an even number of non-fixed point cycles.
T(7,6) = 910 possible (4,2)- and (3,3)-cycles of 7 items.
N(n,y) = possible y-cycles of n items.
N(n,y) = (n!/(n-k)!) / (M(y) * s(y)).
y = partition of k<=n with q parts = (p_1, p_2, ..., p_i, ..., p_q)
s.t. k = Sum_{i=1..q} p_i.
Or:
y = partition of k<=n with d distinct parts, each with multiplicity m_j = (y_1^m_1, y_2^m_2, ..., y_j^m_j, ..., y_d^m_d)
s.t. k = Sum_{j=1..d} m_j*y_j.
M(y) = Product_{i=1..q} p_i = Product_{j=1..d} y_j^m_j.
s(y) = Product_{j=1..d} m_j! ("symmetry of repeated parts").
Note: (n!/(n-k)!) / s(y) = multinomial(n, {m_j}).
Therefore:
T(7,6) = N(7,y=(4,2)) + N(7,y=(3^2))
       = (7!/(4*2)) + (7!/(3^2)/2!)
       = 7! * (1/8 + 1/18)
       = 5040 * (13/72)
T(7,6) = 910.

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)

Cf. A373418 (odd case), A373339 (row sums), A216778 (main diagonal).

b:= proc(n, t) option remember; `if`(n=0, t, add(expand(`if`(j>1, x^j, 1)*
      b(n-j, irem(t+signum(j-1), 2)))*binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1)):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 04 2024

Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)), {k, 0, n}], {n, 0, 10}]

T(n,k) = (n!/(n-k)!/2) * (Sum_{j=0..k} (-1)^j/j! - (k-1)/k!) Cf. Sum_{j=0..k} (-1)^j/j! = A053557(k) / A053556(k).

A373418 Triangle read by rows: T(n,k) is the number of permutations in symmetric group S_n with (n-k) fixed points and an odd number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k <= n that contain an odd number of parts.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 3, 2, 0, 0, 6, 8, 6, 0, 0, 10, 20, 30, 24, 0, 0, 15, 40, 90, 144, 135, 0, 0, 21, 70, 210, 504, 945, 930, 0, 0, 28, 112, 420, 1344, 3780, 7440, 7420, 0, 0, 36, 168, 756, 3024, 11340, 33480, 66780, 66752, 0, 0, 45, 240, 1260, 6048, 28350, 111600, 333900, 667520, 667485

Offset: 0

Julian Hatfield Iacoponi, Jun 04 2024

a(n) + A343417(n) = A098825(n) = partial derangement "rencontres" triangle.
a(n) - A343417(n) = (k-1) * binomial(n,k) = A127717(n-1,k-1).
Difference of 2nd and 1st leading diagonals (n > 0):
T(n,n-1) - T(n,n) = 0,-1,1,2,6,9,15,20,28,35,45,54,...
                  = (0-1) + (2+1) + (4+3) + (6+5) + (8+7) + (10+9) + ...
Cf. A084265(n) with 2 terms 0,-1 prepended (moving its offset from 0 to -2).

			Triangle begins:
   n: {k<=n}
   0: {0}
   1: {0, 0}
   2: {0, 0,  1}
   3: {0, 0,  3,   2}
   4: {0, 0,  6,   8,    6}
   5: {0, 0, 10,  20,   30,   24}
   6: {0, 0, 15,  40,   90,  144,   135}
   7: {0, 0, 21,  70,  210,  504,   945,    930}
   8: {0, 0, 28, 112,  420, 1344,  3780,   7440,   7420}
   9: {0, 0, 36, 168,  756, 3024, 11340,  33480,  66780,  66752}
  10: {0, 0, 45, 240, 1260, 6048, 28350, 111600, 333900, 667520, 667485}
T(n,0) = 0 because the sole permutation in S_n with n fixed points, namely the identity permutation, has 0 non-fixed point cycles, not an odd number.
T(n,1) = 0 because there are no permutations in S_n with (n-1) fixed points.
Example:
T(3,3) = 2 since S_3 contains 3 permutations with 0 fixed points and an odd number of non-fixed point cycles, namely the derangements (123) and (132).
Worked Example:
T(7,6) = 945 permutations in S_7 with 1 fixed point and an odd number of non-fixed point cycles;
T(7,6) = 945 possible 6- and (2,2,2)-cycles of 7 items.
N(n,y) = possible y-cycles of n items;
N(n,y) = (n!/(n-k)!) / (M(y) * s(y)).
y = partition of k<=n with q parts = (p_1, p_2, ..., p_i, ..., p_q) such that k = Sum_{i=1..q} p_i.
Or:
y = partition of k<=n with d distinct parts, each with multiplicity m_j = (y_1^m_1, y_2^m_2, ..., y_j^m_j, ..., y_d^m_d) such that k = Sum_{j=1..d} m_j*y_j.
M(y) = Product_{i=1..q} p_i = Product_{j=1..d} y_j^m_j.
s(y) = Product_{j=1..d} m_j! ("symmetry of repeated parts").
Note: (n!/(n-k)!) / s(y) = multinomial(n, {m_j}).
Therefore:
T(7,6) = N(7,y=(6)) + N(7,y=(2^3))
       = (7!/6) + (7!/(2^3)/3!)
       = 7! * (1/6 + 1/48)
       = 5040 * (3/16);
T(7,6) = 945.

Cf. A373417 (even case), A373340 (row sums), A216779 (main diagonal).

b:= proc(n, t) option remember; `if`(n=0, t, add(expand(`if`(j>1, x^j, 1)*
      b(n-j, irem(t+signum(j-1), 2)))*binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..10);

Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)),{k,1,n}], {n,1,10}]

T(n,k) = (n!/(n-k)!/2) * ((Sum_{j=0..k} (-1)^j/j!) + (k-1)/k!). Cf. Sum_{j=0..k} (-1)^j/j! = A053557(k) / A053556(k).

A353315 Triangle read by rows where T(n,k) is the number of integer partitions of n with k parts on or below the diagonal (weak non-excedances).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 2, 1, 0, 1, 2, 2, 3, 2, 1, 0, 1, 2, 3, 3, 3, 2, 1, 0, 1, 3, 4, 4, 4, 3, 2, 1, 0, 1, 3, 6, 5, 5, 4, 3, 2, 1, 0, 1, 4, 7, 8, 6, 6, 4, 3, 2, 1, 0, 1, 4, 9, 10, 9, 7, 6, 4, 3, 2, 1, 0, 1, 6, 10, 14, 12, 10, 8, 6, 4, 3, 2, 1, 0, 1

Offset: 0

Gus Wiseman, May 15 2022

			Triangle begins:
  1
  0  1
  1  0  1
  1  1  0  1
  1  2  1  0  1
  1  2  2  1  0  1
  2  2  3  2  1  0  1
  2  3  3  3  2  1  0  1
  3  4  4  4  3  2  1  0  1
  3  6  5  5  4  3  2  1  0  1
  4  7  8  6  6  4  3  2  1  0  1
  4  9 10  9  7  6  4  3  2  1  0  1
  6 10 14 12 10  8  6  4  3  2  1  0  1
  6 13 16 17 13 11  8  6  4  3  2  1  0  1
  8 15 21 21 19 14 12  8  6  4  3  2  1  0  1
  9 19 24 28 24 20 15 12  8  6  4  3  2  1  0  1
For example, row n = 9 counts the following partitions (empty column indicated by dot):
  9   72   522   3222   22221  222111  2211111  21111111  .  111111111
  54  81   621   4221   32211  321111  3111111
  63  333  711   5211   42111  411111
      432  3321  6111   51111
      441  4311  33111
      531

MathOverflow, Why 'excedances' of permutations? [closed].

Row sums are A000041.
Column k = 0 is A003106.
The strong version is A114088.
The opposite version is A115720/A115994, rank statistic A257990.
The version for permutations is A123125, strong A173018.
The version for compositions is A352522, rank statistic A352515.
The strong opposite version is A353318.
A000700 counts self-conjugate partitions, ranked by A088902.
A001522 counts partitions with a fixed point, ranked by A352827 (unproved).
A008292 is the triangle of Eulerian numbers.
A064428 counts partitions w/o a fixed point, ranked by A352826 (unproved).
A238352 counts reversed partitions by fixed points, rank statistic A352822.
A352490 gives the nonexcedance set of A122111, counted by A000701.
Cf. A002620, A006918, A008290, A008930, A098825, A219282, A238874, A300788, A353319.

pgeq[y_]:=Length[Select[Range[Length[y]],#>=y[[#]]&]];
Table[Length[Select[IntegerPartitions[n],pgeq[#]==k&]],{n,0,15},{k,0,n}]

A371995 Triangle read by rows: T(n, k) = binomial(n - k, k) * subfactorial(k), for n >= 0 and 0 <= k <= floor(n/2).

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 3, 1, 0, 6, 2, 1, 0, 10, 8, 1, 0, 15, 20, 9, 1, 0, 21, 40, 45, 1, 0, 28, 70, 135, 44, 1, 0, 36, 112, 315, 264, 1, 0, 45, 168, 630, 924, 265, 1, 0, 55, 240, 1134, 2464, 1855, 1, 0, 66, 330, 1890, 5544, 7420, 1854, 1, 0, 78, 440, 2970, 11088, 22260, 14832

Offset: 0

Peter Luschny, Apr 24 2024

			Triangle starts:
  [0] 1;
  [1] 1;
  [2] 1, 0;
  [3] 1, 0;
  [4] 1, 0,  1;
  [5] 1, 0,  3;
  [6] 1, 0,  6,  2;
  [7] 1, 0, 10,  8;
  [8] 1, 0, 15, 20,  9;
  [9] 1, 0, 21, 40, 45;

Cf. A000166, A011973, A098825, A372102 (row sums), A371998 (main diagonal).

T[n_, k_] := Binomial[n - k, k] * Subfactorial[k];
Table[T[n, k], {n, 0, 9}, {k, 0, n/2}] // MatrixForm

T(n, k) = A011973(n, k) * A000166(k).

The rows are the antidiagonals of A098825.

cp's OEIS Frontend

A351983 Number of integer compositions of n with exactly one part above the diagonal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A372102 Number of permutations of [n] whose non-fixed points are not neighbors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A281262 Number of permutations of [2n] with exactly n fixed points.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A352875 Number of integer compositions y of n with a fixed point y(i) = i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A373417 Triangle T(n,k) for the number of permutations in symmetric group S_n with (n-k) fixed points and an even number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k<=n that contain an even number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A353315 Triangle read by rows where T(n,k) is the number of integer partitions of n with k parts on or below the diagonal (weak non-excedances).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A371995 Triangle read by rows: T(n, k) = binomial(n - k, k) * subfactorial(k), for n >= 0 and 0 <= k <= floor(n/2).

Views

Author