A371761 -id:A371761 - cp's OEIS frontend

A136301 Frequency of occurrence for each possible "probability of derangement" for a Secret Santa drawing in which each person draws a name in sequence and the only person who does not draw someone else's name is the one who draws the final name.

1, 1, 1, 1, 5, 2, 1, 1, 13, 6, 13, 2, 6, 2, 1, 1, 29, 14, 73, 6, 42, 18, 29, 2, 18, 8, 14, 2, 6, 2, 1, 1, 61, 30, 301, 14, 186, 86, 301, 6, 102, 48, 186, 18, 102, 42, 61, 2, 42, 20, 86, 8, 48, 20, 30, 2, 18, 8, 14, 2, 6, 2, 1, 1, 125, 62, 1081, 30, 690, 330, 2069, 14, 414, 200, 1394

Offset: 3

Brian Parsonnet, Mar 22 2008

The sequence is best represented as a series of columns 1..n, where each column j has 2^(j-1) rows (see Example). For more details, see A136300.

The first column represents the case for 3 people (offset 3).

			Represented as a series of columns, where column j has 2^(j-1) rows, the sequence begins:
  row |j = 1   2   3   4   5 ...
  ----+-------------------------
    1 |    1   1   1   1   1 ...
    2 |        1   5  13  29 ...
    3 |        2   6  14  30 ...
    4 |        1  13  73 301 ...
    5 |            2   6  14 ...
    6 |            6  42 186 ...
    7 |            2  18  86 ...
    8 |            1  29 301 ...
    9 |                2   6 ...
   10 |               18 102 ...
   11 |                8  48 ...
   12 |               14 186 ...
   13 |                2  18 ...
   14 |                6 102 ...
   15 |                2  42 ...
   16 |                1  61 ...
   17 |                    2 ...
  ... |                  ... ...
.
If there are 5 people, numbered 1-5 according to the order in which they draw a name, and person #5 draws name #5, the first four people must draw 1-4 as a proper derangement, and there are 9 ways of doing so: 21435 / 23415 / 24135 / 31425 / 34125 / 34215 / 41235 / 43125 / 43215.
But the probability of each derangement depends on how many choices exist at each successive draw. The first person can draw from 4 possibilities (2,3,4,5). The second person nominally has 3 to choose from, unless the first person drew number 2, in which case person 2 may draw 4 possibilities (1,3,4,5), and so on. The probabilities of 21435 and 24135 are both then
        1/4 * 1/4 * 1/2 * 1/2 = 1/64.
More generally, if there are n people, at the i-th turn (i = 1..n), person i has either (n-i) or (n-i+1) choices, depending on whether the name of the person who is drawing has been chosen yet. A way to represent the two cases above is 01010, where a 0 indicates that the person's number is not yet drawn, and a 1 indicates it is.
For the n-th person to be forced to choose his or her own name, the last digit of this pattern must be 0, by definition. Similarly, the 1st digit must be a 0, and the second to last digit must be a 1. So all the problem patterns start with 0 and end with 10. For 5 people, that leaves 4 target patterns which cover all 9 derangements. By enumeration, that distribution can be shown to be (for the 3rd column = 5 person case):
        0-00-10 1 occurrences
        0-01-10 5 occurrences
        0-10-10 2 occurrences
        0-11-11 1 occurrences
1;
1, 1;
1, 5, 2, 1;
1, 13, 6, 13, 2, 6, 2, 1;
1, 29, 14, 73, 6, 42, 18, 29, 2, 18, 8, 14, 2, 6, 2, 1;

Brian Parsonnet, Table of n, a(n) for n = 3..257
Brian Parsonnet, Probability of Derangements

The application of this table towards final determination of the probabilities of derangements leads to sequence A136300, which is the sequence of numerators. The denominators are in A001044.
A048144 represents the peak value of all odd-numbers columns.
A000255 equals the sum of the bottom half of each column.
A000166 equals the sum of each column.
A047920 represents the frequency of replacements by person drawing at position n.
A008277, Triangle of Stirling numbers of 2nd kind, can be derived from A136301 through a series of transformations (see "Probability of Derangements.pdf").
Cf. A371761.

maxP = 15;
rows = Range[1, 2^(nP = maxP - 3)];
pasc = Table[
   Binomial[p + 1, i] - If[i >= p, 1, 0], {p, nP}, {i, 0, p}];
sFreq = Table[0, {maxP - 1}, {2^nP}]; sFreq[[2 ;; maxP - 1, 1]] = 1;
For[p = 1, p <= nP, p++,
  For[s = 1, s <= p, s++, rS = Range[2^(s - 1) + 1, 2^s];
        sFreq[[p + 2, rS]] = pasc[[p + 1 - s, 1 ;; p + 2 - s]] .
            sFreq[[s ;; p + 1, 1 ;; 2^(s - 1)]]]];
TableForm[ Transpose[ sFreq ] ]
(* Code snippet to illustrate the conjectured connection with A371761: *)
R[n_] := Table[Transpose[sFreq][[2^n]][[r]], {r, n + 1, maxP - 1}]
For[n = 0, n <= 6, n++, Print[n + 1, ": ", R[n]]] (* Peter Luschny, Apr 10 2024 *)

H(r,c) = Sum_{j=0..c-L(r)-1} H(T(r), L(r)+j) * M(c-T(r)-1, j) where M(y,z) = binomial distribution (y,z) when y - 1 > z and (y,z)-1 when y-1 <= z and T(r) = A053645 and L(r) = A000523.

Conjecture: Assume the table represented as in the Example section. Then row 2^n is row n + 1 of A371761. - Peter Luschny, Apr 10 2024

Edited by Brian Parsonnet, Mar 01 2011

A379821 Array read by ascending antidiagonals: A(n, k) = (-1)^(n + k) * Sum_{j=0..k} (j!)^2 * Stirling1(n, j) * Stirling1(k, j).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 2, 5, 2, 0, 0, 6, 14, 14, 6, 0, 0, 24, 50, 76, 50, 24, 0, 0, 120, 224, 360, 360, 224, 120, 0, 0, 720, 1216, 1908, 2392, 1908, 1216, 720, 0, 0, 5040, 7776, 11628, 15664, 15664, 11628, 7776, 5040, 0

Offset: 0

Peter Luschny, Jan 03 2025

			Array begins:
  [0] 1,   0,    0,     0,      0,       0,        0,        0, ...
  [1] 0,   1,    1,     2,      6,      24,      120,      720, ...
  [2] 0,   1,    5,    14,     50,     224,     1216,     7776, ...
  [3] 0,   2,   14,    76,    360,    1908,    11628,    81072, ...
  [4] 0,   6,   50,   360,   2392,   15664,   110336,   856080, ...
  [5] 0,  24,  224,  1908,  15664,  126676,  1046780,  9169920, ...
  [6] 0, 120, 1216, 11628, 110336, 1046780, 10057204, 99846144, ...
.
Triangle T(n, k) = A(n - k, k) starts:
  [0] 1;
  [1] 0,   0;
  [2] 0,   1,    0;
  [3] 0,   1,    1,    0;
  [4] 0,   2,    5,    2,    0;
  [5] 0,   6,   14,   14,    6,    0;
  [6] 0,  24,   50,   76,   50,   24,    0;
  [7] 0, 120,  224,  360,  360,  224,  120,   0;
  [8] 0, 720, 1216, 1908, 2392, 1908, 1216, 720, 0;

Main diagonal gives A382792.

The corresponding array with Stirling2 numbers is A371761.

A := (n, k) -> local j; (-1)^(n + k)*add((j!)^2*Stirling1(n, j)*Stirling1(k, j), j = 0..k):
seq(lprint(seq(A(n, k), k = 0..7)), n = 0..8);

a(n, k) = sum(j=0, min(n, k), j!^2*abs(stirling(n, j, 1)*stirling(k, j, 1))); \\ Seiichi Manyama, Apr 05 2025

E.g.f.: 1 / (1 - log(1-x) * log(1-y)). - Seiichi Manyama, Apr 05 2025

A344920 The Worpitzky transform of the squares.

Original entry on oeis.org

0, -1, 5, -13, 29, -61, 125, -253, 509, -1021, 2045, -4093, 8189, -16381, 32765, -65533, 131069, -262141, 524285, -1048573, 2097149, -4194301, 8388605, -16777213, 33554429, -67108861, 134217725, -268435453, 536870909, -1073741821, 2147483645, -4294967293

Offset: 0

Peter Luschny, Jun 24 2021

The Worpitzky transform maps a sequence A to a sequence B, where B(n) = Sum_{k=0..n} A163626(n, k)*A(k). (If A(n) = 1/(n + 1) then B(n) are the Bernoulli numbers (with B(1) = 1/2.))

Also row 2 in A371761. Can be generated by the signed Akiyama-Tanigawa algorithm for powers (see the Python script). - Peter Luschny, Apr 12 2024

Index entries for linear recurrences with constant coefficients, signature (-3,-2).

Up to shift and sign: even bisection A267921, odd bisection A141725.

Cf. A163626, A036563, A371761.

gf := (exp(x) - 1)*(exp(x) - 2)*exp(-2*x): ser := series(gf, x, 36):
seq(n!*coeff(ser, x, n), n = 0..31);

W[n_, k_] := (-1)^k k! StirlingS2[n + 1, k + 1];
WT[a_, len_] := Table[Sum[W[n, k] a[k], {k, 0, n}], {n, 0, len-1}];
WT[#^2 &, 32] (* The Worpitzky transform applied to the squares. *)

# Using the Akiyama-Tanigawa algorithm for powers from A371761.
print([(-1)**n * v for (n, v) in enumerate(ATPowList(2, 32))])
# Peter Luschny, Apr 12 2024

a(n) = n! * [x^n] (exp(x) - 1)*(exp(x) - 2)*exp(-2*x).
a(n) = (-1)^(n + 1)*(3 - 2^(n + 1)) for n >= 1. - Hugo Pfoertner, Jun 24 2021
a(n) = [x^n] x*(2*x - 1)/(2*x^2 + 3*x + 1). - Stefano Spezia, Jun 24 2021

A371764 Triangle read by rows: Trace of the Akiyama-Tanigawa algorithm for powers x^3.

Original entry on oeis.org

0, 1, 1, 13, 14, 8, 73, 86, 57, 27, 301, 374, 273, 148, 64, 1081, 1382, 1065, 628, 305, 125, 3613, 4694, 3729, 2308, 1205, 546, 216, 11593, 15206, 12297, 7828, 4265, 2058, 889, 343, 36301, 47894, 39153, 25348, 14165, 7098, 3241, 1352, 512

Offset: 0

Peter Luschny, Apr 15 2024

See the comments in A371763.

			Triangle starts:
0:                        0
1:                      1,  1
2:                   13,  14, 8
3:                 73, 86,  57, 27
4:             301, 374, 273, 148, 64
5:        1081, 1382, 1065, 628, 305, 125
6:     3613, 4694, 3729, 2308, 1205, 546, 216
7: 11593, 15206, 12297, 7828, 4265, 2058, 889, 343

Cf. A371761, A371763.

Cf. A006230 (left edge).

# Using function ATPtriangle from A371763.
ATPtriangle(3, 8)

# Using function ATPtriangle from A371763.
ATPtriangle(3, 9);
# Or, after Detlef Meya:
T := (n,k) -> (k+1)*(7-(k+2)*(3*2^(n-k+1)-(k+3)*3^(n-k)))-`if`(n=k,1,0):
seq(seq(T(n, k), k = 0..n), n = 0..8);  # Peter Luschny, Apr 21 2024

T[n_, k_] := If[n==k, n^3, 2*Binomial[k + 3, k]*3^(n - k + 1) - 6*Binomial[k + 2, k]*2^(n - k + 1) + 7*(k + 1)]; Flatten[Table[T[n, k],{n, 0, 8},{k, 0, n}]] (* Detlef Meya, Apr 21 2024 *)

Python
```
# See function ATPowList in A371761.
```

T(n, k) = n^3 if n=k, otherwise 2*binomial(k + 3, k)*3^(n - k + 1) - 6*binomial(k + 2, k)*2^(n - k + 1) + 7*(k + 1). - Detlef Meya, Apr 21 2024

A370966 a(n) = number of max-closed 2 X 2 X n relations.

Original entry on oeis.org

1, 14, 122, 898, 6086, 39394, 248102, 1536178, 9409046, 57227074, 346467782, 2091269458, 12597590006, 75785795554, 455516874662, 2736312874738, 16430733386966, 98635853704834, 592021022116742, 3552949991056018, 21320996155647926, 127939164097754914, 767687740219762022

Offset: 0

N. J. A. Sloane, Apr 04 2024

Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.14) and (19.16).
Filip Stappers, Problems concerning parades and poly-Bernoulli numbers, 2024. See Problem 10.
Index entries for linear recurrences with constant coefficients, signature (15,-80,180,-144).

Cf. A370967, A371761.

From Filip Stappers, Aug 19 2024: (Start)
a(n) = 35/6*6^n - 6*4^n + 2/3*3^n + 1/2*2^n.
G.f.: (1-z)*(1-8*z^2) / ((1-6*z)*(1-4*z)*(1-3*z)*(1-2*z)). (End)
E.g.f.: exp(2*x)*(3 + 4*exp(x) - 36*exp(2*x) + 35*exp(4*x)). - Stefano Spezia, Aug 20 2024

a(7)-a(9) from Michael S. Branicky, Apr 07 2024
a(10) from Michael S. Branicky, Apr 08 2024
a(11) from Michael S. Branicky, Apr 22 2024
More terms from Filip Stappers, Aug 14 2024
a(0)=1 prepended by Filip Stappers, Aug 19 2024

A371763 Triangle read by rows: Trace of the Akiyama-Tanigawa algorithm for powers x^2.

Original entry on oeis.org

0, 1, 1, 5, 6, 4, 13, 18, 15, 9, 29, 42, 39, 28, 16, 61, 90, 87, 68, 45, 25, 125, 186, 183, 148, 105, 66, 36, 253, 378, 375, 308, 225, 150, 91, 49, 509, 762, 759, 628, 465, 318, 203, 120, 64, 1021, 1530, 1527, 1268, 945, 654, 427, 264, 153, 81

Offset: 0

Peter Luschny, Apr 15 2024

The Akiyama-Tanigawa is a sequence-to-sequence transformation AT := A -> B. If A(n) = 1/(n + 1) then B(n) are the Bernoulli numbers. Tracing the algorithm generates a triangle where the right edge is sequence A and the left edge is its transform B.
Here we consider the sequence A(n) = n^2 that is transformed into sequence B(n) = |A344920(n)|. The case A(n) = n^3 is A371764. Sequence [1, 1, 1, ...] generates A023531 and sequence [0, 1, 2, 3, ...] generates A193738.
In their general form, the AT-transforms of the powers are closely related to the poly-Bernoulli numbers A099594 and generate the rows of the array A371761.

			Triangle starts:
0:                  0
1:               1,   1
2:             5,   6,   4
3:          13,  18,  15,   9
4:        29,  42,  39,  28,  16
5:      61,  90,  87,  68,  45,  25
6:    125, 186, 183, 148, 105,  66, 36
7:  253, 378, 375, 308, 225, 150, 91, 49

Family of triangles: A023531 (n=0), A193738 (n=1), this triangle (n=2), A371764 (n=3).

Cf. A371761, A344920, A099594.

function ATPtriangle(k::Int, len::Int)
    A = Vector{BigInt}(undef, len)
    B = Vector{Vector{BigInt}}(undef, len)
    for n in 0:len-1
        A[n+1] = n^k
        for j = n:-1:1
            A[j] = j * (A[j+1] - A[j])
        end
        B[n+1] = A[1:n+1]
    end
    return B
end
for (n, row) in enumerate(ATPtriangle(2, 9))
    println("$(n-1): ", row)
end

ATProw := proc(k, n) local m, j, A;
   for m from 0 by 1 to n do
      A[m] := m^k;
      for j from m by -1 to 1 do
         A[j - 1] := j * (A[j] - A[j - 1])
   od od; convert(A, list) end:
ATPtriangle := (p, len) -> local k;
     ListTools:-Flatten([seq(ATProw(p, k), k = 0..len)]):
ATPtriangle(2, 9);

T[n,k] := If[n==k, n^2, (k+1)*(2^(n-k)*(k+2)-3)]; Flatten[Table[T[n,k],{n,0,9},{k,0,n}]] (* Detlef Meya, Apr 19 2024 *)

Python
```
# See function ATPowList in A371761.
```

T(n, k) = n^2 if n=k, otherwise (k + 1)*(2^(n - k)*(k + 2) - 3). - Detlef Meya, Apr 19 2024

cp's OEIS Frontend

A136301 Frequency of occurrence for each possible "probability of derangement" for a Secret Santa drawing in which each person draws a name in sequence and the only person who does not draw someone else's name is the one who draws the final name.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A379821 Array read by ascending antidiagonals: A(n, k) = (-1)^(n + k) * Sum_{j=0..k} (j!)^2 * Stirling1(n, j) * Stirling1(k, j).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

PARI

Formula

A344920 The Worpitzky transform of the squares.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A371764 Triangle read by rows: Trace of the Akiyama-Tanigawa algorithm for powers x^3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Julia

Maple

Mathematica

Python

Formula

A370966 a(n) = number of max-closed 2 X 2 X n relations.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A371763 Triangle read by rows: Trace of the Akiyama-Tanigawa algorithm for powers x^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Julia

Maple

Mathematica

Python

Formula