For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
1answer
71 views

Combinatorics, dividing objects into groups.

Assuming we have got 5 horses, that are competing in a race, and assuming 2 different horses can arrive at the exact same time. How many possibilities there are for outcomes? for 3 horses for example ...
1
vote
1answer
28 views

Find the chance that subset $B$ is distributed evenly between $(A_1,A_2,A_3)$

We are given set $A$ which is divided to the 3 parts ($A_1$,$A_2$, $A_3$). $|A| = n = 9k$. For $i,j = 1,2,3;\space \forall i \ne j : A_i \cap A_j = \emptyset; \space\space |A_i| = \frac n 3$. ...
0
votes
1answer
33 views

How many ways can one “fit” $m$ non-overlapping sub-segments of length $k$ into a segment of length $n$?

Given discrete one-dimensional space (a "segment") of length $n$, how many ways can one fit a $m$ non-overlapping sub-segments of length $k$ in this space? This seems like a very simple question, but ...
4
votes
2answers
101 views

How many words can be written with $aabbbccdd$ such that no two equal letters are adjacent?

I'm trying to count this using the principle if inclusion-exclusion. I've done the following: Counting the number of permutations of $aabbbccdd$. $9!$ Counting the number of ...
1
vote
2answers
50 views

let $D_n$ be the number of permutations of $\{1,2,3,…n\}$ which leave no element fixed.

Let $n\geq2$ and let $D_n$ be the number of permutations of $\{1,2,3,\dots,n\}$ which leave no element fixed. How to write an expression for $D_n$ in terms of $D_k$? I don't know how to start. Please ...
1
vote
0answers
32 views

Derangement of multiset using recursive relation

Recently,I have read articles on derangement but now I want know about how to derange a multiset. By using inclusion-exclusion one can find out the number of ways to derange a multiset. I'm looking ...
1
vote
2answers
101 views

The Game of Chess

In how many ways can the first four moves (two from each side) be made in a game of chess? I've seen and solved one on the first two moves. Now I wonder what the answer will look like for the first ...
0
votes
0answers
26 views

Do these statements prove this formula?

$$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = g(x)^{f(x)} B_n(d_1,\cdots,d_n) $$ Calling $$ d_n = \frac{d^n}{dx^n}[ln(g(x))f(x)] $$ Since faa di bruno's formula states $$ \frac{d^n}{dx^n}[f(g(x))] = ...
0
votes
2answers
53 views

Sum function operation: coefficient.

I have problem with the sum: $$ \sum_{k=0}^n \dbinom{n}{k}(\cos \alpha)^k(i\sin \alpha)^{n-k}\,\, $$ Apparantly, I have an imaginary unit therefore I need to distinguish even and odd powers of $i$ to ...
6
votes
1answer
431 views

$m$ balls into $n$ urns

Assume that there are $m$ balls and $n$ urns with $m\gt n$. Each ball is thrown randomly and uniformly into urns. That is, each ball goes into each urn with probability $\dfrac1n$. What is the ...
0
votes
1answer
38 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
1
vote
3answers
106 views

Olympic elementary combinatorics problem

This is a problem taken from the regional selections of the Italian mathematical olympiads: A knight is placed on the bottom left corner of a $ 3\times3 $ chess board. In how many ways can you move ...
0
votes
1answer
59 views

Combinatorics-graph colouring [duplicate]

Show that if $K_9 $is coloured red and blue and contains no red triangle and no blue $K_4$, then every vertex must have red degree $3$ and blue degree $5$. I have absolutely no idea how to proceed :( ...
2
votes
2answers
127 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
0
votes
0answers
50 views

Combining 2 numbers into a uniqe number

I am stumped on a problem, I have a set of numbers (lets say 2 numbers) A and B and i want to combine them into a unique number C where C is not reproducible by any other set thats not identical ...
1
vote
1answer
52 views

How prove this number of the methods is this $\prod\prod 4\cos^2{\frac{j\pi}{m+1}}+4\cos^2{\frac{k\pi}{n+1}}$

Question: show that an $m$-by-$n$ chessboard can be partitioned some $1$-by-$2$ the numbers of methods is $$\prod_{j=1}^{\lfloor\dfrac{m}{2}\rfloor}\prod_{k=1}^{\lfloor\dfrac{n}{2}\rfloor} ...
2
votes
3answers
329 views

Probability of no ace in a 6 card hand, given 4 are not aces.

A player is dealt six cards out of a normal deck of cards. He looks at the first four and notices there is no ace among them. What is the probability that he does not have an ace at all. This sounds ...
0
votes
2answers
106 views

Possible 4 character passwords involving a letter and a digit.

A password consists of 4 characters, each of which is either a digit or a letter of the alphabet. Each password must contain at least ONE digit and AT LEAST ONE letter. How many different such ...
7
votes
0answers
154 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
0
votes
0answers
26 views

dimension of vector space $\frac{\langle e_{ab_1\ldots b_p}\rangle}{\langle \sum_{1\leq i\leq p}e_{ab_1\ldots \widehat{b_i}\ldots b_pc}\rangle}$

Let $p$ be a prime and $n\!\in\!\mathbb{N}$. What is the dimension of the $\mathbb{Z}_p$-module $$V_{p,n}=\frac{\langle e_{ab_1\ldots b_p};\: 1\leq a<b_1<\ldots<b_p\leq n\rangle}{\langle ...
0
votes
2answers
29 views

Probability of an event happening while another doesn't

Say you have a bag with $5$ numbers $(1,2,3,4,5)$. What is the probability that I will draw a $1$ if I draw $3$ times (no replacement)? What is the probability that I will draw a $1$ if I draw 3 ...
0
votes
0answers
91 views

Combinatorics problem - sitting at $n$ tables

I've got the following problem: Given $3n$ people, $n$ tables, each table is for $3$ people. In how many ways can these people sit at the tables so each two people meet only once? For example, let ...
0
votes
1answer
44 views

How many different teams can be created between two groups?

If a company has 8 painters and 12 electricians. How many different teams can be created with 1 painter and 1 electrician? I know that the number of ways a team can be made is: $ {8 \choose 1} * ...
4
votes
4answers
2k views

A simple permutation question - discrete math

There are five distinct computer science books, three distinct mathematics books, and two distinct art books. In how many ways can these books be arranged on a shelf if one of the art books is on ...
-3
votes
1answer
69 views

Better Explanation for an already posted question [duplicate]

Can anyone explain why in this question the answer is 5! * 2! * 10P3? I understand the 5! and 2! but for 10P3 the first thing I thought of was 3! Thanks.
2
votes
1answer
48 views

A problem on distributing indistinguishable balls into 10 different groups such that…

I got this problem which I am stuck at for an hour and half: Suppose that we have an infinite number of indistinguishable balls and we need to distribute them into 10 different groups such that $ ...
1
vote
1answer
28 views

Number of integer coefficient multilinear polynomials

I am looking for an expression for number of multilinear polynomials of degree atmost $t$ in $n$ variables with integer coefficients having coefficient size atmost $|B|$. Is ...
4
votes
3answers
204 views

possible pizza orders

You are ordering two pizzas. A pizza can be small, medium, large, or extra large, with any combination of 8 possible toppings (getting no toppings is allowed, as is gettting all 8). How many ...
1
vote
1answer
60 views

Choosing schedule for courses

To fulfill the requirements for a certain degree, a student can choose to take any 8 out of a list of 20 courses, with the constraint that at least 1 of the 8 courses must be a statistics ...
0
votes
2answers
46 views

How many different pairs can I have from two groups?

A company has 8 painters and 12 electricians, and teams can be created of one painter and one electrician. How many different teams can be created? My best guess is: $ {8 \choose 1} * {12 ...
13
votes
5answers
435 views

How many sets of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?

How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$. For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. ...
0
votes
1answer
81 views

Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with

Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with (a) An even number of 0s (b) An even total number of 0s and 1s (c) An even number of 0s and an even ...
1
vote
4answers
38 views

Select one or zero elements from a set

I am far from a mathematician. Still. I want to formally express that only 0 or 1 element of a series of sets (1...n) is selectet to form a new set. Example: I have three sets $S_1 = \{1,2,3\}$, $S_2 ...
2
votes
3answers
60 views

question on morse code

The morse code is made up of marks called dots and dashes."Q", for example is (--,--).Is it possible to make up such a code so that every letter of the alphabet is represented by at most three marks? ...
1
vote
2answers
102 views

Combinations in application - “smooth order”

I have a long winded question here, so I will state the final question first - then my long explanation: Is there a program, method, code, calculation in which I can determine a complete "smooth" ...
0
votes
2answers
882 views

Number of ways to sit 6 girls and 6 boys together with no two girls together.

As the title of the question explains: What I thought on the very first instant was that we will make them sit alternate hence the answer will be 2 * 6! * 6! But ...
1
vote
0answers
51 views

Proving that elementary row operations are preserved after multiplication

If $E$ is an elementary $n \times n$-matrix, show that if $A$ is any $n\times n$-matrix, then $EA$ is a matrix obtained by carrying out a single elementary row operation on $A$, and that $AE$ is a ...
2
votes
1answer
58 views

What is the probability of not rolling any given number on 10 rolls of a die?

In other words, ALL combinations which don't contain at least one of the number from 1-6 would count. So for example... 5, 2, 3, 3, 4, 1, 5, 5, 3, 1 would be counted because there is no 6 Also 5, ...
19
votes
3answers
353 views

What combinatorial quantity the tetration of two natural numbers represents?

Tetration is a generalization of exponentiation in arithmetic and a part of a series of other generalized notions, Hyperoperators. Consider $m\uparrow n$ denotes the tetration of $m$ and $n$. i.e. ...
1
vote
2answers
108 views

pairing possibilities in chess game

There are 20 people at a chess club on a certain day. They each find opponents and start playing. How many possibilities are there for how they are matched up, assuming that in each game it does ...
1
vote
1answer
43 views

Number of arrangements of the word “MAMMAL” where M is not together

This is in reference to this question. Letter Arrangement with Permutations _A_A_L_ IF M is not together, then M can go into 4 distinct places (denoted by the underscores above). So the number of ...
0
votes
1answer
34 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
8
votes
1answer
145 views

Number of distinct angles that can be formed on a square grid

Given a set of grid points arranged in an $n$ by $n$ square (in 2 dimensions): How many distinct proper (acute or obtuse) angles can be formed having a vertex on one grid point and line segments ...
7
votes
0answers
183 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
3
votes
2answers
142 views

Prove combinatorial identity using inclusion/exclusion principle

The identity is: $$\sum_{k=0}^{m} (-1)^{k} {{n} \choose {k}}{{n-k}\choose{m-k}} = 0$$ I'm not even sure where to begin. Does anyone have any suggestions?
0
votes
0answers
21 views

Upper bound for graphs with no k-cliques

We know that for random graphs $G(n,p)$ we have: $P[X=0]\leq e^{-\Theta(E[X])}$ where $X$ denotes the number of k-cliques in the random graph. Can this fact be used to say anything about the number of ...
1
vote
0answers
85 views

Binomial coefficient in closed form problem

Is anybody to give a insight, please? $8.9$. Let $\ell$ be an even positive integer. Express $$\sum_{k=0}^n\sum_{i=0}^\ell(-1)^i\binom{n}k^2\binom{2k}i\binom{2n-2k}{\ell-i}$$ in closed form. ...
-2
votes
1answer
49 views

Combinatorial Argument Proof

Prove: $c(40,5) = c(17,5) + c(17,4) + c(23,1) +...+ c(23,5)$ where c is the binomial coefficient. Can I use a combinatorial argument to prove?
1
vote
1answer
15 views

Distributing dimes to 2 groups of people such that each member of one group gets at least one

I have a study question that I have the answer for, but I just can't understand how or why it is the answer. The question is: $n$ dimes are distributed to $y$ young people and $o$ old people. Every ...
0
votes
1answer
32 views

Number of graphs with M edges that does not contain K-clique

If we consider the space of graphs $G(n,M)$ with $n$ vertices and $M$ denotes the number of edges. Is there any way of upper bounding the number of graphs in this space that does not contain any ...