Talk:Rencontres numbers
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||
|
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
- A113899 >>[9]
- A129352 >> [10]
- A129536 >> [11]
- 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.
- copy:[[13]]
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)
- 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)
- 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)
- Well, I certainly prefer your equation mark-up.
- 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)
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)
- 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)
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)
- Replace approximation by lim specifying range of validity. — Preceding unsigned comment added by 80.219.149.220 (talk) 22:18, 5 March 2012 (UTC)