Jump to content

Talk:Rencontres numbers

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

START Zlajos 17 jun 2007

Extension: If all character once : example: ABCDE......

  • A008290 Triangle T(n,k) of rencontres numbers (number of *permutations of n elements with k fixed points).[[1]]

1.table

[edit]
fixed point: character numbers: free or "0" 1 2 3 4 5 6 7 8 9 10 11 12
"0" 1
1 0 1
11 1 0 1
111 2 3 0 1
1111 9 8 6 0 1
11111 44 45 20 10 0 1
111111 265 264 135 40 15 0 1
1111111 1854 1855 924 315 70 21 0 1
  • If all character twice: example: AABBCC....
  • A059056 Penrice Christmas gift numbers, Card-matching numbers (Dinner-Diner matching numbers). [[2]]

COMMENT: Analogous to A008290. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 10 2005

1, 0, 0, 1, 1, 0, 4, 0, 1, 10, 24, 27, 16, 12, 0, 1, 297, 672, 736, 480, 246, 64, 24, 0, 1, 13756, 30480, 32365, 21760, 10300, 3568, 970, 160, 40, 0, 1, 925705, 2016480, 2116836, 1418720, 677655, 243360, 67920, 14688, 2655, 320, 60, 0, 1

2.table

[edit]
fixed point: character numbers: free or "0" 1 2 3 4 5 6 7 8 9 10 11 12
"0" 1
2 0 0 1
22 1 0 4 0 1
222 10 24 27 16 12 0 1
2222 297 672 736 480 246 64 24 0 1
22222 13756 30480 32365 21760 10300 3568 970 160 40 0 1
222222 925705 2016480 2116836 1418720 677655 243360 67920 14688 2655 320 60 0 1
2222222 85394646 183749160 191384599 128058000 61585776 22558928 6506955 1507392 284550 43848 5901 560 84

If original or classic table: (1.table)

  • "0" (table sign: "0")then 1 derangements,
  • "A" (table sign: 1)then 0 derangements,
  • "AB" (table sign: 11)then 1 derangements,
  • "ABC" (table sign: 111)then 2 derangements,
  • "ABCD" (table sign: 1111)then 9 derangements, etc.

column > free or 0 :

[edit]

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961...

[edit]
  • 00166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.[[00166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.]]

then:

  • analogous (2.table)
  • "0" (table sign: "0")then 1 derangements,
  • AA (table sign: 2)then 0 derangements,
  • AABB (table sign: 22)then 1 derangements,
  • AABBCC (table sign: 222)then 10 derangements,
  • AABBCCDD (table sign: 2222)then 297 derangements, etc.

column > free or 0 :

[edit]

1, 0, 1, 10, 297, 13756, 925705, 85394646,...

[edit]
  • A059072 Penrice Christmas gift numbers; card-matching numbers; dinner-diner matching numbers.[[3]]

FORMULA: MAPLE p := (x, k)->k!^2*sum(x^j/((k-j)!^2*j!), j=0..k); R := (x, n, k)->p(x, k)^n; f := (t, n, k)->sum(coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)!, j=0..n*k);seq(f(0, n, 2)/2!^n, n=0..18); (AUTHOR Barbara Haas Margolius (margolius(AT)math.csuohio.edu) )


  • COMMENT Number of fixed-point-free permutations of n distinct letters (ABCD...), each of which appears twice. If there is only one letter of each type we get A000166. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 15 2006


Question:

[edit]

2.table

[edit]

column: 2,3,4,5,...

[edit]

where is it :formula or generating function(?)

[edit]

where is it :bibliography?

[edit]

3.table

[edit]
fixed point: character numbers: free or "0" 1 2 3 4 5 6 7 8 9 10 11 12
"0" 1
3 0 0 0 1
33 1 0 9 0 9 0 1
333 56 216 378 435 324 189 54 27 0 1
3333 13833 49464 84510 90944 69039 38448 16476 5184 1431 216 54 0 1
33333 6699824 23123880 38358540 40563765 30573900 17399178 7723640 2729295 776520 180100 33372 5355 540
333333 5691917785 19180338840 31234760055 32659846104 24571261710 14125889160 6433608330 2375679240 722303568 182701480 38712600 6889320 1035330
3333333 7785547001784 25791442770240 etc

If original or classic table: (1.table)

  • "0" (table sign: "0")then 1 derangements,
  • "A" (table sign: 1)then 0 derangements,
  • "AB" (table sign: 11)then 1 derangements,
  • "ABC" (table sign: 111)then 2 derangements,
  • "ABCD" (table sign: 1111)then 9 derangements, etc.

column > free or 0 :

[edit]

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961...

[edit]
  • 00166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.[[00166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.]]

then:

  • analogous (3.table)
  • "0" (table sign: "0")then 1 derangements,
  • AAA (table sign: 3)then 0 derangements,
  • AAABBB (table sign: 33)then 1 derangements,
  • AAABBBCCC (table sign: 333)then 56 derangements,
  • AAABBBCCCDDD (table sign: 3333)then 13833 derangements, etc.

column > free or 0 :

[edit]

1, 0, 1, 56, 13833, 6699824, 5691917785, 7785547001784,

[edit]
  • A059073 Card-matching numbers (Dinner-Diner matching numbers).

FORMULA: MAPLE p := (x, k)->k!^2*sum(x^j/((k-j)!^2*j!), j=0..k); R := (x, n, k)->p(x, k)^n; f := (t, n, k)->sum(coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)!, j=0..n*k); seq(f(0, n, 3)/3!^n, n=0..18); (AUTHOR Barbara Haas Margolius (margolius(AT)math.csuohio.edu) [[4]]

  • Number of fixed-point-free permutations of n distinct letters (ABCD...), each of which appears thrice. If there is only one letter of each type we get A000166. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 15 2006


  • 2.column (free or "0" -fixed point

" " :1

111 :2

222 :10

333 :56

444 :346

555 :2252

etc... A000172 Franel number a(n) = Sum C(n,k)^3, k=0..n. [[5]]

  • 3.column ( "1" -fixed point)

111 :3

222 :24

333 :216

444 :1824

555 :15150

etc... A000279 Card matching. [[6]] COMMENT

Number of permutations of 3 distinct letters (ABC) each with n copies such that one (1) fixed points. E.g. if AAAAABBBBBCCCCC n=3*5 letters permutations then one fixed points n5=15150 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Feb 02 2006

  • 4.column ( "2" fixed point)

111 :0

222 :27

333 :378

444 :4536

555 :48600

etc... A000535 Card matching. [[7]]

  • 5.column ( "3" fixed point)

111 :1

222 :16

333 :435

444 :7136

555 :99350

etc... A000489 Card matching. [[8]]

3.table

[edit]

column: 2,3,4,5,...

[edit]

where is it :formula or generating function(?)

[edit]

where is it :bibliography?

[edit]

Number parallelogram based on Pascal's triangle (and special mirror of central and multiply of diagonal)

[edit]
OEIS
  1. A113899 >>[9]
  2. A129352 >> [10]
  3. A129536 >> [11]
  4. Demo>>...mirror of central and multiply of diagonal...[12] (Pascal háromszög tükrözése és szorzás. Minta.)

continued:

[edit]
  • charcters:quadruple, example:AAAA, AAAABBBB, AAAABBBBCCCC, AAAABBBBCCCCDDDD, etc...
  • table 1.column :4, 44, 444, 4444, 44444, etc...
  • charcters:quintuple, example:AAAAA, AAAAABBBBB, AAAAABBBBBCCCCC, etc...
  • table 1.column :5, 55, 555, 5555, 55555, etc...
  • a great number of connexion of interesting !!

Zlajos 19. jun. 2007.

Zlajos 28. jun. 2007. 16. apr. 2009.

Justification that expectation is 1

[edit]

To show that for n ≥ 1, the expected number of fixed points is 1 :
We'll number the permutations p = 1 to n!
Now let X[p,m]=1 if in the p_th permutation, element m is fixed,
when it is not fixed, X[p,m]=0
Now the expected number of fixed points
is E_n[F] = sum_p_from_1_to_n! { sum_m_from_1_to_n { X[p,m] } } / n!
=> E_n[F] = sum_m_from_1_to_n { sum_p_from_1_to_n! { X[p,m] } } / n!
=> E_n[F] = sum_m_from_1_to_n { (n-1)! } / n!
=> E_n[F] = n * (n-1)! / n!
=> E_n[F] = 1

(with thanks to FD) Pnelnik (talk) 08:42, 19 July 2009 (UTC)[reply]

Simpler argument: Let
Then the number of fixed points is
so the expected number of fixed points is
Michael Hardy (talk) 15:01, 19 July 2009 (UTC)[reply]
Well, I certainly prefer your equation mark-up.
I'd argue that the two proofs are almost almost identical.
The same arguement presented slightly differently.
(I'm now going to make the effort to write the equations properly)
You use the fact that
(eqn1)
Here the probability distribution is discrete, so taking the expectation is a sumation
So to prove eqn1, we just need to swap the order of summation.
In my version, I've just shown that explicitly
For any wikipedians wondering, I should point out that the work or particularly the results
are not original work. The results have probably been known for a couple of centuries.
Pnelnik (talk) 20:52, 19 July 2009 (UTC)[reply]
My version doesn't require knowing how many permutations a set has, given its cardinality. In that sense it is simpler. Michael Hardy (talk) 01:07, 20 July 2009 (UTC)[reply]

Table format

[edit]

On the article page the first table is not very pretty. There is no horizontal bar under number 2,3,4,5,6,7 and the verticle bar goes down too far:

0 1 2 3 4 5 6 7
0 1
1 0 1

Perhaps one solution would be to put in blanks in those extra cells.

0 1 2 3 4 5 6 7
0 1
1 0 1

It is not ideal, but I think it looks a bit better.
Pnelnik (talk) 23:23, 19 July 2009 (UTC)[reply]

I've now just noticed that the tables look fine using Opera and IE browsers.
The only problem is when they are viewed in Firefox (version 3.5.1)
Pnelnik (talk) 23:54, 19 July 2009 (UTC)[reply]

Formulae need clarification

[edit]
  • Explain meaning of symbol z.
 - This is the coefficient operator. Definition can be found at http://en.wikipedia.org/wiki/Formal_power_series#Extracting_coefficients  Heycarnut (talk) 08:37, 10 August 2013 (UTC)[reply]