Talk:Rencontres numbers

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

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

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.

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

• 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.

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

• 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

3.table

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.

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

• 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.

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

• 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]]

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

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:

• 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

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

$X_{i}={\begin{cases}1&{\text{if }}i{\text{ is a fixed point}},\\0&{\text{otherwise}}.\end{cases}}$

Then the number of fixed points is

$X_{1}+\cdots +X_{n},\,$

so the expected number of fixed points is

$E(X_{1})+\cdots +E(X_{n})={\frac {1}{n}}+\cdots +{\frac {1}{n}}=1.$

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

$E(\sum _{i=1}^{n}X_{i})=\sum _{i=1}^{n}E(X_{i})$

(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)

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

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:

$_{n}\!\!\diagdown \!\!^{k}$	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.

$_{n}\!\!\diagdown \!\!^{k}$	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

• 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)