Szerkesztő:Zlajos~huwiki/Ismétlés nélküli permutációk és ismétléses permutációk fixpontjai

Mielőtt én, vagy inkább egy igazán profi wikipédiás matematikus hozzáfogna ennek a szócikknek a megírásához, összegyüjtök ide néhány, a szócikknek legalábbis perifériájára eső dokumentumot, melyet kérek itthagyni!

A szócikket, esetleg másikat is, ezeknek a táblázatoknak a felhasználásával kívánom majd elkezdeni, de a formátum a nagy munkával történő táblázatszerkesztést nem teszi lehetővé úgy elmenteni, hogy a Wikipédián kívül is formálgathassam táblázataimat(még nem értek hozzá).

Majd lecserélem az angol nyelvű (általam bizonyára rosszul fordított) saját elnevezéseket (vissza) magyarra, (pl. Pascal-háromszög tükrözése és a megfeleltetett számok (centrális tükrözéssel) szorzata, stb.

START Zlajos 17 jun 2007

1.RÉSZSzerkesztés

Ha minden karakterből egy van:0(semmi) A, AB, ABC, ABCD, ABCDE, ......

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

Ismétlés nélküli permutációk fixpontjaiSzerkesztés

Nulla fixpontSzerkesztés

KÉT HÉTKÖZNAPI MEGFOGALMAZÁS:

  • 1.Valaki n darab levelet ír, és n darab borítékra felírja a levelekhez tartozó címeket. Hányféleképpen teheti a leveleket a borítékokba, hogy egyetlenegy se kerüljön a megfelelő címzésűbe? (POLYGON KÖNYVTÁR, Hajnal P.: Elemi kombinatorikai feladatok)
  • 2. Sportmérkőzésen örömében mindenki feldobja a kalapját. Hányféleképpen lehetséges, hogy senki nem a saját kalapját kapja ezután el? Forrás: (Ronald L. Graham, Donald E. Knuth, Oren Patashnik:KONKRÉT MATEMATIKA (1998),192-193 oldal) kulcsszavak: szétszóródó permutáció

ELVONTABBAN:

  • Legyen ABCD karakter összes permutációja. Hány olyan permutáció van, ahol a négy karakter közül egyik sincs a "helyén" :
BADC, BCDA, BDAC,
CADB, CDAB, CDBA,
DABC, DCAB, DCBA,

ez 9 db derangement, "zűrzavar" azaz 9 db fixpont nélküli permutáció!

Az 1. táblázat első oszlopában a karakterek, (sapkák, borítékok...) száma szerepel, nevezetesen, hogy mindegyikből 1 db van. A második oszlop tartalmazza a fixpont nélküli permutációk számát: 4 karakter, 1 1 1 1 db esetén tehát kilenc!

1.táblázatSzerkesztés

karakterek száma\fixpontok száma: nulla fixpont,"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

Rencontres numbersSzerkesztés

Az 1.táblázat -ról az angol wikin:

In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, ..., n } with specified numbers of fixed points. (Rencontre is French for encounter. By some accounts, the problem is named after a solitaire game.) For n ≥ 0 and 0 ≤ kn, the rencontres number Dnk is the number of permutations of { 1, ..., n } that have exactly k fixed points. See Riordan, pages 57-58 on the "problème des rencontres" and the table on page 65.

Here is the beginning of this array:

The numbers in the leftmost vertical column enumerate derangements. Thus

for non-negative n. It turns out that

where the ratio is rounded up for even n and and rounded down for odd n. For n ≥ 1, this gives the nearest integer. More generally, we have

The proof is easy after one knows how to enumerate derangements: choose the k fixed points out of n; then choose the derangement of the other n − k points.

értékek...Szerkesztés

A008290 formatted as a triangular array:[2] egyenlő ezzel a táblázattal! http://en.wikipedia.org/wiki/Cycles_and_fixed_points

  k  j 
0123456789sum
101 1
2101 2
32301 6
498601 24
54445201001 120
6265264135401501 720
718541855924315702101 5040
81483314832742024646301122801 40320
91334961334976674422260554411341683601362880
 0123456789sum

SzubfaktoriálisSzerkesztés

The subfactorial function, written as !n, is used to calculate the number of permutations of a set of n objects in which none of the elements occur in their natural place. These are also known as derangements. (The factorial function itself calculates the total number of permutations of the set.)

In practical terms, subfactorial is the number of ways of putting n letters into n envelopes (one in each envelope) with none in its correct envelope.

It can be calculated using the inclusion-exclusion principle.

Subfactorials can also be calculated in the following ways:

where denotes the incomplete gamma function, and e is the mathematical constant; or

where [x] denotes the nearest integer function.

with and (A000255 sorozat az OEIS-ben)

The first few values of the function are:

!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
!7 = 1854
!8 = 14833
!9 = 133496
!10 = 1334961
!11 = 14684570
!12 = 176214841
!13 = 2290792932
!14 = 32071101049
!15 = 481066515734
!16 = 7697064251745
!17 = 130850092279664
!18 = 2355301661033953
!19 = 44750731559645106
!20 = 895014631192902121
!21 = 18795307255050944540

The number 148,349 has the surprising property that it is equal to the sum of the subfactorials of its digits:

Subfactorial is sometimes permitted in the Four fours mathematical game where !4 being 9 is helpful.

Valószínűségi (gyakorisági) eloszlásSzerkesztés

The sum of the entries in each row is the whole number of permutations of { 1, ..., n }, and is therefore n!. If one divides all the entries in the nth row by n!, one gets the probability distribution of the number of fixed points of a uniformly distributed random permutation of { 1, ..., n }. The probability that the number of fixed points is k is

For in, the ith moment of this probability distribution is the i th Bell szám, i.e., the number of partitions of a set of size i. This is the same as the ith moment of a Poisson eloszlás with expected value 1. For i > n, the ith moment is smaller than that of that Poisson distribution.

Limiting probability distributionSzerkesztés

Határ valószínűségi eloszlásSzerkesztés

As the size of the permuted set grows, we get

This is just the probability that a Poisson-distributed random variable with expected value 1 is equal to k. In other words, as n grows, the probability distribution of the number of fixed points of a random permutation of a set of size n approaches the Poisson distribution with expected value 1.

IrodalomSzerkesztés

  • Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958

Külső hivatkozásSzerkesztés

Ismétléses permutáció fixpontjaiSzerkesztés

  • Ha minden karakterből kettő van: AABBCCDD.....
  • A059056 Penrice Christmas gift numbers, Card-matching numbers (Dinner-Diner matching numbers). [[3]]

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.táblázatSzerkesztés

fixpont\ karakterek száma: free vagy "0" fixpont 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

2.táblázat magyarázataSzerkesztés

Az eredeti vagy klasszikus táblázat : (1.táblázat)

  • "0" (táblázatban jele: "0")akkor 1 db 0 fixpont,
  • "A" (táblázatban jele: 1)akkor 0 db 0 fixpont,
  • "AB" (táblázatban jele: 11)akkor 1 db 0 fixpont,
  • "ABC" (táblázatban jele: 111)akkor 2 db 0 fixpont,,
  • "ABCD" (táblázatban jele: 1111) akkor 9 db 0 fixpont,, stb.

oszlop > nulla fixpont, "0" :

  • 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.
  • akkor:
  • hasonlóan : (2.táblázat)
  • "0" (table jele: "0") akkor 1 db 0 fixpont,
  • AA (table jele: 2) akkor 0 db 0 fixpont,
  • AABB (table jele: 22)akkor 1 db 0 fixpont,
  • AABBCC (table jele: 222)akkor 10 db 0 fixpont,
  • AABBCCDD (table jele: 2222)akkor 297 db 0 fixpont, stb.
  • oszlop > free vagy "0" fixpont :
  • 1, 0, 1, 10, 297, 13756, 925705, 85394646,...
  • A059072 Penrice Christmas gift numbers; card-matching numbers; dinner-diner matching numbers.

[[4]]

  • A059072

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

  • A059072
  • 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.táblázatSzerkesztés

Ismétléses permutáció fixpontjai Ha minden karakterből három van: AAABBBCCCDDD.....

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 :
    • 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.
  • column > free or 0 :
    • 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) [[5]]

  • 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. [[6]]

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

111 :3

222 :24

333 :216

444 :1824

555 :15150

etc... A000279 Card matching. [[7]] 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. [[8]]

  • 5.column ( "3" fixed point)

111 :1

222 :16

333 :435

444 :7136

555 :99350

etc... A000489 Card matching. [[9]]

  • 3.table
    • column: 2,3,4,5,...
    • where is it :formula or generating function(?)
    • where is it :bibliography?


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.

Zlajos 21. jun. 2007. Extension: If all character twice : example: AABBCC, which has 2 A, 2 B's, and 2 C's, is

Compare the all distinct anagram for AABBCC to CCBBAA (90) one after the other :template (or schema)

AAAAAA or 6 0 0 equal, (identical): BBBBBB and CCCCCC

AAAAAB or 5 1 0 equal, (identical): BBBBBC and CCCCCA etc.

AAAABB or 4 2 0 equal, (identical): AAAACC and BBBBAA etc.

AAAABC or 4 1 1 equal, (identical): CCCCAB and BBBBAC etc.

AAABBB or 3 3 0 equal, (identical): AAACCC and BBBCCC etc.

AABBCC or 2 2 2

AAABBC or 3 2 1 equal, (identical): BBBCCA and CCCAAB etc.

4.tableSzerkesztés

fixed point: character numbers: free or "0" 1 2 3 4 5 6 sum
6 0 0 or AAAAAA 0 0 90 0 0 0 0 90
5 1 0 or AAAAAB 0 30 30 30 0 0 0 90
4 2 0 or AAAABB 6 24 30 24 6 0 0 90
4 1 1 or AAAABC 6 24 36 12 12 0 0 90
3 3 0 or AAABBB 9 18 36 18 9 0 0 90
2 2 2 or AABBCC 10 24 27 16 12 0 1 90
3 2 1 or AAABBC 12 27 33 15 3 0 0 90


Extension: If all character thrice : example: AAABBBCCC, which has 3 A, 3 B's, and 3 C's, is

Compare the all distinct anagram for AAABBBCCC to CCCBBBAAA (1680) one after the other :template (or schema)

AAAAAAAAA or 9 0 0 equal, (identical): BBBBBBBBB and CCCCCCCCC

AAAAAAAAB or 8 1 0 equal, (identical): BBBBBBBBC and CCCCCCCCA etc.

AAAAAAABB or 7 2 0 equal, (identical): AAAAAAACC and BBBBBBBAA etc.

AAAAAAABC or 7 1 1 equal, (identical): CCCCCCCAB and BBBBBBBAC etc.

AAAAAABBB or 6 3 0 equal, (identical): AAAAAACCC and BBBBBBCCC etc.

AAAAAABBC or 6 2 1 equal, (identical): AAAAAACCB and BBBBBBCCA etc. .................... AAABBBCCC or 3 3 3 etc...

5.tableSzerkesztés

fixed point: character numbers: free or "0" 1 2 3 4 5 6 7 8 9 sum
9 0 0 or AAAAAAAAA 0 0 0 1680 0 0 0 0 0 0 1680
8 1 0 or AAAAAAAAB 0 0 560 560 560 0 0 0 0 0 1680
7 2 0 or AAAAAAABB 0 140 420 560 420 140 0 0 0 0 1680
7 1 1 or AAAAAAABC 0 140 420 630 280 210 0 0 0 0 1680
6 3 0 or AAAAAABBB 20 180 360 560 360 180 20 0 0 0 1680
6 2 1 or AAAAAABBC 20 180 420 480 380 140 60 0 0 0 1680
5 4 0 or AAAAABBBB 40 160 400 480 400 160 40 0 0 0 1680
5 3 1 or AAAAABBBC 40 190 400 460 360 160 60 10 0 0 1680
5 2 2 or AAAAABBCC 40 200 400 460 320 200 40 20 0 0 1680
4 4 1 or AAAABBBBC 48 192 384 480 320 192 48 16 0 0 1680
4 3 2 or AAAABBBCC 52 208 388 436 340 168 72 12 4 0 1680
3 3 3 or AAABBBCCC 56 216 378 435 324 189 54 27 0 1 1680


...4. table, 5.table sum: 90, 1680, etc.:A006480 De Bruijn's s(3,n): (3n)!/(n!)^3. [[11]]

continued! Zlajos 28. jun. 2007.

Compare the all distinct anagram for AAAAAABBBBBBB to BBBBBBAAAAAA (924) one after the other :template (or schema)

one after the other :template (or schema)

AAAAAAAAAAAA or 12 0

AAAAAAAAAAAB or 11 1

AAAAAAAAAABB or 10 2

....................

....................

BBBBBBBBBBAA or 2 10

....................

BBBBBBBBBBBB or 0 12

analogous or similar: A129352 [[12]]

MAPLE:with(combinat):T:=(n,i)->binomial(i,n)*binomial(12-i,6-n): for n from 0 to 6 do seq(T(n, i), i=0+n..12-6+n) od; #Warning, new definition for Chi

924, 462, 210, 84, 28, 7, 1

462, 504, 378, 224, 105, 36, 7

210, 378, 420, 350, 225, 105, 28

84, 224, 350, 400, 350, 224, 84

28, 105, 225, 350, 420, 378, 210

7, 36, 105, 224, 378, 504, 462

1, 7, 28, 84, 210, 462, 924

If this is table rotated right by Pi/4. then equal 6.table

6.tableSzerkesztés

fixed point: character numbers: "0" 1 2 3 4 5 6 7 8 9 10 11 12 sum
12 0 or AAAAAAAAAAAA 924 924
11 1 or AAAAAAAAAAAB 462 462 924
10 2 or AAAAAAAAAABB 210 504 210 924
9 3 or AAAAAAAAABBB 84 378 378 84 924
8 4 or AAAAAAAABBBB 28 224 420 224 28 924
7 5 or AAAAAAABBBBB 7 105 350 350 105 7 924
6 6 or AAAAAABBBBBB 1 36 225 400 225 36 1 924
5 7 or AAAAABBBBBBB 7 105 350 350 105 7 924
4 8 or AAAABBBBBBBB 28 224 420 224 28 924
3 9 or AAABBBBBBBBB 84 378 378 84 924
2 10 or AABBBBBBBBBB 210 504 210 924
1 11 or ABBBBBBBBBBB 462 462 924
0 12 or BBBBBBBBBBBB 924 924


Táblázat binomiális együtthatókkalSzerkesztés

fixed point: character numbers: "0" 1 2 3 4 5 6 7 8 9 10 11 12 sum
12 0 or AAAAAAAAAAAA C(0,0)*C(12,6) 924
11 1 or AAAAAAAAAAAB C(1,0)*C(11,6) C(1,1)*C(11,5) 924
10 2 or AAAAAAAAAABB C(2,0)*C(10,6) C(2,1)*C(10,5 C(2,2)*C(10,4) 924
9 3 or AAAAAAAAABBB C(3,0)*C(9,6) C(3,1)*C(9,5) C(3,2)*C(9,4) C(3,3)*C(9,3) 924
8 4 or AAAAAAAABBBB C(4,0)*C(8,6) C(4,1)*C(8,5) C(4,2)*C(8,4) C(4,3)*C(8,3) C(4,4)*C(8,2) 924
7 5 or AAAAAAABBBBB C(5,0)*C(7,6) C(5,1)*C(7,5) C(5,2)*C(7,4) C(5,3)*C(7,3) C(5,4)*C(7,2) C(5,5)*C(7,1) 924
6 6 or AAAAAABBBBBB C(6,0)*C(6,6) C(6,1)*C(6,5) C(6,2)*C(6,4) C(6,3)*C(6,3) C(6,4)*C(6,2) C(6,5)*C(6,1) C(6,6)*C(6,0) 924
5 7 or AAAAABBBBBBB C(7,1)*C(5,5) C(7,2)*C(5,4) C(7,3)*C(5,3) C(7,4)*C(5,2) C(7,5)*C(5,1) C(7,6)*C(5,0) 924
4 8 or AAAABBBBBBBB C(8,2)*C(4,4) C(8,3)*C(4,3) C(8,4)*C(4,2) C(8,5)*C(4,1) C(8,6)*C(4,0) 924
3 9 or AAABBBBBBBBB C(9,3)*C(3,3) C(9,4)*C(3,2) C(9,5)*C(3,1) C(9,6)*C(3,0) 924
2 10 or AABBBBBBBBBB C(10,4)*C(2,2) C(10,5)*C(2,1) C(10,6)*C(2,0) 924
1 11 or ABBBBBBBBBBB C(11,5)*C(1,1) C(11,6)*C(1,0) 924
0 12 or BBBBBBBBBBBB C(12,6)*C(0,0) 924

8.tableSzerkesztés

Pascal-háromszög része

fixpont: karakterek száma: "0" 1 2 3 4 5 6 7 8 9 10 11 12
............................ C(0,0)*
C(1,0)* C(1,1)*
C(2,0)* C(2,1)* C(2,2)*
C(3,0)* C(3,1)* C(3,2)* C(3,3)*
C(4,0)* C(4,1)* C(4,2)* C(4,3)* C(4,4)*
C(5,0)* C(5,1)* C(5,2)* C(5,3)* C(5,4)* C(5,5)*
C(6,0)* C(6,1)* C(6,2)* C(6,3)*

center

C(6,4)* C(6,5)* C(6,6)* ..................

Pascal-háromszög tükrözése (minta)Szerkesztés

9.tableSzerkesztés

............................. *C(6,6) *C(6,5) *C(6,4) *C(6,3)

center

*C(6,2) *C(6,1) *C(6,0) .................
. *C(5,5) *C(5,4) *C(5,3) *C(5,2) *C(5,1) *C(5,0)
. *C(4,4) *C(4,3) *C(4,2) *C(4,1) *C(4,0)
. *C(3,3) *C(3,2) *C(3,1) *'C(3,0)'
. *C(2,2) *C(2,1) *C(2,0)
. *C(1,1) *C(1,0)
. *C(0,0)

10.tableSzerkesztés

AAAAAABB katakterek permutációja AAAAAABB -tól BBAAAAAA -ig C(8,2) vagy C(8,6)= 28

(ez a "28" a Pascal-háromszög tükrözésének sorát jelöli ki.)

Hasonlítsuk össze ezeket sorra

AAAAAAAA 8 0

AAAAAAAB 7 1

AAAAAABB 6 2

AAAAABBB 5 3

...............

...............

ABBBBBBB 1 7

BBBBBBBB 0 8

mintákkal, és határozzuk meg a fixpontok számát!

Magyarázat nélkül:az elő sor esetén nyilvánvaló hogy 28 darab 6 fixpontos, az utolsó sor esetén 28 darab 2 fixpontos lesz.

Ime részletesen a táblázatban:

fixed point: character numbers: "0" 1 2 3 4 5 6 7 8 sum
8 0 or AAAAAAAA 28 28
7 1 or AAAAAAAB 21 7 28
6 2 or AAAAAABB 15 12 1 28
5 3 or AAAAABBB 10 15 3 28
4 4 or AAAABBBB 6 16 6 28
3 5 or AAABBBBB 3 15 10 28
2 6 or AABBBBBB 1 12 15 28
1 7 or ABBBBBBB 7 21 28
0 8 or BBBBBBBB 28 28

Ellenőrzés: a ferde sorok összege:

balról jobbra felfelé, (vagy átló):84 , azaz C(9,2) vagy C(9,7)

jobbról balra felfelé: (vagy átló):36 , azaz C(9,3) vagy C(9,6)

vízszintesen :28 , azaz C(8,2) vagy C(8,6)

A parallelogramma egyik oldala: A000217 Triangular numbers [[13]]

A háromszögszámok (1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91,...)első számjegyei. C(n,2)

A másik oldala:

A000579 Figurate numbers or binomial coefficients C(n,6).[[14]]

eleje.

11.tableSzerkesztés

Pascal háromszög

0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 sum
1* 1
.... 1* 1* 2
1* 2* 1* 4
1* 3* 3* 1 8
1* 4* 6* 4 1 16
1* 5* 10* 10 5 1 32
1* 6* 15* 20 15 6 1 64
1 7* 21* 35 35 21 7 1 128
1 8 28* 56 70 56 28 8 1 256

12.tableSzerkesztés

Pascal háromszög tükörképe

0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 sum
1 8 28 56 70 56 28* 8 1 256
1 7 21 35 35 21* 7* 1 128
11 6 15 20 15* 6* 1* 64
1 5 10 10* 5* 1* 32
1 4 6* 4* 1* 16
1 3* 3* 1* 8
1* 2* 1* 4
1* 1* 2
1* 1

13.tableSzerkesztés

Pascal háromszög és tükörképe: szorzás a szorzás centruma: a 11. oszlopban: (4*4)


0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 sum
1 8 28 56 70 56 28*1 8 1 256
1 7 21 35 35 21*1 7*1 1 128
11 6 15 20 15*1 6*2 1*1 64
1 5 10 10*1 5*3 1*3 32
1 4 6*1 4*4 1*6 16
1 3*1 3*5 1*10 8
1*1 2*6 1*15 4
1*7 1*21 2
1*28 1

2. PARTSzerkesztés

Maple list:

for n from 0 to 0 do seq(binomial(i,n)*binomial(2-i,0-n), i=0+n..2-0+n ); od;#

for n from 0 to 1 do seq(binomial(i,n)*binomial(2-i,1-n), i=0+n..1-0+n ); od;#

for n from 0 to 2 do seq(binomial(i,n)*binomial(4-i,2-n), i=0+n..4-2+n ); od;#

for n from 0 to 3 do seq(binomial(i,n)*binomial(6-i,3-n), i=0+n..6-3+n ); od;

for n from 0 to 4 do seq(binomial(i,n)*binomial(8-i,4-n), i=0+n..8-4+n ); od;

for n from 0 to 5 do seq(binomial(i,n)*binomial(10-i,5-n), i=0+n..10-5+n );od

for n from 0 to 6 do seq(binomial(i,n)*binomial(12-i,6-n), i=0+n..12-6+n ); od;#

for n from 0 to 7 do seq(binomial(i,n)*binomial(14-i,7-n), i=0+n..14-7+n ); od;#

for n from 0 to 8 do seq(binomial(i,n)*binomial(16-i,8-n), i=0+n..16-8+n ); od;#

for n from 0 to 9 do seq(binomial(i,n)*binomial(18-i,9-n), i=0+n..18-9+n ); od;#

for n from 0 to 10 do seq(binomial(i,n)*binomial(20-i,10-n), i=0+n..20-10+n ); od;#


To simplify table (simple table): for 1 to 8Szerkesztés

  • 0.

1, 1, 1

  • 1.

2, 1

1, 2

  • 2.

6, 3, 1

3, 4, 3

1, 3, 6

  • 3.

20, 10, 4, 1

10, 12, 9, 4

4, 9, 12, 10

1, 4, 10, 20

  • 4.

70, 35, 15, 5, 1

35, 40, 30, 16, 5

15, 30, 36, 30, 15

5, 16, 30, 40, 35

1, 5, 15, 35, 70

  • 5.

252, 126, 56, 21, 6, 1

126, 140, 105, 60, 25, 6

56, 105, 120, 100, 60, 21

21, 60, 100, 120, 105, 56

6, 25, 60, 105, 140, 126

1, 6, 21, 56, 126, 252

  • 6.

924, 462, 210, 84, 28, 7, 1

462, 504, 378, 224, 105, 36, 7

210, 378, 420, 350, 225, 105, 28

84, 224, 350, 400, 350, 224, 84

28, 105, 225, 350, 420, 378, 210

7, 36, 105, 224, 378, 504, 462

1, 7, 28, 84, 210, 462, 924

  • 7.

3432, 1716, 792, 330, 120, 36, 8, 1

1716, 1848, 1386, 840, 420, 168, 49, 8

792, 1386, 1512, 1260, 840, 441, 168, 36

330, 840, 1260, 1400, 1225, 840, 420, 120

120, 420, 840, 1225, 1400, 1260, 840, 330

36, 168, 441, 840, 1260, 1512, 1386, 792

8, 49, 168, 420, 840, 1386, 1848, 1716

1, 8, 36, 120, 330, 792, 1716, 3432

  • 8.

12870, 6435, 3003, 1287, 495, 165, 45, 9, 1

6435, 6864, 5148, 3168, 1650, 720, 252, 64, 9

3003, 5148, 5544, 4620, 3150, 1764, 784, 252, 45

1287, 3168, 4620, 5040, 4410, 3136, 1764, 720, 165

495, 1650, 3150, 4410, 4900, 4410, 3150, 1650, 495

165, 720, 1764, 3136, 4410, 5040, 4620, 3168, 1287

45, 252, 784, 1764, 3150, 4620, 5544, 5148, 3003

9, 64, 252, 720, 1650, 3168, 5148, 6864, 6435

1, 9, 45, 165, 495, 1287, 3003, 6435, 12870

etc...

3. PARTSzerkesztés

all 1.rows 1. numbers (and mirror)

1, 2, 6, 20, 70, 252, 924, 3432, 12870, etc...

Central binomial coefficients: C(2n,n) = (2n)!/(n!)^2.

A000984[[15]]


all 1.rows 2. numbers (and mirror)

1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, etc...

C(2n+1, n+1)

A001700 [[16]]


all 1.rows 3. numbers (and mirror)

1, 4, 15, 56, 210, 792, 3003, 11440, 43758, 167960, etc...

Binomial coefficients C(2n,n-1).

A001791 [[17]]


all 1.rows 4. numbers (and mirror)

1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, etc...

Binomial coefficient binomial(2n+1,n-1).

A002054 [[18]]


all 1.rows 5. numbers (and mirror)

1, 7, 36, 165, 715, 3003, 12376, 50388, 203490, 817190, etc...

Binomial coefficients C(2n+1,n-2).

A003516 [[19]]


all 1.rows 6. numbers (and mirror)

1, 7, 36, 165, 715, 3003, 12376, 50388, 203490, etc...

Binomial coefficients C(2n+1,n-2).

A003516[[20]]


all 1.rows 7. numbers (and mirror)

1, 8, 45, 220, 1001, 4368, 18564, 77520, 319770, etc...

Binomial coefficients C(2n,n-3).

A002696 [[21]]


all 2.rows 1. numbers (and mirror)equal all 1.rows 2. numbers

all 2.rows 2. numbers (and mirror)

2, 4, 12, 40, 140, 504, 1848, 6864, 25740, 97240, etc...

Twice central binomial coefficients

A028329[[22]]


all 2.rows 3. numbers (and mirror)

3, 9, 30, 105, 378, 1386, 5148, 19305, 72930, 277134, 1058148,etc...

3*C(2*n-1,n).

A003409 [[23]]


all 3.rows 3. numbers (and mirror)

6, 12, 36, 120, 420, 1512, 5544 etc...

A067804 formatted as a square array:3.rows [[24]]


all 4.rows 4. numbers (and mirror)

20, 40, 120, 400, 1400, 5040, etc...

A067804 formatted as a square array:4.rows [[25]]


all 5.rows 5. numbers (and mirror)

70, 140, 420, 1400, 4900,etc...

A067804 formatted as a square array:5.rows [[26]]


etc...

etc...


A067804 formatted as a square array:

1 2 6 20 70 252 924 3432 12870

2 4 12 40 140 504 1848 6864

6 12 36 120 420 1512 5544

20 40 120 400 1400 5040

70 140 420 1400 4900

252 504 1512 5040

924 1848 5544

3432 6864

12870

...................................................

all diagonal left to right and bottom to top

Square the entries of Pascal's triangle.

A008459 [[27]]

all 2.table "center" 1, 4, 36, 400, 4900, 63504, 853776, etc...

Binomial(2n,n)^2. 

A002894 [[28]]


Zlajos 2007. július 10., 17:29 (CEST)

A táblázat soraiban levő számok értelmezéseSzerkesztés

Kiindulás: Amennyiben "A" és "B" karakter összes permutációját, vagy "A" , "B" és "C" karakter, vagy "A" , "B", "C" és "D" karakter és így tovább permutációit készítjük el, azaz végtelen sok féle, de bármelyikből csk egy darab lehez, akkor a Subfactorial [29] és Derangement [30] illetve Rencontres numbers [31] fogalmak adnak eligazítást. Példák a permutációkra:

1.Szerkesztés

AB, BA

2.Szerkesztés

ABC, CAB
ACB, BCA
BAC, CBA

3.Szerkesztés

BADC, BCDA, BDAC,
CADB, CDAB, CDBA,
DABC, DCAB, DCBA,

1/2Szerkesztés

Az 1. permutációira analóg módon két karakter, mindegyikből kettő : (most számokkal bemutatva)minta: "1122"

2-2

2112, 1212

2121, 1221

2211, "1122"


Pirossal kiemelve:

0 fixpontos :2211 1 db

2 fixpontos : 2112, 1212, 2121, 1221 4 db

4 fixpontos :"1122" 1 db

Tehát : 1 4 1 (A Pascal háromszög) harmadik sorában lévő számok "'1' '2' '1' " négyzete, valójában itt most így értendő :

1= C(2,0)* C(2,2), 4= C(2,1)* C(2,1), 1=C(2,2)* C(2,0)

"Számszakilag" ugyanaz, de a szorzás mindíg a tükörképpel történik, mivel centrális tükrözés van, ez a kivétel: 4= C(2,1)* C(2,1)

1/3Szerkesztés

Az 1. permutációival analóg módon két karakter, mindegyikből három : (most számokkal bemutatva) minta: "111222" A generáló program miatt: fixpont egyenlő találat

0 találat: 1 db

1 találat: 0 db

2 találat: 9 db

3 találat: 0 db

4 találat: 9 db

5 találat: 0 db

6 találat: 1 db A permutációk

221112,
221121,
221211,
222111,
212112,
212121,
212211,
211212,
211221,
211122,
122112,
122121,
122211,
121212,
121221,
121122,
112212,
112221,
112122,
111222

0 fixpontos : 1 db 222111

2 fixpontos : 9 db 221121, 221112, 221211, 212112, 212211, 212121,122112, 122121, 122211

4 fixpontos : 9 db '211212', '211221','211122', '121212', '121221', '121122', '112212',, '112221', '112122'

6 fixpontos : 1 db 111222


"1 9 0 9 0 1" számok (a 0 itt nem számot jelöl, hanem a "nincs"-et, tehát semmi ) a Pascal háromszög "1 3 3 1 " sorának négyzete, azaz az alábbi szorzatokkal írható le:

1=C(3,0)*C(3,3),

9=C(3,1)*C(3,2),

9=C(3,2)*C(3,1),

1=C(3)3*C(3,0),

1/4Szerkesztés

z 1. permutációival analóg módon két karakter, mindegyikből négy : (most számokkal bemutatva) minta: "11112222" A fixpontot korábban bemutatva, itt már a permutációk és a találatok, majd a képlet magyarázata következik:

22211112 22211121 22211211 22212111

22221111 0 fixpont

22121112 22121121 22121211 22122111 22112112 22112121 22112211 22111212 22111221 22111122 21221112 21221121 21221211 21222111 21212112 21212121 21212211 21211212 21211221 21211122 21122112 21122121 21122211 21121212 21121221 21121122 21112212 21112221 21112122 21111222 12221112 12221121 12221211 12222111 12212112 12212121 12212211 12211212 12211221 12211122 12122112 12122121 12122211 12121212 12121221 12121122 12112212 12112221 12112122 12111222 11222112 11222121 11222211 11221212 11221221 11221122 11212212 11212221 11212122 11211222 11122212 11122221 11122122 11121222

11112222 8 fixpont

0 találat: 1 db
1 találat: 0 db (nincs!!!)
2 találat: 16 db
3 találat: 0 db (nincs!!!)
4 találat: 36 db
5 találat: 0 db (nincs!!!)
6 találat: 16 db
7 találat: 0 db (nincs!!!)
8 találat: 1 db

Ezek a találatok (fixpontok darabszáma) is a Pascal háromszög alábbi sorának négyzetét

1 4 6 4 1 azaz a következő szorzatot írják le:

1=C(4,0)*C(4,4)

16=C(4,1)*C(4,3)

36=C(4,2)*C(4,2)

16=C(4,3)*C(4,1)

1=C(4,4)*C(4,0)

2/a/3Szerkesztés

A 2. permutációira analóg módon három féle karakter (1,2,3), mindegyikből kettő darab:

(most számokkal bemutatva, de nincs rendezve!)

Jelölve (kövér) néhány 0 fixpontos permutációt (a tízből), ha a minta "112233"

321312, 321321, 321132, 321231, 321123, 321213, 323112, 323121, 322131, 322113, 323211, 322311, 312312, 312321, 312132, 312231, 312123, 312213, 332112, 332121, 332211, 313212, 313221, 311232, 311223, 331212, 331221, 313122, 311322, 331122, 231312, 231321, 231132, 231231, 231123, 231213, 233112, 233121, 232131 ,232113, 233211, 232311, 132312, 132321 132132, 132231, 132123, 132213, 133212, 133221, 131232, 131223, 133122 131322, 213312, 213321, 213132, 213231, 213123, 213213, 223131, 223113, 223311, 123312, 123321, 123132, 123231, 123123, 123213, 113232, 113223, 113322, 211332, 212331, 211323, 212313, 221331, 221313, 121332, 122331, 121323, 122313, 112332, 112323, 211233, 212133, 221133, 121233, 122133, "112233"

Az egyetlen, most 6 fixpontos az utolsó: "112233"

A többi fixpont száma (találat):


Találatok:

0 találat: 10 db
1 találat: 24 db
2 találat: 27 db
3 találat: 16 db
4 találat: 12 db
5 találat: 0 db
6 találat: 1 db

TÁBLÁZATSzerkesztés

A legfelső sor a találatok számát, mint fejléc mutatja.

A második sor az előző pontban bemutatott találati (fixpont) mennyiségeket mutatja!

222 222 ....0.....1.....2.....3.....4.....5......6.
222 222 ..10....24....27.....6.....12....0.....1
222 600 ...0.....0.....90.....0.......0....0.....0
222 510 ...0....30....30....30......0....0.....0
222 420 ...6....24....30....24......6....0.....0
222 411 ...6....24....36....12.....12....0.....0
222 330 ...9....18....36....18......9.....0....0
222 321 ...9....24....27....21......6.....3....0


1/6Szerkesztés

Hat darab "A" és hat darab "B" objektum (AAAAAABBBBBB), (karakter) összes permutációját vessük össze a kiindulási Hat darab "A" és hat darab "B" objektum (AAAAAABBBBBB)kiindulási mintájával és vizsgáljuk meg, hogy mennyi fixpontot kapunk!

Sorra nulla, egy, kettő, ... öt, tíz, tizenegy, és tizenkettő fixpont lehet. Ezeknek a darabszámát adja meg a táblázat:

6 6 vagy AAAAAABBBBBB sor :1 36 225 400 225 36 1 a fixpontok száma, ez összesen 924

Ha az összes permutációt összevetjük hasonlóképpen 12 db "A" karakterrel(AAAAAAAAAAAA), vagy 12 db "B" karakterrel (BBBBBBBBBBBB),akkor csak hat fixpont lehet a legfelső és legalsó táblázatsor szerint: 924 darab.

Értelemszerűen a táblázat további sorai is a fixpontok számát írják le.

"Fixpont" alatt az összehasonlítás során az azonos helyen megegyező karakter értendő!

lásd:

http://en.wikipedia.org/wiki/Rencontres_numbers

http://en.wikipedia.org/wiki/Cycles_and_fixed_points

http://en.wikipedia.org/wiki/Subfactorial Zlajos 2007. november 22., 15:23 (CEST) folytatom!!!


Meglett a magyar Variáció


Permutations with repetitionsSzerkesztés

When the order matters, and an object can be chosen more than once, the number of permutations is

 

where n is the number of objects from which you can choose and r is the number to be chosen.

For example, if you have the letters A, B, C, and D and you wish to discover the number of ways to arrange them in three letter patterns (trigrams)

  1. order matters (e.g., A-B is different from B-A, both are included as possibilities)
  2. an object can be chosen more than once (A-A possible)

you find that there are 43 or 64 ways. This is because for the first slot you can choose any of the four values, for the second slot you can choose any of the four, and for the final slot you can choose any of the four letters. Multiplying them together gives the total.

Egy példa (OEIS-ből) az ismétléses variáció (angol:of n-permutations of 8 objects:r,s,t,u,v,z,x,y with repetition) "fixpontjait" (angol:containing exactly five (5) u's.)leíró képletre és elrendezésre:

A140404 Binomial(n+5,5)*7^n.

1, 42, 1029, 19208, 302526, 4235364, 54353838, 652246056, 7419298887, 80787921214, 848273172747, 8636963213424, 85649885199788, 830145041167176, 7886377891088172, 73606193650156272, 676256904160810749 (list; graph; listen)

OFFSET

0,2

COMMENT

With a different offset, number of n-permutations of 8 objects:r,s,t,u,v,z,x,y with repetition allowed, containing exactly five (5) u's. Example: a(1)=42 because we have

uuuuur, uuuuru, uuuruu, uuruuu, uruuuu, ruuuuu

uuuuus, uuuusu, uuusuu, uusuuu, usuuuu, suuuuu,

uuuuut, uuuutu, uuutuu, uutuuu, utuuuu, tuuuuu,

uuuuuv, uuuuvu, uuuvuu, uuvuuu, uvuuuu, vuuuuu,

uuuuuz, uuuuzu, uuuzuu, uuzuuu, uzuuuu, zuuuuu,

uuuuux, uuuuxu, uuuxuu, uuxuuu, uxuuuu, xuuuuu,

uuuuuy, uuuuyu, uuuyuu, uuyuuu, uyuuuu, yuuuuu.

MAPLE

seq(binomial(n+5, 5)*7^n, n=0..17);

AUTHOR

Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 16 2008

tehát: ha öt pozíción kell öt u-t elhelyezni, az csak egyféleképpen lehetséges:uuuuu

A sorozat első tagja 1
A sorozat második tagja a fenti példából:(hat pozició) 42
A sorozat harmadik tagja 1029 (hét pozició) egy példa: uuuuuxx, és még 1028 eset...