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
42 views

Ways to get a full house, how is my method wrong?

In how many ways can you deal a "full house"? (Three cards of one rank and two cards of another rank.) What is wrong with this approach? ${13 \choose 2}$ ways to choose 2 ranks out of 13 ${4 \...
2
votes
1answer
113 views

A 4 × 4 grid of squares is filled in, with each of the 16 squares colored either black or white…

A 4 × 4 grid is filled in, with each of the 16 squares colored either black or white. Two colorings are regarded as identical if one can be converted to each other by performing any combination of ...
2
votes
1answer
39 views

Two pair problem, what is wrong with this reasoning

What is the probability that you are dealt a "two pair"? (Two pairs of cards where each pair contains two cards of the same denomination, with the fifth card of a different denomination. Note that we ...
0
votes
1answer
53 views

How many non-identical colorings are there?

A 4 × 4 grid of squares is filled in, with each of the 16 squares colored black or white. Two colorings are regarded as identical if one can be converted to each other by performing any combination of ...
3
votes
1answer
39 views

Large family of subsets of odd size such that the pairwise intersections also have odd size

I'm trying to prove that for some $\alpha > 1$ and every $n ≥ 5$, there is a family $F ⊂ P(n)$ of size at least $\alpha^{n}$ such that every set in $F$ has odd size, and the intersection of any two ...
1
vote
1answer
38 views

We are making bracelets with 6 stones in a ring, with three different colors of stone…

We are making bracelets with 6 stones in a ring, with three different colors of stone. A bracelet must contain at least one stone of each color. Two bracelets are considered to be identical if one is ...
4
votes
1answer
52 views

In how many ways can two dozen identical robots be assigned to four assembly lines?

In how many ways can two dozen identical robots be assigned to four assembly lines with (a) at least three robots assigned to each line? (b) at least three, but no more than nine ...
0
votes
1answer
134 views

Number of solutions to the equation $a + b + c + d = 25$ [closed]

Use generating functions to answer the following question: What is the number of solutions of the equation $a + b + c + d = 25$ if $a, b, c, d \in \{0,1,2,\ldots,9\}$? Any ideas for the problem?
0
votes
1answer
65 views

What is the probability two die show the same values on their second rolls?

What is the probability two die, a red and a white one, show the same values on their second rolls as on their first rolls? so i first computed the total number of ways of just getting outcomes from ...
1
vote
3answers
38 views

Product of generating functions

Let $f(x) = \sum_{i=0}^\infty a_ix^i$ and $g(x) = \sum_{i=0}^\infty b_ix^i$ where $a_n = 1$ and $b_n = 2^n$ for all natural numbers $n$ What are the first three terms of the sequence generated by $...
-2
votes
1answer
91 views

Closed form expression for $\sum_{k=0}^{n}(k^2 + 3k + 2)$

How can I find the closed form expression for the sum below using generating functions? $$\sum_{k=0}^{n}(k^2 + 3k + 2)$$ EDIT: We transform $k^2+3k+2$ into $(k+2)(k+1)$. Let $a_k=(k+2)(k+1)$ and $...
1
vote
1answer
30 views

Possible results that can be in a horse race

There are three horses: Uri, Uli and Buki. Results that can be possible in the race are 13. Uri first, Uli second, Buki third. Buki first, Uri second, Uli third. Buki first, Uri and Uli second ...
4
votes
3answers
43 views

Elementary Combinatorics… How many different shirts are being sold?

A shirt sold in 6 colors, 5 sizes, striped or solid, and long sleeve or short sleeve. -How many different shirts are being sold? -What if the black and yellow shirts only come in short-sleeve and ...
0
votes
1answer
57 views

How many ways to put 3 balls in 5 urns

How to put 3 balls in 5 urns (where an urn can have any number of balls)? Why doesn't this approach work? I can select $5\choose 3$ urns and put 3! on the selected ones. So shouldn't the number of ...
0
votes
3answers
60 views

Choosing 5 marbles out of 100 identical marbles?

In how many ways can $5$ marbles be chosen out of $100$ identical marbles? Why does my book say there is only one way to make this selection?
0
votes
0answers
28 views

Selecting point of reference when counting

When arranging people (A, B, C, D, E) in seats (1,2,3,4,5), why isn't it same to count with reference to seats eg. (number of people can sit in seat number 1) * (number of people can sit in seat ...
0
votes
1answer
25 views

number of linear boolean function with XOR

For x, y ∈ {0, 1}n , let x ⊕ y be the element of {0, 1}n obtained by the component-wise exclusive-or of x and y. A Boolean function F : {0, 1}n → {0, 1} is said to be linear if F(x ⊕ y) = F(x) ⊕ F(y), ...
0
votes
0answers
93 views

Recurrence relation for ordering n items from k different types

I'm having trouble with this question, could someone please walk me through the thinking process on how to approach this problem? please give a detailed explanation on what each step represents. Find ...
0
votes
0answers
64 views

Calculating horse racing odds by having some data.

I've seen a few similar questions but non of them give satisfactory answer. My question is connected with horse races. Assume we have a race with 6 horses and we are given following coefficients (...
3
votes
1answer
222 views

Prove identity without using complex numbers

How to prove the following identity without using complex numbers (and de Moivre's formula)?
1
vote
1answer
24 views

Combinations problem on committee.

A committee of three boys and three girls is to be selected from a class of 14 boys and 17 girls. In how many ways can the committee be selected if: (a) Ana has to be on the committee? (b) the girls ...
0
votes
1answer
31 views

Consider the set A = { x| x = (a+b)^3^n mod 3} where a and b is either 0 or 1, n is a positive integer. Determine the cardinality of the set A

Consider the set $A = \{ x \mid x = (a+b)^{3^n} \mod 3\}$ where $a$ and $b$ is either $0$ or $1$, $n$ is a positive integer. Determine the cardinality of the set $A$. Not sure whether the answer is 3 ...
0
votes
0answers
48 views

permutation with 3 cycles

I am supposed to find the number of permutations on a set of {1,2....n} with two fixed points and three cycles. I have a trouble solving the second part - finding the number of permutations with three ...
1
vote
2answers
41 views

prove the formula and then evalute the sum

m,n,r are given non-negative integers, show that $\sum_{k>=-n}$ ${r \choose m+k}$ ${s \choose n+k}$ $=$ ${r+s \choose r-m+n}$ Then evaluate $\sum_{k>=0}k$ ${r \choose k}$ ${s \choose k}$ I ...
0
votes
1answer
30 views

What is the maximum cardinality of $C$?

Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 ⊂ S_2$ or $S_2⊂ S_1$. What is the maximum ...
0
votes
1answer
47 views

Combinatorial argument for numbers

As part of a bigger proof I want to show the following proposition, but unfortunately I did not make any progress on it: Let $X:=\{a_1,...,a_n\} \subset \mathbb{N}$ such that $\text{gcd}(a_1,...,a_n)=...
4
votes
1answer
39 views

Given no of ways of selection for a game of mixed doubles find no of ways if selecting any 2 people

If the number of ways of choosing 2 boys and 2 girls in a class for a game of mixed doubles is 1620, what is the number of ways of choosing 2 students from the class? My attempt: Let there be $m$ ...
0
votes
0answers
27 views

State space complexity of $2d$ and $3d$ tic tac toe

So for a 2d tic tac toe game, we know that the space complexity can be represented as follows. A naive upper bound will be $3^9$ as there is $3$ possibilities (X, Y or blank) in each of the $9$ ...
1
vote
2answers
41 views

Probability of 2 permutations of slightly different sets meeting in k places.

I have already posted a simplified problem of this (and received a comprehensive answer) hoping that it would lead me to solving this one, however, it does not seem to be the case. We have got two ...
1
vote
2answers
21 views

Probability of 2 n-permutations meeting in k places.

I have been thinking about think problem, however, I still do not really know how to tackle it. We have two permutations of $n$ elements. What is the probability that these two permutations meet in ...
3
votes
2answers
50 views

Some very particular strictly ordered sequence of numbers

You can construct a sequence of 5 numbers $(a,b,c,d,e)$ with the following rule: $a\in\{1\}$ $b\in\{2,3\}$ $c\in\{3,4,5\}$ $d\in\{4,5,6,7\}$ $e\in\{5,6,7,8,9\}$ How many sequence are strictly ...
1
vote
2answers
26 views

Prove by induction that all coins greater than or equal to 8p can be made using 3 pence and 5 pence coins . [duplicate]

Prove by induction that all coins greater than or equal to 8 pence can be made using 3 pence and 5 pence coins . Here is my thought : I looked at Z+ greater than 8 ... I considered multiples of 3(...
2
votes
0answers
52 views

Recurrence Relation - How to come up with a formula

Here is an example from "Discrete and combinatorial mathematics an-applied introduction" by Grimaldi. My problem is that I have a hard time following along with the arguments. Example: For $n\geq 1$ ...
2
votes
0answers
112 views

Number of edges needed for good colouring in Ramsey graph theory

Given $n$, consider the complete graph $K_{R(n)-1}$, where $R(n)$ is the diagonal Ramsey number. So there exist $2$-colourings of the edges of $K_{R(n)-1}$ without a monochromatic copy of $K_n$. ...
0
votes
2answers
69 views

Find number of words of length n over alphabet {A, B, C} where any nonterminal A must be followed by B.

Let $a_n$ be the number of words of length n over the alphabet {A, B, C} such that any nonterminal A has to be immediately followed by B. Find $a_n$. Here's what I know: If the word starts with $C$ ...
0
votes
1answer
25 views

The approximability of different NP-hard problems

I'm fairly new to the topic Computational Complexity and had the following question (I therefore apologies before hand for any poorly stated terminology). Suppose i have two optimization problems $A$...
2
votes
1answer
47 views

Finding the number of permutations of the digits 1 through 9 in which none of the blocks 34, 45 and 738 appears

How do I find the number of permutations of the digits 1 through 9 in which none of the blocks 34, 45 and 738 appears? I know that I can probably brute force the solution, but is there a concept I ...
5
votes
6answers
1k views

How many different ways can I get up a flight (of stairs) with 11 steps?

You can climb either $1$ or $2$ stairs at a time, at any given time. How many ways can you get up $11$ stairs? I've tried using different cases to solve this. So I did: Case 1: All $1$ steps --> $...
0
votes
0answers
47 views

How many of these permutations leave no number fixed?

I am not exactly sure how to approach this problem. I know that there exists only one mapping in which all numbers are fixed, but I don't how this translates into leaving no number fixed. Below are ...
2
votes
1answer
41 views

Using generating functions show that $\sum^n _{r=1}r\binom{n}{r}\binom{m}{r} =n\binom{n+m-1}{n}$

Using generating functions show that $$\sum^n _{r=1}r\binom{n}{r}\binom{m}{r} =n\binom{n+m-1}{n}$$ I have been thinking about it as follows. The RHS is a coefficient of $x^n$ in the expansion of $$\...
1
vote
0answers
49 views

How many binary sequences of length n satisfy constraints

Let Sn be a sequence of ones and zeros, of length n Let C(a,b,c) be the constraint defined as: Subsequence starting from the a-ith element of the sequence, ending at b (included), must have value c, ...
0
votes
1answer
84 views

Number of permutations for card decks in “Skat” and “Doppelkopf” games

In the card game Skat, you play with a deck of $32$ cards and each of the three players gets $10$ cards. This means that there are $32! \approx 2.63 × 10^{35}$ possible permutations of the card deck. ...
0
votes
1answer
29 views

Number of points of intersection between lines.

Lines $L_1,L_2,...,L_{100} $ are distinct .All lines $L_{4n}$ ,$n$ a positive integer, are parallel to each other. All lines $L_{4n-3}$, $n$ a positive integer,pass through a given point $A$. Find the ...
2
votes
1answer
147 views

Finding $\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$

How to find this alternating sum of binomial coefficients? $$\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$$
1
vote
1answer
61 views

Probability that two such randomly generated strings are not identical

A random bit string of length $n$ is constructed by tossing a fair coin $n$ times and setting a bit to $0$ or $1$ depending on outcomes head and tail, respectively. The probability that two such ...
1
vote
1answer
43 views

Number of unordered partitions of a given cardinality

suppose that I have N distinct elements, I would like to count the number of ways that they can be arranged in subsets of cardinality m1,m2,...,mK such that m1+m2+...+mK = N. Example: I have N=4 ...
2
votes
1answer
50 views

Use inclusion-exclusion principle to count permutations where no number $i$ is followed by $i+1$

$a_n$ is the number of permutations of $[n]$ in which no number $i$ is immediately followed by $i+1$. I need to use the Inclusion-Exclusion principle to get a formula for $a_n$. In this case I know ...
1
vote
1answer
53 views

Collisions in random permutations

Let $S_n$ denote the group of permutations on $n$ letters, and consider a subset $A = \{\sigma_1, \dots, \sigma_k\} \subset S_n$. We will say $A$ has a collision if there are two permutations in $A$ ...
2
votes
1answer
20 views

If C is a subgraph of G, with a vertex v with 2 incoming edges, by definition of simple cycle for directed graphs, is C a simple cycle?

I am trying to prove something about graphs... clearly a non-directed graph like this: $a-b-c-d-a$ is a cycle, but what about when we talk about directed graphs, $a \to b \to c \to d \to a$ is one, ...
1
vote
2answers
38 views

String in an kleene star alphabet

Let Σ = {a, b}. How many strings of length 10 are in the language (bb + aab)*? If this a matter of writing them out or is there a formula to it?