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)

0
votes
1answer
19 views

Non-recursive formula for calculating the number of ways of arranging k elements in an n-element list so that no three elements are in adjacent cells?

While working on one problem, I've found myself solving a sub-problem like this recursively: We have a list of length $n$ consisting of $k$ ones and $n-k$ zeroes. In how many ways can we ...
0
votes
0answers
14 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
1
vote
1answer
46 views

Suppose we roll 10 fair six-sided dice. Probability of getting exactly two 2's and three 3's?

Here's my solution, but as usual with combinatorics problems, I tend to be convinced of my errors too early. So I'd like to know what you guys think. Is this correct? $\frac{\binom{10}{2} ...
0
votes
1answer
87 views

Combinatorial Power Series proof [closed]

Need help proving the following involving power series $A(x)$ and $B(x)$: If $A(x)B(x)=0$ (the power series where every coefficient is 0), then $A(x)=0$ or $B(x)=0$. AND If $(A(x))^2=(B(x))^2$, ...
9
votes
0answers
104 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
3
votes
0answers
76 views

Probability that a bridge hand has at most $k$ points

I want to calculate the exact probability that a random bridge hand has at most $k$ points , where $0\le k \le 37$ (more than $37$ points is not possible) For non-bridge-players : A bridge hand ...
0
votes
1answer
33 views

How many subgraphs does $K_3$ have? Same question for $K_n$

I have the following problem solved, but the answer seems wrong to me. Problem: How many subgraphs does $K_3$ have? Same question for $K_n$ Answer: We will classify the subgraphs by the size of ...
2
votes
1answer
21 views

Find number of inversions in the permutation $X$. Given $A$, $B$, $C$ and $AXB = C$.

$$ A = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 1 & 5 & 7 & 6 & 4 \end{pmatrix} \\ B = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 ...
0
votes
1answer
21 views

Probability of search results showing up for two different merchants with different products in a top 25 list.

If we have 115,000 results for a given search term on a shopping web site with multiple merchants and one merchant has 28 products that match while the other has 78, what is the probability of their ...
1
vote
1answer
39 views

A quick exercise on the Binomial Theorem

What is the coefficient of $x^2$ in $(2x-5)^{24}(3-4x)^{60}$. So applying the Binomial Theorem, we get $\sum\limits_{k=0}^{24}{24\choose k}(2x)^k(-5)^{24-k}\times\sum\limits_{n=o}^{60}{60\choose ...
1
vote
1answer
29 views

Matching with number of edges from one side

Let $A=\{a_1,\ldots,a_k\}$ and $B=\{b_1,\ldots,b_l\}$ be two sets of students. Suppose that each $b_i\in B$ knows at least $m$ students in $A$. Can we always find $m$ disjoint pairs $(a_i,b_i)$ such ...
-1
votes
0answers
30 views

Chances in combinatorics [on hold]

There are 124 apples, you and 9 more people are taking them. What are the chances for you to take the one that you wanted?
0
votes
1answer
17 views

Partitions of an integer where each summand appears at most four times

Find the generating function for the number of partitions of an integer (greater than zero), where each summand appears at most four times. Is it the following?
4
votes
4answers
140 views

Simplify the expression (combination and factorial)

Simplify the following expression: $\binom{n+1}{3} * \frac{(n-1)! + (n-2)!}{(n+1)!}$ My attempt: $\binom{n+1}{3} * \frac{(n-1)! + (n-2)!}{(n+1)!} = \frac{(n+1)!}{3!(n+1-3)!} * \frac{(n-1)! + ...
0
votes
1answer
46 views

number of ways to choose pairs of nonadjacent people from $2k$ people sitting in a circle

The following is problem 19 in Chapter 2 from Richard Stanley's Enumerative Combinatorics, vol. 1 (2nd ed.): Suppose that $2k$ persons are sitting in a circle. In how many ways can they form pairs if ...
3
votes
2answers
146 views

Showing planarity of graphs

I am trying to show $G_3$ is planar. I have constructed $G'_3$ as shown. Is it correct to say that by the Jordan curve theorem, $G_3$ cannot be planar, as any drawing will cause edges to overlap. ...
2
votes
2answers
54 views

Understanding a Generating Function

This is from generating functionology by Herbert S Wilf. Here a rule is given as let f $\longleftrightarrow$ {$a_n$}$^{\infty}_0$ is a ordinary power series generating function and let k be a ...
0
votes
2answers
28 views

Linear Recurrences

I was working on linear recurrence... But I am having trouble with it. $a_0 = 1; a_1 = 2; a_k = 4a_{k-1} - 2a_{k-2}$ I found $a_2$ which is $$4a_1 - 2 a_0=4\cdot2 - 2\cdot 1 = 6$$ I found $a_3$ ...
0
votes
1answer
37 views

Which formula to use to solve following problem? The number of combinations without repetition or smth. else? [closed]

I don't know combinatorics at all. Could anyone point section of combinatorics or wiki article to solve problem below? Girl has five red, four blue and four green flowers. She wants to plant all ...
0
votes
1answer
40 views

Probability of most frequent occurrences of suits/values when drawing 4 cards from 52

Draw 4 cards from a card deck with 52 cards (4 colours and 13 values for each colour) one after the other -- none is put back. Let's have two discrete random varaibles X and Y. X counts the maximum ...
2
votes
1answer
40 views

Exponential generating functions counting

How many $10$-digit numbers use only the digits $0, 1, 2$ with each digit appearing at least twice or not at all? I know I need the coefficient of $\frac{x^{10}}{10!}$ in: ...
0
votes
2answers
69 views

how many ways can you divide 24 people into groups of two? [closed]

just can't seem to figure this out. I need to aquire a function for this scenario. I have tried to look at smaller forms of the problem. My problem is I am struggling to get the # of possibilities. ...
0
votes
1answer
56 views

Generating function for set of binary strings of equal block length

Where blocks would be consecutive 0's or consecutive 1's. So 0000 would be a block of length 4. I'm not even sure how such a set would look? Would the following elements at least be in the set (so I ...
1
vote
1answer
22 views

Probability of full house

I'm trying to calcualte the probability of a full house in a standard 52-card deck. We choose out of the thirteen kinds $2$ of them so $\binom{13}{2}$. There are $4$ houses of each card in the deck ...
1
vote
0answers
66 views

Finding coefficient in formal power series

How to do this kind of questions: Determine the value of the following coefficient: $[x^{33}](x+x^3)(1+5x^6)^{-13}(1-8x^9)^{-37}$
1
vote
2answers
35 views

Arrangements of sets of k positions in a n-competitors race

Let $E(n)$ be the set of all possible ending arrangements of a race of $n$ competitors. Obviously, because it's a race, each one of the $n$ competitors wants to win. Hence, the order of the ...
2
votes
2answers
61 views

How to calculate the Summation??

Can we get the formula in terms of N and k for this summation series? $$ A=\sum_{t=0}^N\sum_{s=0}^t\sum_{r=0}^sk^rk^{s-r}k^{t-s} $$
0
votes
0answers
10 views

Existence of two-color paths between boundary vertices in a near-triangulated plane graph with an external face of degree 4

Let G be a plane graph with the following characteristics: It is near-triangulated. It has an external face of degree 4 (i.e. the graph has 4 boundary vertices, a diamond-shaped boundary ring). It ...
1
vote
1answer
11 views

What is $R(k,l)$?

I'm reading Landman/Robertson's: Ramsey Theory on the Integers. It states the following theorem: Theorem 1.15 (Ramsey's Theorem for Two Colors). Let $k,l \geq 2$. There exists a least positive ...
1
vote
1answer
30 views

How to find a formula for these generating sequences?

It is given that $a_{0}=1$ , $b_{0}=0$ , $c_0=0$ $$ c_n= xc_{n-1}+x(x-1)a_{n-1}(3b_{n-1}+(x-2)a_{n-1}^{2})) $$ $$ b_n=xb_{n-1}+x(x-1)a_{n-1}^{2} $$ $$ a_n=xa_{n-1}+1 $$ where x is any constant. ...
1
vote
1answer
46 views

Binomial Theorem…extra indexed term.

I have the following expression: $$\sum_{i=0}^{n}\binom{n}{i}(2x+1)^{n-i}(-1)^ii!$$ Without the $i!$, the above expression would simply reduce to $(2x)^n$, but is there a way, or method for ...
0
votes
1answer
27 views

Prove that using generating function:For any $n ,k\in N$, the number of partitions of $n$ into parts

For any $n,k\in N$, the number of partitions of $n$ into parts, each of which appears at most $k$ times, is equal to the number of partitions of $n$ into parts the sizes which are not divisible by ...
-1
votes
1answer
42 views

How do we prove that $(k!)^2$ is factor of $(2k + 2)!$ for any positive integer $k$? [closed]

Prove that $(k!)^2$ is a factor of $(2k+2)!$ for any positive integer $k$.
2
votes
2answers
87 views

Prove ten objects can be divided into two groups that balances each other when placed on the two pans of balance. [closed]

There are 10 objects with total weight 20, each of the weight being a positive integer. Given that none of the weights exceed 10, prove ten objects can be divided into two groups that balances each ...
2
votes
1answer
55 views

Arrange the 26 letters of the alphabet in a row such that certain words do not occurr

How many ways are there to arrange the 26 letters of the alphabet in a row such that none of the following words are formed by consecutive letters in the arrangement INCH, LOST, or THIN? The answer ...
0
votes
1answer
33 views

How many ways can $3$ black counters and $5$ red counters be selected from a bag containing $7$ of each? [closed]

In how many ways can we choose 3 black counters and 5 red counters from a bag containing 7 black counters and 7 red counters?
0
votes
1answer
19 views

Integrality conditions and proof by double counting.

Theorem $\mathbf{3.4.}$ In a block design of type $2-(v,k,\lambda)$ every element lies in precisely $r$ blocks, where $$r(k-1)=\lambda(v-1)\textit{ and }bk=vr\;.$$ The letter $r$ stands for ...
2
votes
0answers
62 views

Tricky combinatorics problem

I'm trying to solve the following problem: You get $15$ free spins on a slot machine, with a $0.01$ chance of re-triggering a further $15$ spins when a certain symbol falls on the centre reel. You ...
-1
votes
0answers
15 views

Select k non overlapping rectangles in a $n \times m$ grid

We are given a given a $n \times m$ grid with $nm$ points. We have to select $k$ rectangles(obviously with corners lying at lattice points) such that no $2$ of them overlap. We can give a recurrence ...
1
vote
0answers
14 views

The maximum size of an antichain in a poset

Given $A$ as an n-element set and $X=p(A)$, I need to show that if $F$ is an antichain in the poset $(X,\subseteq)$ such that the maximum size of $F$'s elements is $n/2$ then $\mid F \mid \leq (_k^n)$ ...
1
vote
1answer
43 views

Distributing identical objects into distinct boxes

The problem I'm trying to solve is: find the number of ways of distributing $r$ identical objects into $n$ distinct boxes such that no box is empty, where $r \geq n$. I've found conflicting answers ...
3
votes
3answers
71 views

Seating arrangements with no 3 objects together.

Suppose that five $1$'s and six $0$'s need to be arranged in such a way that no three $0$'s are consecutive. How many different arrangements are possible? This is a variation on a problem where ...
1
vote
1answer
37 views

Splitting parties into committees

I feel like this should be an extremely simple problem, but I can't quite figure it out. How many ways are there to split $2n + 1$ places in a committee among $3$ nonempty parties, such that a ...
2
votes
3answers
30 views

Proving the combinatorial expression

Ok I've been reading in my probability book about the different methods on how to count and I'm just trying to dissect the usual combinatorial formula: $$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$ ...
4
votes
2answers
55 views

Expected value of max of three numbers

This is a combo problem that a friend came up with some time ago, and recently showed to me. He claims he solved it when it first occurred to him, but can no longer remember the solution, and neither ...
1
vote
2answers
39 views

How many five digit positive integer numbers are possible that each of the digits but the last one, is $\ge$ the next digit?

How many five digit positive integer numbers are possible that each of the digits but the last one, is $\ge$ the next digit? How do I approach this problem?
2
votes
2answers
36 views

Finding Number of Ordered Solutions to Equation

$$ A \times B \times C \times D \times E \times F = 7 \times 10^7 $$ How can I find the number of ordered solutions for integers (I mean for integers $A,B,C,D,E,F$) so that they can satisfy the ...
0
votes
3answers
153 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
1
vote
1answer
29 views

Select $k$ non overlapping segments from $n$ points

We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap. One possible solution would be by using a recurrence relation $f(k,n)=\sum ...
1
vote
0answers
65 views

The best strategy to increase StackExchange Reputation [closed]

I do not have a lot of background in game theory, but I am curious how would one formally pose the title problem and mathematically describe possible strategies. Are the problems of this type best ...