This tag is for basic 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)

3
votes
1answer
33 views

100 students in two classrooms.

Given 100 distinct students and two classrooms: A and B, of 60 and 45 seats respectively. In how many ways can a professor split the students into the two classrooms with respect to their ...
7
votes
2answers
2k views

Permutations with identical objects

How can I find the number of $k$-permutations of $n$ objects, where there are $x$ types of objects, and $r_1, r_2, r_3, \cdots , r_x$ give the number of each type of object? Example: I have 20 ...
0
votes
4answers
60 views

Combinatorics elementary question

A board has a red space, a blue space, and a yellow space. A checker is situated on the red space. On each move the checker is transferred to one of the other two spaces. In how many ways can one make ...
2
votes
1answer
59 views

How many patterns of length 3?

I asked another question that I quess is too hard to be answerd but a want to learn so I have to change the problem: how many patterns with length three we can draw on an android device?
0
votes
1answer
56 views

Intermediate-Advanced Counting Problem

How many standard 6-sided dice do I have to roll to guarantee that some nonempty subset of them add up to a multiple of 5?
3
votes
0answers
49 views

Conjectured Value of Ramsey Number $R(3,10)$

It is known that the value of the Ramsey number $R(3,10)$ is either 40, 41, or 42. Have any experts in the field offered a conjecture as to which it might be?
2
votes
1answer
226 views

Number of ways of placing $n$ distinguishable balls in $k$ indistiguishable bins where the maximum size of a bin is $m$

I know that the number of ways of placing $n$ distinguishable balls in $k$ indistinguishable bins is given by the Stirling number of the second kind. But I don't know how to modify it to include the ...
1
vote
0answers
19 views

Enumerating certain size 15 square matrices

This is an attempt to tackle A zero sum subset of a sum-full set by complete enumeration. I am looking for an algorithm which will efficiently (i.e. within reasonable time, several hours at the most) ...
2
votes
1answer
42 views

Combinatorial Probability

Another exercise from Saeed Ghahramani's Fundamentals of Probability, paraphrased below: Consider a train with $n$ cars and $m > n$ passengers. Suppose passengers board cars randomly. What is ...
-1
votes
2answers
198 views

Count the whistles

Sports Teacher gathered all the players in his garden and ordered them to line up. After the whistle all players should change the order in which they stand. Teacher gave all the students numbers ...
2
votes
1answer
243 views

Probability question involving sets of cards

I have an infinite deck built out of sets of 10 cards (in other words 10*n cards). The sets are identical so one '2' is identical to another '2'. A player draws 6 cards. If he draws: any '1' AND a ...
1
vote
0answers
21 views

Faces of the Permutahedron

We define the Permutahedron as the convex hull of all permutations of the vector $(1,2,\dots,n)\in\mathbb R^n$. I am having trouble seeing why the number of $n-k$ dimensional faces of this polytope is ...
1
vote
2answers
84 views

In how many ways can you divide bonuses between employees?

How many ways are there to divide 33 000 USD between 22 employees of a company (including 1 president, 1 vice-chairman and 20 normal employees), if a normal employee can get 1000 or 1500 USD, whereas ...
1
vote
0answers
46 views

Sum of product of binomial coefficients and exponential function

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
4
votes
1answer
42 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
0
votes
0answers
25 views

How to calculate the number of combinations of getting a pair in a deck of 52 cards?

I am confused over calculating the number of ways in which I can select a pair out of a deck of 52 cards, this is how I go about solving the problem, following the definition of a pair in card games, ...
17
votes
3answers
724 views

Exceptional books on real world applications of graph theory.

What are some exceptional graph theory books geared explicitly towards real-world applications? I would be interested in both general books on the subject (essentially surveys of applied graph ...
1
vote
2answers
100 views

How many patterns?

You probably have seen #patterns# in android devices witch working like passwords. My question is how many patterns can we draw in a 3*3 net and then how many in a m*n? assumptions: -a pattern ...
3
votes
0answers
71 views

Combinatorical interpretation of $\binom{15}{5} = \binom{14}{6}$

I was reading up on Sigmaster's conjecture on repeated binomial coefficiencts and I read that $$\binom{15}{5} = \binom{14}{6}$$ Sure, it's possible to prove it non-combinatorically: ...
1
vote
0answers
82 views

Arranging numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
1
vote
2answers
56 views

Semi-Ambiguous Combinatorics Problem

I'm having trouble fully understanding this introductory combinatorics problem; this is all that's provided, so it's most likely me not fully comprehending the question. Any help is appreciated. The ...
0
votes
1answer
95 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
0
votes
2answers
35 views

Perfect matching for graph with exactly $k$ edges for every node

Consider two disjoint sets $A$ and $B$, each of size $n$. Some (undirected) edges connect nodes in $A$ with nodes in $B$. Suppose that each node (in $A$ or $B$) is adjacent to exactly $k$ of those ...
7
votes
4answers
588 views

Combinatorial proof

Using notion of derivative of functions from Taylor formula follow that $$e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$$ Is there any elementary combinatorial proof of this formula here is my proof for ...
1
vote
2answers
19 views

Counting Problem using Permutations

The Question was: In how many ways can the letters of the English alphabet be arranged so that there are exactly 10 letters between a and z? My approach was the following: In between a and z, there ...
0
votes
1answer
14 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
6
votes
2answers
82 views

Partitioning $\mathbb{N}$ into distinct AP’s

Can $\mathbb{N}$, the set of natural numbers, be partitioned into a finite number of subsets that are in arithmetic progression with distinct steps ?
1
vote
1answer
39 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
0
votes
3answers
29 views

Problematic Permutation Problem

i see a problem without any definition. would you please help me? i want to calculate the number of permutations of 1,2,...,1392 that 696 numbers be in the natural positions (from all numbers, 696 ...
4
votes
1answer
40 views

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin.

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin. $P(\text{H}) = p$. $P(\text{T}) = 1 - p = q$. I came up with the following two-roll ...
2
votes
1answer
34 views

Perfect matching for graph with two edges for every node

Consider two disjoint sets $A$ and $B$, each of size $n$. Some (undirected) edges connect nodes in $A$ with nodes in $B$. Suppose that each node (in $A$ or $B$) is adjacent to at least two edges. Is ...
1
vote
2answers
41 views

Combinations with replacement

In a factory there are 40 employees. A union of 5 people is being chosen. How many combinations are there for a union, if the union contains of 5 different roles, and each employee can hold more than ...
1
vote
3answers
72 views

Counting valid tickets

I think my question is very easy but I need to understand. The problem is, I have a ticket with 2 numbers from 1 to 10. The first number cannot be greather than the second number. How many valid ...
0
votes
3answers
32 views

Basic Combinatorics Choices Question

I'm having some trouble with the question below: I believe the student to have 9 x 8 x 7 x 6 = 3024 choices overall. However I am unsure how to calculate part (a) and (b) of the question. Any help ...
0
votes
0answers
34 views

show by using leibniz formula

There are given $ r, s,n \in\mathbb N$ and $r+s=n$. It also given $A \in M_{r,K} $, $B \in M_{r\times s,K} $ and $C \in M_{s,K} $. Let $M$ be the matrix $\begin{bmatrix}A & B\\0 & ...
0
votes
1answer
151 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
5
votes
1answer
49 views

Closed form for sequence A145271

I would like to know if there is a simple formula or method of expanding the expression given by $\left[g(x) \frac{d}{dx}\right]^n g(x)$ where $n$ is a positive integer, without having to resort to ...
2
votes
1answer
235 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
0
votes
0answers
28 views

Counting question about a rectangular block

Consider the 12 face diagonals of a rectangular block. How many pairs of them are skew lines? (Two lines in space are skew if they do not intersect AND they are not parallel.) Basically I got that ...
4
votes
5answers
192 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
2
votes
3answers
36 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
0
votes
0answers
6 views

densities in sumsets is the product of the desities

Suppose $A,B,X,Y$ are finite subsets of $\mathbb Z$ with $X\subset A$ and $Y\subset B$. By $A+B$ and $X+Y$ we mean $\{a+b:a\in A,b\in B\}$ and $\{x+y:x\in X,y\in Y\}$ respectively. Suppose ...
1
vote
1answer
43 views

Permutations, Combinations, and Counting

A group of 63 people are camping together. They have two 6-person tents, three 4-person tents, five 3-person tents, and three 2 person tents. 18 people will sleep outside of the tents under a tarp. ...
2
votes
1answer
49 views

How many answers can be created using the elementary arithmetic operators?

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)? These are the rules: All numbers ...
0
votes
1answer
31 views

Selecting 6 people from a group of 10 people with special conditions

Sorry for a misleading or such title, but i didn't know how to make it short enough. Anyways, if we have 10 people in a group such that 8 people eat apples, 1 eats pears and one eats watermelons, ...
0
votes
1answer
53 views

Counting the arrangements of 8 people around a square table?

I am trying to solve this problem of counting the number of arrangements of 8 people around a square table, as shown in the figure below, To solve this problem you can consider arrangements obtained ...
0
votes
0answers
179 views

Distributing cards among players

Moderator Note: This is a current contest question on codechef.com. N players sit around a round table. There are $n \cdot m$ cards with unique numbers of range $1\ldots n\cdot m$. Each player ...
0
votes
3answers
37 views

Counting Number of even and distinct digits

The Question was: The number of even four-digit decimal numbers with no digit repeated. So the first digit cannot be 0 so there are 9 ways to choose a digit. Then for the 3rd, 2nd and 1st digits ...
3
votes
0answers
38 views

an elementary problem on wreath product groups with combinatorial flavor

Embarrassingly, I got stuck in solving the following elementary exercise. Let $G=H\wr \Gamma$ be a wreath product groups, $H,\Gamma$ are countable discrete groups, when $\xi\in\oplus_{\Gamma}H$, then ...
2
votes
2answers
50 views

Alternating sum of a simple product of binomial coefficients

I would like to evaluate the following alternating sum of products of binomial coefficients: $$\sum_{k=0}^{m} (-1)^k \binom m k \binom n k .$$ I had the idea to use Pascal recursion to re-express ...