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)

1
vote
1answer
380 views

Find the number of elements in the set: $A=\{\sigma\in S_4 |\thinspace \sigma\thinspace(3)=3\}$

Find the number of elements in the set: $A=\{\sigma\in S_4 |\thinspace \sigma\thinspace(3)=3\}$ I know that this would be $3!=6$. But are these the correct elements? $$ \{e, (12), (24), (14), (142), ...
1
vote
1answer
95 views

The complexity of counting solutions to $x_1 + \dots + x_m = N$ in non-negative integers under constraints

Consider the equation $$x_1 + \dots + x_m = N$$ where $x_1,\dots,x_m \ge 0$ and under the additional constraints $x_k \le a_k$ for $k=1,2,\dots,m$. I'm interested in knowing whether the number of ...
1
vote
1answer
49 views

Combinations formula

What is the no. of ways to distribute N identical objects among two persons such that at every instant first person gets more than the second person? My approach is : For N=1 ans=1 For N=2 ans=1 For ...
0
votes
1answer
323 views

Graph theory : How to find edges ??

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by Kn the complete graph on n vertices. A simple bipartite graph with bipartition (X,Y)...
0
votes
1answer
57 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
0
votes
1answer
54 views

Long induced path containing a lot of vertices from a stable set

Is there a simple proof/counter-example for this? If we have a (big) connected graph $G$ with a big stable set $S$ and with bounded maximum degree (read "small"), then there's a long induced path (...
0
votes
1answer
37 views

colouring a non-cubic prism

How many distinct ways are there to colour the faces of a rectangular non-cubic prism, if you have 3 colours available to use? attempt of solution: we have done this same question with a cube but ...
-1
votes
2answers
47 views

Combinatorics on sets

Let $A$ and $B$ be two sets containing $2$ elements and $4$ elements respectively. Find the number of subsets of $A\times B$ having $3$ or more elements. My actual problem is how can a cartesian ...
0
votes
1answer
31 views

There is no projective plane of order $10$.

I need to determine if there is a projective plane of order $10$. The Bruck-Ryser theorem tells us that if $n \equiv2, 1 \bmod 4$, and there is a projective plane of order $n$, then $n$ is a sum of ...
0
votes
2answers
32 views

Number of ways to assign $8$ subjects to $4$ people s.t. one gets an odd number of subjects

I am asked to find the number of ways to assign $8$ subjects to $4$ people, such that the third person always gets an odd number of subjects. What I did was consider the problem as putting ...
0
votes
1answer
65 views

How can I figure out the total solutions in this Combinatorics problem?

Imagine you have a sequence of cards, each having a unique set of features. Example features : letter (A, B, C), number (1, 2, 3), and color (Red, Green, Blue) Some example cards : A1Red, B1Blue, ...
0
votes
1answer
310 views

combinatorics shelf arrangement

Any help with this problem would b highly appreciated. Brian needs to put twelve distinguishable school books away. Four of them are science, five are math and the remaining three are computer books....
1
vote
2answers
67 views

Division of Objects into Different Sized Boxes

Suppose you have a set of N distinguishable boxes with lengths $l_1$,$l_2$...$l_N$. Suppose you try to divide x distinguishable objects among them, such that the probability of any object landing in ...
0
votes
2answers
79 views

Marbles combinatorics problem

An urn contains 4 red, 5 blue and 3 green marbles. Six are drawn at random (without replacement) one at a time. How many ways could the sequence of six marbles contain two of each color? I thought ...
0
votes
1answer
86 views

Cardinality of sum-set of two arithmetic progressions

Suppose that sum-set $A+B$ between sets $A$ and $B$ is defined as $A+B=\{a+b|a \in A, b \in B \}$. We further assume that $A=\{d_az|z \in \mathbb{Z} \}$ and $B=\{d_bz|z \in \mathbb{Z} \}$ where $d_a$ ...
0
votes
1answer
116 views

How can I prove this combinatorial identity without using Wilf-Zeilberger?

I am trying to prove the following identity without using W-Z algorithm: \begin{equation} \sum\limits_{j=0}^n (-1)^{(n-j)} \frac{(n+j+1)!}{(n-j)!(j)!(j+1)!} = 1 \end{equation}
2
votes
2answers
72 views

Interesting combinatorics question

As a child I had a deck of cards which consisted of maybe 50 cards. On each card there were 6 objects. Players had to pick 2 cards from the deck, and the player who first spotted the difference ...
3
votes
1answer
225 views

Placing n points in a MxM square grid

I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
1
vote
1answer
75 views

Calculate sum with binomial coefficients: $\sum_{k=0}^{n} \frac{1}{k+1} \binom nk x^{k+1}$

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
5
votes
6answers
4k views

Fewest number of moves to win the game 2048?

I'm trying to figure out the fewest number of moves one could make to win the game 2048. In another thread, someone placed the figure at 520, but I'm wondering if anyone knows how to mathematically ...
0
votes
1answer
163 views

about probablity of a card game with replacement allowed

I am thinking of a card game using standard 52 card and randomly deal 5 cards as initial hand. It is easy to calculate the probability of each winning hand (straight, flush, full house, etc.) dealt to ...
2
votes
3answers
50 views

probabilty of getting one of each character

Kelloggs (the breakfast-foods company) and Nintendo (which owns the Pokemon franchise) have agreed to distribute Pokemon toys for free inside specially-marked boxes of Fruit Loops. Upon opening a ...
3
votes
2answers
287 views

Is there a solution to this Seating Plan problem?

So a colleague asked me for some Help on an interesting Problem, which we both couldn't find the optimal answer for. The event which needed it is already in the past, so this is just me trying to ...
0
votes
1answer
89 views

Number of ways to colour a square with n colours

A smaller square is centered inside of a larger one. If we paint the edges of the outer square and the corners of the inner square, then how many distinct ways are there to colour the squares, ...
5
votes
2answers
349 views

Number of ordered pairs $(a,b)$ such that $ab \le 3600$

Find number of ordered pairs $(a,b)$ such that $ab\le 3600$ and $a,b \in N$ My attempt : Well, all $a,b \leqslant 60$ are solutions. These 3600 solutions. After that I have no idea how to count the ...
0
votes
2answers
48 views

Understanding “avoiding sequence”

Each subsequence (91674, 91675, 91672) is called a copy, instance, or occurrence of σ. Since the permutation π = 391867452 contains no increasing subsequence of length four, π avoids 1234. http://en....
2
votes
3answers
2k views

How many four digit numbers, in which all digits are distinct, contain at least one of 2 and 4 and have no leading zeros?

First off, I'm not quite sure what this question is asking (there are a lot of very vague questions in the textbook I'm using and it's caused me some frustration), and I'm assuming one interpretation ...
59
votes
8answers
33k views

Probability that random moves in the game 2048 will win

I have recently played the game 2048, created by Gabriele Cirulli, which is fun. I suggest trying if you have not. But my brother posed this question to me about the game: If he were to write a ...
1
vote
1answer
186 views

How many ways to paint a board with 2 colors..

You got a fence, you need to paint the boards with black and white, but can not have 3 or more boards same color in a row. how many ways do you have?
3
votes
1answer
133 views

How did the Symmetric group and Alternating group come to be named as such?

The Dihedral group makes sense, "Di" means two, and "hedral" means.. shape I think (I've just realised how much of what I think words mean are guesses based on experience) like a "polygon" is a 2d ...
1
vote
1answer
127 views

determining the size of a test bank given acceptable number of repeats

I have a question for a challenge that I'm trying to create - having some trouble quantifying the size of the challenge's test bank. 20 people are taking a challenge of 9 questions the test bank (n) ...
0
votes
5answers
297 views

Get the number of subset.

number of subsets of A with an even number of elements; A ={1,2,3,4,5,6,7} I have no idea about this question(This is part h of the problem set and I finished the previous). Here, subsets of A with ...
0
votes
2answers
829 views

Combinatorics proof of “sum of (k choose m) with k from m up to n is equal to n+1 choose m+1”

I've already proved this statement algrebraically. I'm asked to prove it with combinatorics. So far I came up with, LHS= # ways to choose m apples from a total of m,m+1,...,n RHS= # ways to choose ...
0
votes
2answers
32 views

X probability function

3 men and 3 women sits on chairs numbered 1-6. let X be the lowest number which a woman sits on. what is the probability function of X? I know X=1,2,3,4 and all the combinations is 64, but Im not ...
3
votes
1answer
35 views

Combinatorial approach to an inequality.

Prove that $$\left(\frac{2^{10}}{11}\right)^{11} \gt \binom{10}{1}^2\binom{10}{2}^2\binom{10}{3}^2\binom{10}{4}^2\binom{10}{5} $$ I am practicing for an upcoming exam, and this question got me stuck. ...
-2
votes
2answers
117 views

How many times can a word appear in a random phrase?

I'm taking about finding a word in a larger set of characters. Lets say, what is the probability/chance of finding the word 'math' in a random 8 length phrase. (For example gjbmdlep does not have ...
3
votes
2answers
149 views

Find the number of series

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that: $$ 11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i $$ (this is not a homework) There is a similar problem (...
7
votes
0answers
196 views

Knight's metric: ellipse and parabola.

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...
3
votes
3answers
107 views

Number of solutions of $x+y+z=10$

The number of different solutions $(x,y,z)$ of the equation $x+y+z=10$ where each of $x, y$ and $z$ is a positive integer is $36$. How to derive this answer? I know that $x, y$ and $z$ have to be $...
1
vote
2answers
326 views

If we take 5 shots with a basketball, what's the probability that you make 2 given you make at least 1?

Probability of making a shot is $\displaystyle \frac{3}{5}$. So $2$ shots would be $\displaystyle \dbinom{5}{2} \left(\frac{3}{5}\right)^2 \left(\frac{2}{5}\right)^3$ right?
0
votes
2answers
75 views

A fair dice is rolled until a 2 comes up. Given the first roll is not 2, what's the probability it'll take more than 3 rolls?

Also, if it takes an even amount of rolls, what's the probability of exactly 2 rolls? I am completely lost so any help would be appreciated.
4
votes
2answers
3k views

How many routes possible in the traveling salesman problem with $n$ cities? And more…

SO the general answer I come across on the internet is $(n-1)!/2$. But it would seem to be $n!$, or at least $(n-1)!$. Which one is it? If you have 2 cities, you would have 1 path. So $(n-1)!/2$ can'...
0
votes
0answers
44 views

Illustrate this proof about transversals with an example. Is there a typo?

Let $F = \{S_1,\dots,S_m\}$ and $G = \{T_1,\dots,T_m\}$ be two collections of subsets of a finite set $E$. A transversal for $F$ is a list of elements $s_1,\dots,s_m$, one coming from each set in $F$....
0
votes
4answers
323 views

How to prove the following combinatorial identity?

How does one prove that, for $1 \leq k \leq n $, it is true that $\binom{n+k-1}{n-1} = \sum_{i=1}^{k} \binom{k-1}{i-1} \binom{n}{i} $ ? I tried to prove it by working out the definitions of the ...
1
vote
1answer
57 views

Equality of the number of multisets to \sum_{i = 1}^k \binom{k - 1}{i - 1} \binom{n}{i}

As part of an exercise I'm tasked to prove that for $1 \leq k \leq n$ \begin{align*} \binom{n + k - 1}{n - 1} = \sum_{i = 1}^k \binom{k - 1}{i - 1} \binom{n}{i} \end{align*} I know that the left part ...
2
votes
3answers
82 views

Combinatorics problem: coefficient of $x^k$ in $(x + x^2 + x^3 + …)^n$

Define $f(n,k)$ with $k \geq n$ as the number of ways to colour $k$ identical objects with $n$ colours, such that every object has one colour and every colour is used at least once. I want to prove ...
1
vote
2answers
119 views

Decide the total amount of six digit numbers which don't contain the sequence.

The following problem. I have to decide how many numbers that satisfy the following It should not contain the sequence 17 eg. 1743, 4179. A leading zero does not count as a digit. 0234 is not a ...
2
votes
4answers
92 views

Combinatorics for integer solutions

How many integer solutions are there to the following equation? $x_1 + x_2 + x_3 = 17$ a) if $x_1 > 1, x_2 > 2, x_3 > 3$ b) if $x_1 < 6, x_3 > 5$ and $x_2$ can be any integer. c) ...
0
votes
2answers
32 views

Permutation and combinatorics problem

How many numbers between 10 and 1000 can be formed using digits 3,4,5,7? Should we first find number of 2 digit numbers and then find number of three digit numbers and add them
1
vote
4answers
84 views

Combinatorics and probability for cards

With a standard 52 deck (13 types and 4 suites), what is the probability that a poker hand contains cards of five different types? A poker hand is a set of 5 cards. The obvious answer is ...