Yπολογισμός δυνατών πινάκων

[iliaplio]

Καλησπέρα και πάλι...χρειάζομαι τη βοήθειά σας...Πρέπει να υπολογίσω πόσοι 4χ4 πίνακεσ με στοιχεία 0 και 1 μπορούν να κατασκευαστούν και Πόσοι είναι προσκείμενοι και πόσοι είναι προσαρτημένοι απο αυτούς.
για το 1ο σκέλος μετά από κάποιες δοκιμές σε 2χ2 και 3χ3 πίνακες βρήκα πως αν έχοθμε έναν πίνακα nxn τοτε οι δυνατοί πίνακες που μπορούμε να κατασκευάσουμε είναι : n εισ την nxn.Δηλαδή για τον 4χ4 :4 εισ την 16η.Είναι σωστό αυτό? Αν ναι πως μπορώ να αποδείξω ποσοι είναι προσκείμενοι και ποσοι παρακείμενοι?Υπάρχει κάποιος τύπος?Εψαξα και σε ελληνικές και σε αγγλικές βιβλιογραφιες στο google και δεν βρήκα κάτι αντίστοιχο.Ευχαριστώ εκ των προτέρων!

[macJohn]

Νομίζω πως στη γενική περίπτωση είναι $$2^{(n \cdot n)}$$.

Αφού μπορείς να γεμίσεις τον πίνακα μόνο με 0 και 1.

[iliaplio]

χμμ οσο αναφορά το 2ο ερώτημα?καμια ιδέα?

[Stokos]

=> Κάθε πίνακας έχει 16 στοιχεία, καθένα από τα οποία μπορεί να πάρει 2 δυνατές τιμές άρα έχουμε 2^16 συνδυασμούς.

=> "Ο προσαρτημένος πίνακας ενός γραφήματος έχει ακριβώς δύο 1 σε κάθε στήλη και δεν υπάρχουν δύο ίδιες στήλες." [Source]
Οι δυνατές στήλες με ακριβώς δύο 1 για 4χ4 πίνακα είναι:
1100 (α)
1010 (β)
1001 (γ)
0110 (δ)
0101 (ε)
0011 (ζ)

(Γράφω τις στήλες οριζόντια για ευκολία)

Για να απαντήσεις στο ερώτημα πόσοι πίνακες είναι δυνατόν να είναι incidence αρκεί να βρεις πόσες 4γράμματες "λέξεις" μπορείς να κατασκευάσεις με τα (α,β,...,ζ) (π.χ. αβγδ, αεδγ, βζγδ, ...). Πρόσεξε όμως! Δε μπορείς να πεις 4 γράμματα με 6 δυνατές τιμές άρα 4^6, γιατί απαγορεύεται να έχεις 2 φορές το ίδιο γράμμα...

Οι δυνατοί συνδυασμοί είναι 6! = 720

"Μπακάλικη" Απόδειξη:
* Με 2 γράμματα έχεις 2 συνδυασμούς (αβ,βα)
* Με 3 γράμματα, κρατάς "σταθερό" το πρώτο γράμμα και έχεις 2 συνδυασμούς με τα υπόλοιπα: (αβγ, αγβ και βαγ, βγα και γαβ, γβα) δηλ. 3*2 = 6 = 3!
* Με 4 γράμματα, ομοίως κρατώντας "σταθερό" το πρώτο γράμμα έχεις 3! συνδυασμούς με τα υπόλοιπα, άρα συνολικά: 4*3! = 12 = 4!
και κατ'επέκταση...
* Με ν γράμματα έχεις ν*(ν-1)! = ν! πιθανούς συνδυασμούς.

[iliaplio]

οο...σε ευχαριστω πολυ stokos ακριβως οτι ζητουσα

[Stathmarxis]

Οι δυνατές στήλες με ακριβώς δύο 1 για 4χ4 πίνακα είναι:
1100 (α)
1010 (β)
1001 (γ)
0110 (δ)
0101 (ε)
0011 (ζ)

Είναι οι συνδυασμοί 4 στοιχείων ανά 2 ομοίων(δύο 2άδες στοιχείων), που είναι 4!/(2!2!)=6

Για να απαντήσεις στο ερώτημα πόσοι πίνακες είναι δυνατόν να είναι incidence αρκεί να βρεις πόσες 4γράμματες "λέξεις" μπορείς να κατασκευάσεις με τα (α,β,...,ζ) (π.χ. αβγδ, αεδγ, βζγδ, ...). Πρόσεξε όμως! Δε μπορείς να πεις 4 γράμματα με 6 δυνατές τιμές άρα 4^6, γιατί απαγορεύεται να έχεις 2 φορές το ίδιο γράμμα...
Οι δυνατοί συνδυασμοί είναι 6!

Εδώ θα διαφωνήσω ελαφρώς.. με το σκεπτικό σου έβαλες τις 6 στήλες στη σειρά, με 720 θα συμφωνήσω συνδυασμούς. Όμως, για κάθε συνδυασμό κρατάμε μόνο τις 4 πρώτες του στήλες. Συνεπώς, μετράμε τον κάθε συνδυασμό 2 φορές (π.χ. μία το αβγδεζ και μία το αβγδζε) οπότε πρέπει να μας βγούνε οι μισές (320 ή μάλλον 6!/2!)

Η σωστή απάντηση θα είναι οι συνδυασμοί των 6 στοιχείων ανά 4 [=6!/(4!2!)] -που δίνουνε τις 4-άδες στοιχείων που θα είναι εντός του πίνακα- επί τους συνδυασμούς των 4 αυτών στοιχείων μεταξύ τους (ανά ένα), δηλαδή 4!.
Το γινόμενο είναι 6!/2! δηλαδή οι μισοί..

[Stokos]

Οι δυνατές στήλες με ακριβώς δύο 1 για 4χ4 πίνακα είναι:
1100 (α)
1010 (β)
1001 (γ)
0110 (δ)
0101 (ε)
0011 (ζ)

Είναι οι συνδυασμοί 4 στοιχείων ανά 2 ομοίων(δύο 2άδες στοιχείων), που είναι 4!/(2!2!)=6

Για να απαντήσεις στο ερώτημα πόσοι πίνακες είναι δυνατόν να είναι incidence αρκεί να βρεις πόσες 4γράμματες "λέξεις" μπορείς να κατασκευάσεις με τα (α,β,...,ζ) (π.χ. αβγδ, αεδγ, βζγδ, ...). Πρόσεξε όμως! Δε μπορείς να πεις 4 γράμματα με 6 δυνατές τιμές άρα 4^6, γιατί απαγορεύεται να έχεις 2 φορές το ίδιο γράμμα...
Οι δυνατοί συνδυασμοί είναι 6!

Εδώ θα διαφωνήσω ελαφρώς.. με το σκεπτικό σου έβαλες τις 6 στήλες στη σειρά, με 720 θα συμφωνήσω συνδυασμούς. Όμως, για κάθε συνδυασμό κρατάμε μόνο τις 4 πρώτες του στήλες. Συνεπώς, μετράμε τον κάθε συνδυασμό 2 φορές (π.χ. μία το αβγδεζ και μία το αβγδζε) οπότε πρέπει να μας βγούνε οι μισές (320 ή μάλλον 6!/2!)

Η σωστή απάντηση θα είναι οι συνδυασμοί των 6 στοιχείων ανά 4 [=6!/(4!2!)] -που δίνουνε τις 4-άδες στοιχείων που θα είναι εντός του πίνακα- επί τους συνδυασμούς των 4 αυτών στοιχείων μεταξύ τους (ανά ένα), δηλαδή 4!.
Το γινόμενο είναι 6!/2! δηλαδή οι μισοί..

Ναι έχεις δίκιο, αν και έγραψα ότι πρέπει να βρούμε όλες τις δυνατές 4γράμματες "λέξεις", το ξέχασα στη πορεία...